# Traveling Salesman Planet Edition

I completed this problem for an interview and my solution as rejected; of course no reasons were provided.

I opted to use the nearest neighbour algo based on the timeframe allotted and having no indication of the average number of coordinates that will be fed to the function. I didn't want to use an exact solution that could result in terrible performance when given anything larger than a small dataset.

Questions:

• Does my solution to the problem look accurate ?
• What about the quality of my implementation?
• Based on my understanding of the problem statement, I assumed that you can travel in a straight line between planets. Does this seem like an accurate assumption?

Problem statement:

• Create a function to calculate the shortest path between a set of planets from a starting position.

• Universe is two dimensional, coordinates are represented by (x, y) where x and y are integers

• Destinations in the list are unique

• Not allowed to use any third party libraries

• There are multiple solutions to the problem, try to be realistic what can be achieved in few hours

Code:

public interface INavigator {
Coordinate[] route(Coordinate spaceshipPosition, Coordinate[] destinations);
}


Navigator (entry point)

  package com.sandbox.travelingsalesman;

import com.sandbox.travelingsalesman.util.DistanceCalculator;
import com.sandbox.travelingsalesman.util.Pair;

import java.util.*;

public class Navigator implements INavigator {

/*
Lots of system.out.println's in here. Would have preferred to print these using a logging framework at debug level, but this is not allowed as per the requirements
*/

private Set<Coordinate> planetsNotYetVisited;

/**
* Calculates an "optimal" path to vist a set of unique destinations given a starting point. The path is calculated using the Nearest Neighbour heuristic algorithm which has increased performance over an exact one.
*
* @param spaceshipPosition starting position
* @param destinations      set of destinations to visit
* @return "optimal" path to vist without returning to the origin destination.
*/
public Coordinate[] route(Coordinate spaceshipPosition, Coordinate[] destinations) {
final int NUMBER_OF_DESTINATIONS = destinations.length;
planetsNotYetVisited = new HashSet<Coordinate>(Arrays.asList(destinations));

if (spaceshipPosition == null) {
throw new RuntimeException("Spaceship position is null!");
}

if (destinations == null) {
throw new RuntimeException("Destinations is null!");
}

if (destinations.length == 0) {
return new Coordinate;
}
System.out.println("Coordinates to visit: " + Arrays.toString(destinations) + " starting from " + spaceshipPosition);
Coordinate[] optimalRoute = findOptimalRoute(spaceshipPosition, new Coordinate[NUMBER_OF_DESTINATIONS], 0);
System.out.println("Optimal route: " + Arrays.toString(optimalRoute));
return optimalRoute;
}

/*
The problem statement said to design a function to plot an optimal route to visit a unique set of planets. Though the test case was made up of only 8 planets, the problem statement was not limited to such a small dataset. Given the problem statement didn't provide an indication of the posible data sizes, I went with a heuristic algorithim to calculate the path. The algorithim may not always produce the most optimal path, but will scale better performance wise as the data set grows compare to an exact solution which only perfoms OK on very small datasets.
*/
private Coordinate[] findOptimalRoute(Coordinate currentPlanet, Coordinate[] optimalRoute, int counter) {

if (planetsNotYetVisited.size() == 1) {
Iterator<Coordinate> iterator = planetsNotYetVisited.iterator();
Coordinate lastPlanetToVisit = iterator.next();
iterator.remove();
optimalRoute[counter] = lastPlanetToVisit;
return optimalRoute;
}
Coordinate nearestNeighbour = findNearestNeighbour(currentPlanet);
optimalRoute[counter] = nearestNeighbour;
return findOptimalRoute(nearestNeighbour, optimalRoute, ++counter);

}

private Coordinate findNearestNeighbour(Coordinate currentPlanet) {

planetsNotYetVisited.remove(currentPlanet);

List<Pair<Coordinate, Double>> planetsAndTheirDistances = new ArrayList<Pair<Coordinate, Double>>();

System.out.println("Finding nearest neighbour to " + currentPlanet + ">>>");

for (Coordinate planetNotYetVisited : planetsNotYetVisited) {
double distanceFromCurrentPlanet = DistanceCalculator.calcuateDistance(currentPlanet, planetNotYetVisited);
Pair<Coordinate, Double> planetDistance = new Pair<Coordinate, Double>(planetNotYetVisited, distanceFromCurrentPlanet);
System.out.println("Neighbour: " + planetDistance);
}

Collections.sort(planetsAndTheirDistances, PlanetDistanceComparator.getInstance());
final int SMALLEST_DISTANCE_INDEX = 0;
Pair<Coordinate, Double> nearestNeighbour = planetsAndTheirDistances.get(SMALLEST_DISTANCE_INDEX);

Coordinate coordinateOfNearestNeighbour = nearestNeighbour.getFirst();
Double distanceToNearestNeighbour = nearestNeighbour.getSecond();
System.out.println("Found the nearest neighbour to " + currentPlanet + " -> " + coordinateOfNearestNeighbour + " with a distance of " + distanceToNearestNeighbour);
planetsNotYetVisited.remove(coordinateOfNearestNeighbour);
return coordinateOfNearestNeighbour;
}
}


