Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## Destination Routing

I have a project that should prompt the user to enter as many cities as he likes with x and y coordinates. When he is done entering cities the program should use recursion to pick each city from the list and calculate the distance. So lets say the user enters 3 cities.

New York 10, 15
Las Vegas 33, 55
Denver 22, 44

I need to calculate the distance from New York to Las Vegas and from Las Vegas to Denver, then add it all up and display it.

Here are the actual instructions: Create a Java program that prompts the user for a list of cities, where each city has a name and x and y coordinates. After all cities have been entered, the program should use a recursive algorithm to print the length of all possible routes that start at the first city entered and end at the last city entered, and visit every city in the list. For each route, the program should print the name of each city visited, followed by the length of the route.

Can anyone point me in the right direction? If you have any suggestions on how to solve this a different way please let me know. My brain is smoking right now.
Here is what I have so far:

Code:
package Citydistance;

import java.util.*;

public class Cityroute {

public static void main(String[] args)
{
Scanner scanner = new Scanner (System.in);

String city = "";
double x = 0;
double y = 0;
int choice = 0;

// First run to enter the starting location.
System.out.println("Enter the name of the city:");
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

System.out.println();
System.out.println("Pick one of the following choices:");
System.out.println(" 1. Enter another city");
System.out.println(" 2. Enter destination");
System.out.println(" 3. Exit");

System.out.println();
choice = scanner.nextInt();

while(choice == 1)
{
switch(choice)
{
case 1:
System.out.println("Enter the name of the city:");
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

System.out.println();
System.out.println("Pick one of the following choices:");
System.out.println(" 1. Enter another city");
System.out.println(" 2. Enter destination");
System.out.println(" 3. Exit");

System.out.println();
choice = scanner.nextInt();

break;

case 3:
// Exit
System.out.println("Good bye");
System.exit(0);
break;

}// end switch
}// end loop

// Enter final destination
city = scanner.next();
System.out.println("Enter the X coordinate");
x = scanner.nextDouble();
System.out.println("Enter the Y coordinate");
y = scanner.nextDouble();

System.out.println("City: " + city + " X " + x + " Y " + y);
System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

// Compute the distance between all the cities recursively, print all cities, and the total distance
// between all cities. Not Sure How....?????

double distance = 0;
double endX = 0;
double startX = 0;
double endY = 0;
double startY = 0;
distance = Math.sqrt((endX-startX)*(endX-startX) + (endY-startY)*(endY-startY));

}// end main
}//end class

• I would suggest you make a tree data structure which has a node for every city in between the first and last, which has a child node for each remaining city, which has a child node for each remaining city .... get the idea?

Graph traversal algorithms may also be of some help.

cs_student

• I'll be honest with you. This is my first java class and only my second project. too me I'm doing a lot for someone just figuring it out so maybe the class just assumes everyone is good at java so I don't know. But what I did in the above code took me 5 hours to figure out.

• Well, let's take a simple example.

Let's say 5 cities, named A through E.

So you need to find all of the following path distances:
A - B - C - D - E
A - B - D - C - E
A - C - B - D - E
A - C - D - B - E
A - D - B - C - E
A - D - C - B - E

yes? Is that your understanding of the question, as well???

• Originally Posted by Old Pedant
Well, let's take a simple example.

Let's say 5 cities, named A through E.

So you need to find all of the following path distances:
A - B - C - D - E
A - B - D - C - E
A - C - B - D - E
A - C - D - B - E
A - D - B - C - E
A - D - C - B - E

yes? Is that your understanding of the question, as well???
Yes that is my understanding.

