Travelling salesman with four cities

Question

I am writing a program that is based on the Travelling Salesman Problem. There are four cities in which the user determines its x and y coordinates. The salesman always starts at city1 and ends up at city1, so there are 6 possible routes. However, each route has an equivalent route, i.e route1 has the same distance as route6. I have accounted for this. I've also tried to account for if (route1 or route6) and (route2 or route4) have the same distance. The program tells you that.

import java.util.Scanner;
import java.lang.Math;

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

     //x and y coordinates of each city
     int x1, y1, x2, y2, x3, y3, x4, y4;

     //Variable for the distances of each route
     double route1, route2, route3, route4, route5, route6; 

     //Since the distance from cityA to cityB is the same as the distance from cityB to cityA,
     //these are all the possible combinations of distances between each city
     double city1city2, city2city3, city3city4, city4city1, city2city4, city3city1;
     double city2city1, city3city2, city4city3, city1city4, city4city2, city1city3;

     double shortestRoute;

     System.out.println("Enter the value of each city's x-coordinate and y-coordinate");
     System.out.println(" ");

     //First city
     System.out.println("City 1's x-coordinate:");
     x1 = keyboard.nextInt();
     System.out.println("City 1's y-coordinate:"); 
     y1 = keyboard.nextInt();

     //Second city
     System.out.println("City 2's x-coordinate:");
     x2 = keyboard.nextInt();
     System.out.println("City 2's y-coordinate:"); 
     y2 = keyboard.nextInt();

     //Third city
     System.out.println("City 3's x-coordinate:");
     x3 = keyboard.nextInt();
     System.out.println("City 3's y-coordinate:"); 
     y3 = keyboard.nextInt();

     //Fourth city
     System.out.println("City 4's x-coordinate:");
     x4 = keyboard.nextInt();     
     System.out.println("City 4's y-coordinate:"); 
     y4 = keyboard.nextInt();

     System.out.println(" ");
     System.out.println("City 1's coordinates are: (" +  x1 + ", "  +  y1 +")");
     System.out.println("City 2's coordinates are: (" +  x2 + ", "  +  y2 +")");
     System.out.println("City 3's coordinates are: (" +  x3 + ", "  +  y3 +")");
     System.out.println("City 4's coordinates are: (" +  x4 + ", "  +  y4 +")");

       //Computing all possible combinations of distance between each city
       city1city2 = Math.sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)); //distance from city1 to city2 
       city3city1 = Math.sqrt((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)); //distance from city1 to city3 
       city4city1 = Math.sqrt((x1 - x4)*(x1 - x4) + (y1 - y4)*(y1 - y4)); //distance from city4 to city1
       city2city3 = Math.sqrt((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3)); //distance from city2 to city3 
       city3city4 = Math.sqrt((x3 - x4)*(x3 - x4) + (y3 - y4)*(y3 - y4)); //distance from city3 to city4 
       city2city4 = Math.sqrt((x2 - x4)*(x2 - x4) + (y2 - y4)*(y2 - y4)); //distance from city2 to city4 

       city2city1 = city1city2; //distance from city2 to city1
       city3city2 = city2city3; //distance from city3 to city2
       city4city3 = city3city4; //distance from city4 to city3
       city1city4 = city4city1; //distance from city1 to city4
       city4city2 = city2city4; //distance from city4 to city2
       city1city3 = city3city1; //distance from city1 to city3

       //Computing the distance of each possible route
       route1 = city1city2 + city2city3 + city3city4 + city4city1;
       route2 = city1city2 + city2city4 + city4city3 + city3city1;
       route3 = city1city3 + city3city2 + city2city4 + city4city1;
       route4 = city1city3 + city3city4 + city4city2 + city2city1;
       route5 = city1city4 + city4city2 + city2city3 + city3city1;
       route6 = city1city4 + city4city3 + city3city2 + city2city1;

       System.out.println(" ");
       System.out.println("The first route has a total distance of " + route1 + " km");
       System.out.println("The second route has a total distance of " + route2 + " km");
       System.out.println("The third route has a total distance of " + route3 + " km");
       System.out.println("The fourth route has a total distance of " + route4 + " km");
       System.out.println("The fifth route has a total distance of " + route5 + " km");
       System.out.println("The sixth route has a total distance of " + route6 + " km");

       shortestRoute = Math.min(Math.min(route1, Math.min(route2,route3)), Math.min(route4,Math.min(route5,route6)));
       System.out.println(" ");

       boolean r1 = shortestRoute == route1 || shortestRoute == route6;
       boolean r2 = shortestRoute == route2 || shortestRoute == route4;
       boolean r3 = shortestRoute == route3 || shortestRoute == route5;

       if(r1 && r2 && r3) 
       {
         System.out.println("Every route has the same distance, there is no best route");
       }
       else if(r1 && r2)
       {
         System.out.println("route1, route2, route4 and route6 are the best routes");
       }
       else if(r1 && r3)
       {
         System.out.println("route1, route3, route5 and route6 are the best routes");
       }
       else if(r2 && r3)
       {
         System.out.println("route2, route3, route4 and route5 are the best routes");
       }
       else if(r1)
       {
         System.out.println("route1 and route6 are the best routes");
       }
       else if(r2)
       {
         System.out.println("route2 and route4 are the best routes");
       }
       else
       {
         System.out.println("route3 and route5 are the best routes");
       }
   }
}

