Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 23
  1. #1
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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);
                     LinkedList citiesList = new LinkedList();
                     LinkedList yList = new LinkedList();
                     LinkedList xList = new LinkedList();
    
                     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();
                     citiesList.addFirst(city);
                     System.out.println("Enter the X coordinate");
                     x = scanner.nextDouble();
                     xList.addFirst(x);
                     System.out.println("Enter the Y coordinate");
                     y = scanner.nextDouble();
                     yList.addFirst(y);
    
                     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)
                            {
                               // enter additional cities
                               case 1:
                                      System.out.println("Enter the name of the city:");
                                      city = scanner.next();
                                      citiesList.add(city);
                                      System.out.println("Enter the X coordinate");
                                      x = scanner.nextDouble();
                                      xList.add(x);
                                      System.out.println("Enter the Y coordinate");
                                      y = scanner.nextDouble();
                                      yList.add(y);
    
                                      System.out.println("City: " + city + " X " + x + " Y " + y);
                                      System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);
    
                                                    // ask for next choice
                                      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
                     System.out.println("Enter your final destination:");
                     city = scanner.next();
                     citiesList.addLast(city);
                     System.out.println("Enter the X coordinate");
                     x = scanner.nextDouble();
                     xList.addLast(x);
                     System.out.println("Enter the Y coordinate");
                     y = scanner.nextDouble();
                     yList.addLast(y);
    
                     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

  • #2
    Regular Coder cs_student's Avatar
    Join Date
    Oct 2009
    Location
    ~/
    Posts
    195
    Thanks
    2
    Thanked 22 Times in 22 Posts
    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

  • #3
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #4
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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???
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #5
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Old Pedant View Post
    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.

  • #6
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #7
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #8
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #9
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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/>
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #10
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #11
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    You could use a static method on class City that would return an instance of City.

    Not a bad design pattern.

    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;
             cities.add( nextCity );
        }
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #12
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #13
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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:");
                            String orginCity = in.readLine();
                            System.out.println("Please enter the X cordinate for the city of orgin:");
                            int orginX = Integer.parseInt(in.readLine());
                            System.out.println("Please enter the Y cordinate for the city of orgin:");
                            int orginY = Integer.parseInt(in.readLine());
    
                            //Prompt the user for the Destination city.
                            System.out.println("Please enter the destination city:");
                            String destinationCity = in.readLine();
                            System.out.println("Please enter the X cordinate for the destination city:");
                            int destinationX = Integer.parseInt(in.readLine());
                            System.out.println("Please enter the Y cordinate for the destination city:");
                            int destinationY = Integer.parseInt(in.readLine());
    
                            //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.):");
                                    String nextCity = in.readLine();
                                    if (nextCity.equalsIgnoreCase("exit"))
                                    {
                                            cont = false;
                                    }
                                    else
                                    {
                                            System.out.println("Please enter the X cordinate for the next city:");
                                            int nextX = Integer.parseInt(in.readLine());
                                            System.out.println("Please enter the Y cordinate for the next city:");
                                            int nextY = Integer.parseInt(in.readLine());
    
                                            //Add the information entered to the appropriate stacks.
                                            name.add(nextCity);
                                            x.add(nextX);
                                            y.add(nextY);
                                    }
    
                            }
    
                    }
           
                           //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;
             cities.add( nextCity );
        }
           
           public double distance(City other){
    
           }
    }
    Last edited by JynxRD; 05-15-2010 at 01:18 AM.

  • #14
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,919
    Thanks
    79
    Thanked 4,423 Times in 4,388 Posts
    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.

    In other words, your main class, main method should start with something like this:
    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;
                     cities.add( nextCity );
                }
            }
            // 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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #15
    New Coder
    Join Date
    Nov 2008
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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;
                     cities.add( nextCity );
                }
            }
            // 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 ...
        }
    }


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

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