# Travelling salesman with four cities

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");
}
}
}

• Welcome back! Please add a bit more context, so that people that didn't see your previous migrated post don't have to infer everything the code does from the code itself :) – Mathieu Guindon Jan 16 '14 at 4:19
• I took the liberty of adding your original text (actually @Jamal's edit), feel free to rollback or edit as you like. I'm sure reviews are coming! – Mathieu Guindon Jan 16 '14 at 4:40

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;
}
}

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++) {
}


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++) {
}

RoutePlanner planner = new RoutePlanner(cityCoordinates);

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

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

List<Integer> shortestRoutes = findIndicesOfMinima(distances);

printShortestRoutes(shortestRoutes, distances);
}

/** Prompt the user for the coordinates of city number 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<>();
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<>();
double minimum = distances.get(0);

for (int i = 1; i < distances.size(); i++) {
double d = distances.get(i);
if (d < minimum) {
indices.clear();
minimum = d;
} else if (d == minimum) {
}
}
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.
• Excellent! I would add another rule of thumb for programmers: there should be 0, 1, or 2 of something. If you have 3 or more, it's probably time to generalize. Therefore, if you have 3 variables for cities, that's a sign that they should be replace with something like an array or list. – 200_success Jan 16 '14 at 10:24