Coordinate:

public class Coordinate {
public final int x;
public final int y;

public final static Coordinate CENTER = new Coordinate(0, 0);

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

@Override
public String toString() {
return String.format("(%d,%d)", x, y);
}

@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (obj == null) {
return false;
}
if (obj.getClass() != getClass()) {
return false;
}

Coordinate c = (Coordinate) obj;
return x == c.x && y == c.y;
}

@Override
public int hashCode() {
return (x * 397) ^ y;
}
}


Distance Calculator

public class DistanceCalculator {

/**
* @param startingPlanetCoordinate
* @param destinationPlanetCoordinate
* @return Distance between two coordinates using Pythagorean theorem
*/
public static double calcuateDistance(Coordinate startingPlanetCoordinate, Coordinate destinationPlanetCoordinate) {

if (startingPlanetCoordinate == null || destinationPlanetCoordinate == null) {
throw new RuntimeException("One or both of starting and destination coordinates is null! startingPlanetCoordinate[" + startingPlanetCoordinate + "] destinationPlanetCoordinate[" + destinationPlanetCoordinate + "]");
}

if (startingPlanetCoordinate.equals(destinationPlanetCoordinate)) {
return 0;
}

int distanceBetweenXcordinates = destinationPlanetCoordinate.x - startingPlanetCoordinate.x;
double squaredDistanceBetweenXcoordinates = Math.pow(distanceBetweenXcordinates, 2);

int distanceBetweenYcoordinates = destinationPlanetCoordinate.y - startingPlanetCoordinate.y;
double squaredDistanceBetweenYcoordinates = Math.pow(distanceBetweenYcoordinates, 2);

return Math.sqrt(squaredDistanceBetweenXcoordinates + squaredDistanceBetweenYcoordinates);
}
}


PlanetDistanceComparator

/*
Ideally would have made PlanetDistanceComparator a Spring managed bean,
but the requirements disallow libraries not already included in the pom
*/

public class PlanetDistanceComparator implements Comparator<Pair<Coordinate, Double>> {

private static PlanetDistanceComparator instance = null;

public static PlanetDistanceComparator getInstance() {
if (instance == null) {
instance = new PlanetDistanceComparator();
}
return instance;
}

/**
* Compares based on distance between 2 planets
*
* @param planetA
* @param planetB
* @return -1 if planetA's distance from the current planet is shorter than planetB's,
*          0 if planetA's distance from the current planet is equal to that of planetB's,
*          1 if planetA's distance from the current planet is greater than planetB's
*/
public int compare(Pair<Coordinate, Double> planetA, Pair<Coordinate, Double> planetB) {

Double distanceToPlanetA = planetA.getSecond();
Double distanceToPlanetB = planetB.getSecond();
return distanceToPlanetA.compareTo(distanceToPlanetB);
}
}


Pair

    public class Pair<F, S> {

private F first;
private S second;

public Pair(F first, S second) {

this.first = first;
this.second = second;
}

public F getFirst() {
return first;
}

public S getSecond() {
return second;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;

Pair<?, ?> pair =

(Pair<?, ?>) o;

if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
return second != null ? second.equals(pair.second) : pair.second == null;

}

@Override
public int hashCode() {
int result = first != null ? first.hashCode() : 0;
result = 31 * result + (second != null ? second.hashCode() : 0);
return result;
}

public String toString() {
return "[" + first + "][" + second + "]";
}
}


In findNearestNeighbour(), you compute n distances, add them to an ArrayList, sort the ArrayList, and then get the first element to find the nearest neighbor.
If you simply kept track of the best candidate as you computed the n distances, you wouldn't need to perform the sort. This would reduce the time complexity of this step from $O(n \log n)$ to $O(n)$. It would also allow you to eliminate the code for Pair and PlanetDistanceComparator, which almost reduces your code by half.
If I were an evaluator, I personally would find your solution to be overly complex for the problem asked. By complex, I mean you added a lot of extra unnecessary code, such as hashCode functions, etc. If I were to write my own solution, it would probably end up in less than 50 lines of code total.