• Okay, so the concept is simply enough.
Code:
Pick 2nd city B, calculate A->B
Pick 3rd city C, calculate B->C
Pick 4th City D, calculate C->D
Do last city, calculate D->E
Pick 3rd city D, calculate B->D
Pick 4th City C, calculate D->C
Do last city, calculate C->E
No more 3rd cities
Pick 2nd city C, calculate A->C
Pick 3rd city B, calculate C->B
... etc. ...
And the only "tricks" needed are:
-- Each level of indentation above represents a recursive call to the "pick next city" function
-- You need to mark which cities have been picked, so they aren't picked again at a lower level in the recursion
-- You need to reset all the marks each time you go back to start from city A

I'd like to see you at least attempt to write the recursion before I step in again. You need to learn to think like a computer and if I write it all that won't help you.

• Old Pedant: Your spot on. Now if only I knew how to do any of that I know, I suck. I'm trying. Java isn't my forte at all and I'm trying to cram all this in.

• If it's any comfort, I don't think this is a trivial exercise. The fact that the only good way I can see to accomplish this involves somehow "marking" cities as "already used on this path" and then unmarking them before you try the next path makes it a pain in the patootie. Maybe I'm wrong; maybe there's a way around that. But I don't see it.

Let me give you one huge hint:

It will all be a lot easier if you first create a City class.

Something like this:
Code:
class City
{
String cityname;
double xPosition;
double yPositon;
boolean hasBeenUsedOnThisPath; // or pick a shorter name <grin/>
}
So now you have an array of City, rather than 3 individual arrays (or 4, if you added the boolean marker).

Much simpler conceptually, not to mention more "correct" in any programming style or academic sense.

• And might I strongly suggest that you completely separate the code that fills that array (using...ugh...the Scanner) from the code that processes it.

That way you could initially test the route-creatiion code by using a constant JS array instead of having to continually run the program and enter 5 cities, etc., and thus take forever to debug.

That is, for testing purposes, you could do:
Code:
City[] cities = new City[5];
cities[0] = new City("Albuquerque", 3611, 3418 );
cities[1] = ...
etc.
Oh, did I forget to mention your City class should have a constructor? <grin/>

• Ok I created a better structure.

Code:
public class City{

private int x, y;
private String name;
boolean hasvisited;

public City(){

int x = 0;
int y = 0;
String name = "";
boolean hasvisited = false;
}

public City(int x, int y, String name){

this.x = x;
this.y = y;
this.name = name;
}

public int getX(){return x;} //returns value stored in x
public int getY() {return y;}
public String getName() {return name;}

public void setX(int x){this.x = x;}
public void setY(int y){this.y = y;}
public void setName(String name){this.name = name;}

public double distance(City other){

}
}
Now I just have to figure out where to put all my scanner stuff readin stuff and then of course the main part of the actual project.

• You could use a static method on class City that would return an instance of City.

So your basic code to get a list of cities would be something like:
Code:
ArrayList<City> cities = new ArrayList<City>( );
while ( true )
{
City nextCity = City.getCityFromScanner( scanner );
if ( nextCity == null ) break;
}

• As a very minor comment: You really shouldn't have any use for the set methods for the City class, except for setHasvisited, and you'd probably want to use something like
Code:
public void setHasvisited() { this.hasvisited = true; }
public void resetHasvisited() { this.hasvisited = false; }
for that. And I can't see a need for a default constructor, either. Or, if you have one, make it private, perhaps?

Why are x and y int? If they are intended to be latitude and longitude, for example, they should be double. But if the problem spec says int is adequate, ignore me.

• Yea your right I need to change it to double. I just don't know how to tie it all together.

Code:
import java.util.*;
import java.io.*;