Answer 1

The biggest high-level comment I have is that you need to learn about modularity; that is, how to divide your code into separate components that act independently, so that you can reuse those components instead of copy-pasting and editing code. The basic unit of modularity in most programming languages is the function.

---

Let's start with a simple example. You repeat the following lines 4 times with slight modifications:

System.out.println("City 1's x-coordinate:");
x1 = keyboard.nextInt();
System.out.println("City 1's y-coordinate:"); 
y1 = keyboard.nextInt();

Instead, let's define a little data structure and function (quick note: all the code in this answer is untested -- there may be typos in here):

public class Coordinate {
    public final int x;
    public final int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Coordinate readCityCoordinate(int i) {
    System.out.format("City %d's x-coordinate%n");
    int x = keyboard.nextInt();
    System.out.format("City %d's y-coordinate%n");
    int y = keyboard.nextInt();
    return new Coordinate(x, y);
}

And in the calling function, you'll write

List<Coordinate> cityCoordinates = new ArrayList<>();
for (int i = 1; i <= 4; i++) {
    cityCoordinates.add(readCityCoordinate(i));
}

---

OK, the next thing to think about it the overall reusability of this code. Today you want to be able to enter 4 cities' coordinates, compute the shortest route, and then print out the result. Tomorrow, you may be writing some mapping software, and you'll have a bunch of cities in your dataset, and each user may ask you the length of a different route. You may want to do other things with the data, too. The idea is to separate the things that pertain to this general class of problem from the things that are specific to this particular problem (find the shortest route among four cities). Let's make a flexible class design that you may be able to extend later.

import java.util.Iterable;
import java.util.List;

public class RoutePlanner {
    private List<Coordinate> landmarkCoordinates;

    public class Coordinate {
        public final int x;
        public final int y;
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public RoutePlanner(List<Coordinate> landmarkCoordinates) {
        this.landmarkCoordinates = landmarkCoordinates;
    }

    // 
    public double computeRouteDistance(Iterable<Integer> route) {
        // We'll fill this in later
    }
    // We may add more class members later, too.
}

---

OK, we've figure out the general shape of our main abstraction. That will drive the design of the main function. We'll want to do the following things:

1. Read in the coordinates of our four cities.
2. Build a RoutePlanner out of these landmarks.
3. Compute the length of each route.
4. Figure out which routes are shortest.
5. Print out the shortest routes.

That tells us how main should be written! Each set should correspond to a function call or perhaps 2-3 lines in your main function.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

class CityDistancesProgram {
    private static Scanner keyboard = new Scanner(System.in);

    public static void main(String[] args) {
        List<RoutePlanner.Coordinate> cityCoordinates = new ArrayList<>();
        for (int i = 1; i <= 4; i++) {
            cityCoordinates.add(readCityCoordinate(i));
        }

        RoutePlanner planner = new RoutePlanner(cityCoordinates);

        List<List<Integer>> routes = enumerateRoutes();

        List<Double> distances = new ArrayList<>();
        for (List<Integer> route : routes) {
            distances.add(planner.computeRouteDistance(route));
        }

        List<Integer> shortestRoutes = findIndicesOfMinima(distances);

        printShortestRoutes(shortestRoutes, distances);
    }

