package aps2.tsp;
class Node{
	int id;
	int x;
	int y;
	Node(int x,int y,int id){
		this.id = id;
		this.x = x;
		this.y = y;
	}
}
public class TravellingSalesman {
	int N,added, maxn = 18;
	int[] optimal;
	double resDist;
	Node nodes[];
	public TravellingSalesman() {
		this.N=0;
		this.nodes = new Node[100];
	}
	/**
	 * To solve the travelling salesman problem (TSP) you need to find a shortest
	 * tour over all nodes in the graph where each node must be visited exactly
	 * once. You need to finish at the origin node.
	 *
	 * In this task we will consider complete undirected graphs only with
	 * Euclidean distances between the nodes.
	 */

	/**
	 * Adds a node to a graph with coordinates x and y. Assume the nodes are
	 * named by the order of insertion.
	 *
	 * @param x X-coordinate
	 * @param y Y-coordinate
	 */
	public void addNode(int x, int y){
		Node n = new Node(x,y,N);
		nodes[N] = n;
		N++;
	}

	/**
	 * Returns the distance between nodes v1 and v2.
	 *
	 * @param v1 Identifier of the first node
	 * @param v2 Identifier of the second node
	 * @return Euclidean distance between the nodes
	 */
	public double getDistance(int v1, int v2) {
		return Math.sqrt(Math.pow(nodes[v1].x - nodes[v2].x, 2)+Math.pow(nodes[v1].y - nodes[v2].y, 2));
	}

	/**
	 * Finds and returns an optimal shortest tour from the origin node and
	 * returns the order of nodes to visit.
	 *
	 * Implementation note: Avoid exploring paths which are obviously longer
	 * than the existing shortest tour.
	 *
	 * @param start Index of the origin node
	 * @return List of nodes to visit in specific order
	 */

	double DP[][];
	public int[] calculateExactShortestTour(int start){
		calculateExactShortestTourDistance(start);
		int mask = (1<<N)-1, last = start;
		int path[] = new int[N];
		for(int i=0;i<N;i++) {
			for(int k=0;k<N;k++) {
					if((mask&(1<<k))!=0){
						if(DP[mask^(1<<last)][k]+getDistance(k,last)==DP[mask][last]) {
							mask ^= (1<<last);
							last = k;
							path[N-1-i]=k;
							break;
						}
					}
			}
		}
		return path;
	}
	/**
	 * Returns an optimal shortest tour and returns its distance given the
	 * origin node.
	 *
	 * @param start Index of the origin node
	 * @return Distance of the optimal shortest TSP tour
	 */
	public double calculateExactShortestTourDistance(int start){
		DP = new double[1<<maxn][maxn];
		for(int i=0;i<(1<<maxn);i++)
			for(int j=0;j<(maxn);j++)
				DP[i][j] = Double.MAX_VALUE;
		DP[0][start] = 0.0;

		for (int k = 0; k < (1 << N); k++)
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if ((k & (1 << j)) == 0)
						DP[k | (1 << j)][j] = Math.min(DP[k | (1 << j)][j], getDistance(i, j) + DP[k][i]);
				}
			}

		return DP[(1<<N) - 1][0];

	}
	/**
	 * Returns an approximate shortest tour and returns the order of nodes to
	 * visit given the origin node.
	 *
	 * Implementation note: Use a greedy nearest neighbor apporach to construct
	 * an initial tour. Then use iterative 2-opt method to improve the
	 * solution.
	 *
	 * @param start Index of the origin node
	 * @return List of nodes to visit in specific order
	 */
	public int[] calculateApproximateShortestTour(int start){
		int[] initial = nearestNeighborGreedy(start);
		return twoOptExchange(initial);
	}

	/**
	 * Returns an approximate shortest tour and returns its distance given the
	 * origin node.
	 *
	 * @param start Index of the origin node
	 * @return Distance of the approximate shortest TSP tour
	 */
	public double calculateApproximateShortestTourDistance(int start){
		optimal = calculateApproximateShortestTour(start);
		return calculateDistanceTravelled(optimal);
	}

	/**
	 * Constructs a Hamiltonian cycle by starting at the origin node and each
	 * time adding the closest neighbor to the path.
	 *
	 * Implementation note: If multiple neighbors share the same distance,
	 * select the one with the smallest id.
	 *
	 * @param start Origin node
	 * @return List of nodes to visit in specific order
	 */
	public int[] nearestNeighborGreedy(int start){
		int[] res = new int[N+1];
		boolean visited[] = new boolean[N];
		res[0] = start; visited[start] = true;
		int prev = start;
		for(int i=1;i<N;i++) {
			int next = -1;
			double min = Integer.MAX_VALUE;
			for(int j=0;j<N;j++) {
				double tempDist = getDistance(prev,j);
				if(!visited[j] && tempDist <= min) {
					min=tempDist;
					next = j;
				}
			}
			visited[next] = true;
			res[i] = next;
			prev = next;
		}
		res[N] = start;
		return res;
	}

	/**
	 * Improves the given route using 2-opt exchange.
	 *
	 * Implementation note: Repeat the procedure until the route is not
	 * improved in the next iteration anymore.
	 *
	 * @param route Original route
	 * @return Improved route using 2-opt exchange
	 */
	private int[] twoOptExchange(int[] route) {
		boolean improvement = true;
		int validNodes = route.length - 2;
		while(improvement) {
			improvement = false;
			double bestDistance = calculateDistanceTravelled(route);
			for(int i=1;i<validNodes-1;i++) {
				for(int k=i+1;k<validNodes;k++) {
					int[] newRoute = twoOptSwap(route, i, k);
					double newDistance = calculateDistanceTravelled(route);
					if(newDistance < bestDistance) {
						route = newRoute;
						bestDistance = newDistance;
						improvement = true;
					}
				}
			}
		}
		return route;
	}

	/**
	 * Swaps the nodes i and k of the tour and adjusts the tour accordingly.
	 *
	 * Implementation note: Consider the new order of some nodes due to the
	 * swap!
	 *
	 * @param route Original tour
	 * @param i Name of the first node
	 * @param k Name of the second node
	 * @return The newly adjusted tour
	 */
	public int[] twoOptSwap(int[] route, int i, int k) {
		int size = route.length; int[] newTour = new int[size];
		for(int p = 0; p < size;p++) {
			if(p < i || p > k) newTour[p] = route[p];
			else newTour[p] = route[k-(p-i)];
		}
		return newTour;
	}

	/**
	 * Returns the total distance of the given tour i.e. the sum of distances
	 * of the given path add the distance between the final and initial node.
	 *
	 * @param tour List of nodes in the given order
	 * @return Travelled distance of the tour
	 */
	public double calculateDistanceTravelled(int[] tour){
		double distanceTurn = 0; int size = tour.length;
		for(int i=0;i<size;i++) distanceTurn = distanceTurn + getDistance(tour[i],tour[(i+1)%size]);
		return distanceTurn;
	}

}