package pl.smashed.berlin;

import java.io.File;
import java.util.Scanner;

import javax.swing.plaf.metal.MetalIconFactory.FolderIcon16;

import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

public class Main {

	private static final int NUMBER_OF_ITERATIONS = 200000;
	private static final int NUMBER_OF_TOURISTS = 20;

	public static void main(String[] args) throws Exception {

		String fileName = "att48.txt";
		String logRecord;
		File dataFile = new File(fileName);
		String[] splitLine = null;
		Scanner scanner = new Scanner(dataFile);
		int rowSize = Integer.valueOf(scanner.nextLine());			// pierwsza linia wczytanego dokumentu (ilosc wierszy w pliku)
		int[][] tab = new int[rowSize][rowSize];
		int[][] tourist = new int[NUMBER_OF_TOURISTS][rowSize];
		int[] ocena = new int[NUMBER_OF_TOURISTS];

		shuffleArrayList(rowSize, tourist);

		int i = 0;
		while (scanner.hasNextLine()) {
			logRecord = scanner.nextLine();
			splitLine = logRecord.split("\\s");

			for (int j = 0; j < splitLine.length; j++) {
				if (!"0".equals(splitLine[j])) {
					tab[i][j] = Integer.valueOf(splitLine[j]);
					tab[j][i] = Integer.valueOf(splitLine[j]);
				}
			}
			i++;
		}
//---------------------------------------------------------------------------------------------------------------------------------------
		for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
			System.out.printf("Wiersz %2d. ", d+1);			// numerowanie wierszy
				for (int j = 0; j < rowSize; j++) {
					System.out.printf("%5d", tourist[d][j]);		// wypisanie pojedynczego miasta (dlugosci)???
				}
					ocena[d] = countDistance(tab, tourist[d]);
					System.out.printf(" :: %s  ", ocena[d]);
					System.out.println();
		}
		System.out.println("\nOceny: ");
		for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
			System.out.printf("%5d ", ocena[j]);
		}
		System.out.println("\n");
		System.out.println("Najkrótsza trasa: " + getMin(ocena) + "\n\n");
		// System.out.println("Najlepsza trasa: "+selekcjaTurniej(ocena));
	//----------------------------------------------------------------------------------------------------------
	//	----------------------------------------------------------------------------------------------------------
		//int minVal = 99999;
		//for (int j = 0; j < NUMBER_OF_ITERATIONS; j++) {


		int[][] touristTMP = tourist;
		 int tmpOcena = Integer.MAX_VALUE;

		for (int k = 0; k < NUMBER_OF_ITERATIONS; k++) {

		int[] indeksySelekcja = selekcjaTurniej(ocena);					//indekx najmniejszego elementu z ocena[]



		int[][] touristChild = new int[NUMBER_OF_TOURISTS][rowSize];

		touristChild = crossOver(indeksySelekcja, touristChild, touristTMP);	/// mamy pokrzyzowana populacje (wynik tablica[][])


		touristChild = mutacja(indeksySelekcja, touristChild);



		for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {

					ocena[d] = countDistance(tab, touristChild[d]);

		}



		if(getMin(ocena) < tmpOcena) {
		tmpOcena = getMin(ocena);
		}

		touristTMP = touristChild;

		}
		System.out.println("--------------------------------------------");
		System.out.println("Najkrótsza trasa: " + tmpOcena + "\n\n");

		/*

			int[][]  krzyzowanieArr = crossOver(indeksySelekcja, touristChild, tourist);
			// --------------------------------------------------------------------

			int[] ocena2 = new int[NUMBER_OF_TOURISTS];

			//printMultiArr(crossOverArr);		// wyswietla tablice

			for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
				System.out.printf("Wiersz %2d. ", d+1);			// numerowanie wierszy
					for (int j = 0; j < rowSize; j++) {
						System.out.printf("%5d", krzyzowanieArr[d][j]);		// wypisanie pojedynczego miasta (dlugosci)???
					}
						ocena[d] = countDistance(tab, krzyzowanieArr[d]);
						System.out.printf(" :: %s  ", ocena2[d]);
						System.out.println();
			}
			System.out.println("\nOceny: ");
			for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
				System.out.printf("%5d ", ocena2[j]);
			}
			System.out.println("\n");
			System.out.println("Najkrótsza trasa: " + getMin(ocena2) + "\n\n");
			// System.out.println("Najlepsza trasa: "+selekcjaTurniej(ocena));

			System.out.println();
			System.out.println("-----------------------------------------------------");
			System.out.println();*/

			//----------------------------------------------------------------------------------------------------------
			//----------------------------------------------------------------------------------------------------------


			//int[][] crossOverArr = crossOver(indeksySelekcja, touristChild, tourist);


		/*
			System.out.println("\nOceny: ");
			for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
				System.out.printf("%5d ", indeksySelekcja[j]);
			}
			System.out.println("\n");
			System.out.println("Najkrótsza trasa: " + getMin(indeksySelekcja) + "\n\n");
			}*/

	}






