import java.util.ArrayList;
//import java.util.Arrays;


public class TSPtester {

	/**
	 * Code By Nicholas Kolegraff
	 */
	SriramCity city = new SriramCity();
	public TSPtester()
	{
		
	}
	public void TSP(ArrayList<Integer> partialTour, ArrayList<Integer> currentBestTour)
	{
		// base case: if discovered a tour better than currentBestTour
		if (tourDistance(partialTour) < tourDistance(currentBestTour))
			{
				partialTour = currentBestTour;
				System.out.println(partialTour);
				System.out.println(tourDistance(partialTour));
				return;
			}
		// base case: if partial tour is not worth completing
		if (tourDistance(partialTour) > tourDistance(currentBestTour))
		{
			partialTour.remove((partialTour.size() - 1));
			System.out.println(currentBestTour);
			System.out.println(tourDistance(currentBestTour));
			return;

		}

		// recursive case: if partialTour is not complete and is currently better than currentBestTour
		for (int i = 0; i < partialTour.size(); i++)
			{
			if(!partialTour.contains(city.getIndex(city.cityName[i], city.cityState[i])))
			{
				partialTour.add(city.getIndex(city.cityName[i], city.cityState[i]));
				TSP(partialTour, currentBestTour);
				partialTour.remove(partialTour.size() - 1);
			}
			}
		
	}
	public int getDistance(int i, int j)
	{
		int distance = 0;
		
		if (i < j)
			{
				distance = city.distances[j][i];
			}
		else
		{
			distance = city.distances[i][j];
		}
		return distance;
	}
	public int tourDistance(ArrayList<Integer> tour)
	{
		int tourDistance = 0;
		for (int i = 0; i < (tour.size()-1); i++)
			tourDistance += getDistance(tour.get(i), tour.get(i+1));
		return tourDistance;
			
	}
	public static void main(String[] args) 
	{
		TSPtester t = new TSPtester();
		SriramCity city = new SriramCity();
		ArrayList<Integer> R = new ArrayList<Integer>();
		ArrayList<Integer> T = new ArrayList<Integer>();
		for (int i = 0; i < 5; i++)
			T.add(city.getIndex(city.cityName[i], city.cityState[i]));
		R.add(city.getIndex(city.cityName[0], city.cityState[0]));
		t.TSP(R,T);
		
		

	}

}