    /** Prompt the user for the coordinates of city number i */
    private RoutePlanner.Coordinate readCityCoordinate(int i) {
        // Defined above
    }

    /** Returns a list of all circuits through the four cities. */
    private List<List<Integer>> enumerateRoutes() {
    }

    /**
     * Returns of a list of the indices of all of the elements
     * that are equal to the minimum value in the input list.
     */
    private List<Integer> findIndicesOfMinima(List<Double> distances) {
    }

    /** Prints out which routes were shortest. */
    private void printShortestRoutes(List<Integer> shortestRoutes
        List<Double> distances) {
    }
}

Now a reader can look at your main, and in a few seconds figure out how the program works. Now let's talk about the helper functions!

---

The first is enumerateRoutes, which is pretty straightforward. The idea is that we want to produce values that we can feed to RoutePlanner's computeRouteDistance method.

    private List<List<Integer>> enumerateRoutes() {
        // Note: you can generalize this to list all permutations of
        // 0, 1, ..., n that begin with 0, but let's hold on to this
        // for now -- permutation code is much more complicated than
        // this, so it doesn't seem worth it when we know we have
        // only four cities.
        List<List<Integer>> routes = new ArrayList<>();
        routes.add(Arrays.asList(0, 1, 2, 3, 0));
        routes.add(Arrays.asList(0, 1, 3, 2, 0));
        routes.add(Arrays.asList(0, 2, 1, 3, 0));
        routes.add(Arrays.asList(0, 2, 3, 1, 0));
        routes.add(Arrays.asList(0, 3, 1, 2, 0));
        routes.add(Arrays.asList(0, 3, 2, 1, 0));
        return routes;
    }

You'll note that these routes use a 0-based index system, not a 1-based index system. That's only sensible, as that's what Java uses!

---

Now findIndicesOfMinima. I favor an approach that keeps a running tab on which values are currently minimum, rather than computing the minimum and then going back through the list to find which values actually match it.

    private List<Integer> findIndicesOfMinima(List<Double> distances) {
        List<Integer> indices = new ArrayList<>();
        indices.add(0);
        double minimum = distances.get(0);

        for (int i = 1; i < distances.size(); i++) {
            double d = distances.get(i);
            if (d < minimum) {
                indices.clear();
                indices.add(i);
                minimum = d;
            } else if (d == minimum) {
                indices.add(i);
            }
        }
        return indices;
    }

---

OK, we're up to printShortestRoutes. Instead of coming up with an if-else block with a slightly different bit of code in each stanza, let's try to generalize.

    private void printShortestRoutes(List<Integer> shortestRoutes,
        List<Double> distances) {
        assert(shortestRoutes.size() >= 2);
        if (shortestRoutes.size() == 2) {
            System.out.format(
                "route%d and route%d are the best routes (distance %f)%n",
                shortestRoutes.get(0), shortestRoutes.get(1),
                distances.get(shortestRoutes.get(0));
        } else {
            for (int i = 0; i < shortestRoutes.size() - 1; i++) {
                System.out.format("route%d, ", shortestRoutes.get(i));
            }
            System.out.format(
                "and route%d are the best routes (distance %f)%n",
                shortestRoutes.get(shortestRoutes.size() - 1),
                distances.get(shortestRoutes.get(0)));
        }
    }

This could be made a bit cleaner, but it gives the general idea.

---

The last thing to write is RoutePlanner.computeRouteDistance.

public double computeRouteDistance(Iterable<Integer> route) {
    double distance = 0.0;
    Iterator<Integer> it = route.iterator();
    if (!it.hasNext()) return 0;
    int prev = it.next();
    while (it.hasNext()) {
        int next = it.next();
        distance += computeDistance(prev, next);
        prev = next;
    }
    return distance;
}

private double computeDistance(int i, int j) {
    Coordinate ci = landmarkCoordinates.get(i);
    Coordinate cj = landmarkCoordinates.get(j);
    return Math.sqrt((ci.x - cj.x) * (ci.x - cj.x)
        + (ci.y - cj.y) * (ci.y - cj.y));
}

---

That's it for a first pass! Some general rules of thumb to keep in mind:

• Try not to repeat yourself in code (this is known in some circles as the DRY principle).
• If you can break a function down into logical steps, each step should probably be a function call.
• If you can't think of a good name that describes what a function is doing, it should probably be two or more functions.