//	}
			// --------------------------------------------------------------------
		//	int mutedArr[][] = mutacja(indeksySelekcja, touristChild, touristChild, rowSize);

	/*
			for (int[] val : touristChild) {
				for (int v : val) {
					System.out.print(v + " ");

				}
				System.out.println();
			}

			// --------------------------------------------
			for (int d = 0; d < NUMBER_OF_TOURISTS; d++) {
				System.out.printf("%2d. ", d);
				for (int j = 0; j < rowSize; j++) {
					System.out.printf("%5d", mutedArr[d][j]);
				}
				ocena[d] = countDistance(tab, mutedArr[d]);
				System.out.printf(" :: %s  ", ocena[d]);
				System.out.println();
			}
			System.out.println("\nOcena: ");
			for (int j = 0; j < 20; j++) {
				System.out.printf("%5d ", ocena[j]);
			}

			System.out.println("\n");

			// minVal = getMin(ocena);

			if (getMin(ocena) < minVal) {
				minVal = getMin(ocena);

			}
			System.out.println(getMin(ocena));
	//	}
		System.out.println("Najmniejsza ocena: " + minVal);*/
	//}



	// --------------------------METODY----------------------------------------

	private static void printMultiArr(int[][] crossOverArr) {
		for (int[] val : crossOverArr) {
			for (int v : val) {
				System.out.print(v + " ");

			}
			System.out.println();
		}
	}

	// Mieszanie wartości w tablicy
	private static void shuffleArrayList(int rowSize, int[][] tourist) {
		for (int i = 0; i < tourist.length; i++) {

			ArrayList<Integer> numbers = new ArrayList<>();
			for (int q = 0; q < rowSize; q++) {
				numbers.add(q + 1);
			}
			Collections.shuffle(numbers);
			for (int j = 0; j < rowSize; j++) {
				tourist[i][j] = numbers.get(j);
			}
		}
	}

			//Znajdź min z tablicy[]
	public static int getMin(int[] inputArray) {
		int minValue = inputArray[0];
		for (int i = 1; i < inputArray.length; i++) {
			if (inputArray[i] < minValue) {
				minValue = inputArray[i];
			}
		}
		return minValue;
	}

			// Licz distans
	private static int countDistance(int[][] tab, int[] user) {
		int trasa = 0;
		int a, b;
		for (int i = 0; i < user.length; i++) {
			a = user[i];
			if (i == (user.length - 1)) {
				b = user[0];
			} else {
				b = user[i + 1];
			}
			trasa += tab[a - 1][b - 1];
		}
		return trasa;
	}

	private static int[] selekcjaTurniej(int ocena[]) {
		Random r = new Random();
		int k = 2;		// skacz co dwie oceny

		int[] indeksyTurniej = new int[NUMBER_OF_TOURISTS];
		for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
			int ocenaMin = Integer.MAX_VALUE;			//największa możliwa wartość, zamiast tego 9999
			int indexMin = -1;							// -1 b ona pewno go nie ma, deklaracja
			for (int i = 0; i < k; i++) {
				int randIndeks = r.nextInt(NUMBER_OF_TOURISTS);
				if (ocena[randIndeks] < ocenaMin) {
					indexMin = randIndeks;
					ocenaMin = ocena[randIndeks];
				}
			}
			indeksyTurniej[j] = indexMin;
		}

		return indeksyTurniej;

	}

	// ----------------------Krzyżowanie----------------------

			// Porównanie indeksów ????????????
	private static int indeksOf(int[] tab, int el) {
		for (int i = 0; i < tab.length; i++) {
			if (tab[i] == el)
				return i;
		}
		return -1;
	}

	// Krzyzowanie
	private static int[][] crossOver(int[] indeksySelekcja, int[][] touristChild, int[][] tourist) {

		for (int i = 0; i < indeksySelekcja.length; i += 2) {
			int p1 = indeksySelekcja[i];
			int p2 = indeksySelekcja[i + 1];
			Random r = new Random();
			int cross1 = r.nextInt(tourist[0].length - 3) + 1;
			int cross2 = r.nextInt(tourist[0].length - 1 - cross1) + cross1 + 1;

			// zamiana środka
			for (int j = cross1; j <= cross2; j++) {
				touristChild[i][j] = tourist[p1][j];
				touristChild[i + 1][j] = tourist[p2][j];
			}

			// krzyżowanie PMX
			for (int j = 0; j < cross1; j++) {
				int city1 = tourist[p2][j];
				int ind;
				// zamiana nieistniejących środka
				while ((ind = indeksOf(touristChild[i], city1)) != -1) {
					city1 = tourist[p2][ind];
				}
				touristChild[i][j] = city1;
			}

			for (int j = cross2 + 1; j < tourist[0].length; j++) {
				int city1 = tourist[p2][j];
				int ind;

				// zamiana nieistniejących środka
				while ((ind = indeksOf(touristChild[i], city1)) != -1) {
					city1 = tourist[p2][ind];
				}
				touristChild[i][j] = city1;
			}

			for (int j = 0; j < cross1; j++) {
				int city1 = tourist[p1][j];
				int ind;
				// zamiana nieistniejących środka
				while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
					city1 = tourist[p1][ind];
				}
				touristChild[i + 1][j] = city1;
			}

			for (int j = cross2 + 1; j < tourist[0].length; j++) {
				int city1 = tourist[p1][j];
				int ind;
				// zamiana nieistniejących środka
				while ((ind = indeksOf(touristChild[i + 1], city1)) != -1) {
					city1 = tourist[p1][ind];
				}
				touristChild[i + 1][j] = city1;
			}
		}

		return touristChild;
	}

	// Mutacja
	private static int[][] mutacja(int[] indeksySelekcja, int[][] touristChild) {
		// losowanie przeciec
		int cross1 = 0;
		int cross2 = 0;

		for (int i = 0; i < indeksySelekcja.length; i++) {

			Random r = new Random();

			cross1 = r.nextInt(touristChild[0].length - 3) + 1;
			cross2 = r.nextInt(touristChild[0].length - 1 - cross1) + cross1 + 1;

			ArrayList<Integer> touristChildTmpSrodek = new ArrayList<>();

			// przypisujemy srodek z touristCHild
			for (int j = cross1; j <= cross2; j++) {
				touristChildTmpSrodek.add(touristChild[i][j]);
			}

			Collections.reverse(touristChildTmpSrodek);


			int tmpIndex = 0;
			for (int j = cross1; j <= cross2; j++) {

				touristChild[i][j] = touristChildTmpSrodek.get(tmpIndex);
				tmpIndex++;


			/*	 System.out.print("cross1 = "+cross1);

				 System.out.print("cross2 = "+cross2); System.out.println();*/

			}

		}

		return touristChild;

	}

}