//a class to model a City object
public class City{

private Double x, y;
private String name;
boolean hasvisited;

public City(){

int x = 0;
int y = 0;
String name = "";
boolean hasvisited = false;
}

public double getX(){return x;}
public double getY() {return y;}
public String getName() {return name;}

public void setX(Double x){this.x = x;}
public void setY(Double y){this.y = y;}
public void setName(String name){this.name = name;}

public getCities()
{
try
{

//Prompt the user for the city of orgin.
System.out.println("Please enter the city of orgin:");
System.out.println("Please enter the X cordinate for the city of orgin:");
System.out.println("Please enter the Y cordinate for the city of orgin:");

//Prompt the user for the Destination city.
System.out.println("Please enter the X cordinate for the destination city:");
System.out.println("Please enter the Y cordinate for the destination city:");

//Initilize a loop to prompt the user for one of more additional cities.
boolean cont = true;
while (cont == true)
{

//Prompt the user for the next city.
System.out.println("Please enter the next city(Type \"exit\" to quit.):");
if (nextCity.equalsIgnoreCase("exit"))
{
cont = false;
}
else
{
System.out.println("Please enter the X cordinate for the next city:");
System.out.println("Please enter the Y cordinate for the next city:");

//Add the information entered to the appropriate stacks.
}

}

}

//Catch block to complete try block.
catch(IOException e)
{
System.out.println(e.getMessage());
}

ArrayList<City> cities = new ArrayList<City>( );
while ( true )
{
City nextCity = City.getCityFromScanner( scanner );
if ( nextCity == null ) break;
}

public double distance(City other){

}
}

• You "getCities( )" method should *NOT* be in the City class!!!

It should be in your main class, whatever you call it. Maybe
Code:
class FunWithRoutes
In fact, you probably won't have a getCities() method. It will probably just be part of the main() method.

BUT...

But the code in the main class should *NOT* prompt for cityname/x/y. *THAT* should be in the City.getCityFromScanner() method.

Code:
class FunWithDickAndJane
{
boolean testing = true; // so you don't have to input cities while testing
ArrayList<City> cities;

public void main( )
{
cities = new ArrayList<City>( );
if ( testing )
{
cities.add( new City("Albuquerque", 33.173, 44.111 ) );
cities.add( new City("Baltimore", 22.222, 11.111 ) );
cities.add( new City("Chicago", 28.111, 19.333 ) );
cities.add( new City("Denver", 5.280, 55.444 ) );
}
else
{
System.out.println("Enter your cities, in order.  Enter a blank city name after the last city.");
while ( true )
{
City nextCity = City.getCityFromScanner( scanner ); // assuming you use a Scanner instance
if ( nextCity == null ) break;
}
}
// and then your do-all-routes code starts here
...
}
// you will have at least one method that uses recursion:
double nextCityOnRoute( ??? what are your arguments ??? )
{
... the tough part ...
}
}
Don't forget that the getCityFromScanner should be a static method.

• So like this?

Code:
import java.util.*;
import java.io.*;

//a class to model a City object
public class Cityroute{

private Double x, y;
private String name;
boolean hasvisited;

public City(){

double x = 0;
double y = 0;
String name = "";
boolean hasvisited = false;
}

public double getX(){return x;}
public double getY() {return y;}
public String getName() {return name;}

public void setX(Double x){this.x = x;}
public void setY(Double y){this.y = y;}
public void setName(String name){this.name = name;}

class FunWithDickAndJane
{
boolean testing = true; // so you don't have to input cities while testing
ArrayList<City> cities;

public void main( )
{
cities = new ArrayList<City>( );
if ( testing )
{
cities.add( new City("Albuquerque", 33.173, 44.111 ) );
cities.add( new City("Baltimore", 22.222, 11.111 ) );
cities.add( new City("Chicago", 28.111, 19.333 ) );
cities.add( new City("Denver", 5.280, 55.444 ) );
}
else
{
System.out.println("Enter your cities, in order.  Enter a blank city name after the last city.");
while ( true )
{
City nextCity = City.getCityFromScanner( scanner ); // assuming you use a Scanner instance
if ( nextCity == null ) break;
}
}
// and then your do-all-routes code starts here
...
}
// you will have at least one method that uses recursion:
double nextCityOnRoute( ??? what are your arguments ??? )
{
... the tough part ...
}
}

•

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•