patternjavaModerate

Travelling salesman with four cities

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

salesmanwithfourtravellingcities

Problem

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

Solution

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 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 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 landmarkCoordinates) {
        this.landmarkCoordinates = landmarkCoordinates;
    }

    // 
    public double computeRouteDistance(Iterable 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:

Read in the coordinates of our four cities.

Build a RoutePlanner out of these landmarks.

Compute the length of each route.

Figure out which routes are shortest.

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 cityCoordinates = new ArrayList<>();
        for (int i = 1; i > routes = enumerateRoutes();

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

        List 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> 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 findIndicesOfMinima(List distances) {
    }

    /** Prints out which routes were shortest. */
    private void printShortestRoutes(List shortestRoutes
        List 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> 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> routes = new A

Code Snippets

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

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

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

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

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

Context

StackExchange Code Review Q#39353, answer score: 12

Revisions (0)

No revisions yet.