package pl.smashed.berlin;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Scanner;

import org.apache.commons.codec.binary.StringUtils;
import org.apache.poi.hssf.usermodel.HSSFCell;
import org.apache.poi.hssf.usermodel.HSSFRow;
import org.apache.poi.hssf.usermodel.HSSFSheet;
import org.apache.poi.hssf.usermodel.HSSFWorkbook;

import com.csvreader.CsvWriter;

import java.util.Collections;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	private static final int NUMBER_OF_ITERATIONS = 400000;
	private static final int NUMBER_OF_TOURISTS = 40;

	public static void main(String[] args) throws Exception {
		/*
		 * ArrayList<Main> obiektyArr = new ArrayList<Main>(); Main obiekt = new
		 * Main();
		 */

		/*
		 * for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) { obiektyArr.add(new
		 * Main()); }
		 */

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

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

		for (int j = 0; j < tourist.length; j++) {
			System.arraycopy(tourist[j], 0, touristTMP[j], 0, touristTMP[j].length);
		}

		int tmpOcena = Integer.MAX_VALUE;

		// DUZA
		// PETLA------------------------------------------------------------------
		for (int k = 1; k < NUMBER_OF_ITERATIONS; k++) {
			int[] indeksySelekcja = new int[NUMBER_OF_TOURISTS];
			/*
			  if(k<((3*NUMBER_OF_ITERATIONS)/4)){

			  indeksySelekcja = selekcjaTurniej(ocena); } else {
			 */

			if(k%20000<10000){
				System.out.println("Turniej");
				indeksySelekcja = selekcjaTurniej(ocena);

            } else {
            	System.out.println("Ruletka");
            	indeksySelekcja = ruletka(ocena);

            }


			/*System.out.println("\nRul: ");
			for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {
				System.out.printf("%5d ", indeksySelekcja[j]);
			}*/
			// }

			touristChild = crossOver(indeksySelekcja, touristTMP, rowSize);

			System.arraycopy(touristChild, 0, touristTMP, 0, touristTMP.length);

			touristMutted = mutacja(indeksySelekcja, touristTMP);
			// indeksySelekcja = null;

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

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

			}

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

			System.arraycopy(touristMutted, 0, touristTMP, 0, touristTMP.length);

			System.out.println("Iteracja: " + (k + 1) + " -> Najkrótsza trasa: " + tmpOcena + "\n\n");

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

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

	public static int getMax(int[] inputArray) {
		int maxValue = inputArray[0];
		for (int i = 1; i < inputArray.length; i++) {
			if (inputArray[i] > maxValue) {
				maxValue = inputArray[i];
			}
		}
		return maxValue;
	}

	// 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 //120 7615

		int[] indeksyTurniej = new int[NUMBER_OF_TOURISTS];
		for (int j = 0; j < NUMBER_OF_TOURISTS; j++) {

			int ocenaMin = Integer.MAX_VALUE;
			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;
		}
		int[] indTur = new int[indeksyTurniej.length];
		System.arraycopy(indeksyTurniej, 0, indTur, 0, indeksyTurniej.length);

		return indTur;

	}

	// ----------------------Koło ruletki----------------------

	/*
	 * private static int[][] ruletka(int[] ocena, int[][] tourist, int[][]
	 * touristChild) {
	 *
	 * int sumaPrawd = 0; for (int i = 0; i < ocena.length; i++) { sumaPrawd +=
	 * ocena[i]; }
	 *
	 * Random r = new Random(); for (int i = 0; i < touristChild.length; i++) {
	 * int numberRand = r.nextInt(sumaPrawd); int suma = 0; int j; for (j = 0; j
	 * < tourist.length && suma < numberRand; j++) { suma += ocena[j]; } //
	 * arraycopy(Object src, int srcPos, Object dest, int destPos, int //
	 * length)
	 *
	 * System.out.println("tourist[j]"+tourist[j].length);
	 * System.out.println("tourustChild[j]"+touristChild[j].length);
	 * System.out.println("tourist[j]"+tourist[j].length);
	 *
	 * System.arraycopy(tourist[j], 0, touristChild[j], 0, tourist[j].length);
	 * // bo // lecimy // po // wierszach
	 *
	 * // int [][] array = (int[][]) Arrays.stream(tourist).toArray();
	 * //touristChild = tourist.clone();
	 *
	 * }
	 *
	 * return touristChild; }
	 */

	private static int[] ruletka(int distance[]) {


        int max = getMax(distance);
        int[] tmpDistance = new int[NUMBER_OF_TOURISTS];
        for (int i = 0; i < distance.length; i++) {
            tmpDistance[i] = max + 1 - distance[i];
        }


        int propabilitySum = 0;
        for (int i = 0; i < tmpDistance.length; i++) {
            propabilitySum += tmpDistance[i];
        }

        int[] rouletteIndexes = new int[NUMBER_OF_TOURISTS];
        Random r = new Random();

        for (int i = 0; i < NUMBER_OF_TOURISTS; i++) {
            int numberRand = r.nextInt(propabilitySum);
            int j = 0;

            while (numberRand > 0) {
                numberRand = numberRand - tmpDistance[j];
                j++;
            }
            if(j>0){
            j=j-1;
            }
            rouletteIndexes[i] = j;
        }

        return rouletteIndexes;
    }

	/*
	 * arr = [150, 200, 250, 400], s = 1000 prob = [15%, 20%, 25%, 40%]
	 *
	 * max = weź największy z arr (400) for i < arr.length; i++ { arr[i] = max +
	 * 1 - arr[i]; } // max + 1 żeby nigdy nie wyszło 0
	 *
	 * arr = [251, 201, 151, 1] s = 604 prob = [42%, 33%, 25%, <1%]
	 */
	/*
	 * private static int[] ruletka(int ocena[]) {
	 *
	 * int sumaPrawd = 0; for (int i = 0; i < ocena.length; i++) { sumaPrawd +=
	 * ocena[i]; }
	 *
	 * int[] indeksyRul = new int[NUMBER_OF_TOURISTS]; Random r = new Random();
	 *
	 * for (int i = 0; i < NUMBER_OF_TOURISTS; i++) { int numberRand =
	 * r.nextInt(sumaPrawd); int j = 0;
	 *
	 * while (numberRand > 0) { numberRand = numberRand - ocena[j]; j++; }
	 *
	 * if (j > 0) { j = j - 1; }
	 *
	 * indeksyRul[i] = j; }
	 *
	 * return indeksyRul; }
	 */

	// ----------------------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[][] tourist, int rowSize) {
		int[][] touristChild = new int[NUMBER_OF_TOURISTS][rowSize];
		int szansaKrzyzowania = 700;
		Random rand = new Random();

		for (int i = 0; i < indeksySelekcja.length; i += 2) {
			if (rand.nextInt(1000) < szansaKrzyzowania) {

				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++) {
					/*System.out.println("\ni ->"+i);
					System.out.println("j ->"+j);
					System.out.println("p1 ->"+p1);
					System.out.println("p2 ->"+p2);*/

					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;
				}
			} else {
				for (int j = 0; j < tourist[i].length; j++) {

					touristChild[i][j] = tourist[i][j];
					touristChild[i + 1][j] = tourist[i + 1][j];

				}
			}
		}

		return touristChild;
	}

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

		for (int i = 0; i < indeksySelekcja.length; i++) {
			if (rand.nextInt(1000) < szansaMutacji) {
				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++;
				}
			}
		}

		return touristChild;

	}

	/*
	 * private static String saveToExcel(int numberOfIterations, int
	 * iterationRow, int rowNumber, ArrayList<Integer> cellValue, String
	 * fileName) throws IOException {
	 *
	 * HSSFWorkbook wb = new HSSFWorkbook(); HSSFSheet sheet = wb.createSheet(
	 * "new sheet");
	 *
	 *
	 *
	 *
	 * for (int i = 0; i < numberOfIterations; i++) { HSSFRow row =
	 * sheet.createRow(i);
	 *
	 *
	 * HSSFCell cell = row.createCell(iterationRow); cell.setCellValue(i+1);
	 * //numer iteracji
	 *
	 * HSSFCell cell2 = row.createCell(rowNumber);
	 * cell2.setCellValue(cellValue.get(i)); }
	 *
	 * // Write the output to a file FileOutputStream fileOut = new
	 * FileOutputStream(fileName); wb.write(fileOut); fileOut.close();
	 *
	 * wb.close();
	 *
	 * return "Excel created"; }
	 */

	/*
	 * private static String saveToExcel(int numberOfIterations, int
	 * iterationRow, int rowNumber, ArrayList<Integer> cellValue) {
	 * //this.iloscIteracji = numberOfIterations;
	 *
	 * try { FileOutputStream fileOut = new FileOutputStream("wynik.xls");
	 * HSSFWorkbook workbook = new HSSFWorkbook(); HSSFSheet worksheet =
	 * workbook.createSheet("POI Worksheet");
	 *
	 * // index from 0,0... cell A1 is cell(0,0)
	 *
	 * for (int i = 0; i < numberOfIterations; i++) {
	 *
	 * HSSFRow row1 = worksheet.createRow(i); HSSFRow row2 =
	 * worksheet.createRow(i); // ile wierszy
	 *
	 * HSSFCell cellA1 = row1.createCell(iterationRow); HSSFCell cellA2 =
	 * row2.createCell(rowNumber);
	 *
	 * cellA1.setCellValue(i+1); //nr iteracji w wierszu
	 * cellA2.setCellValue(cellValue.get(i)); // wartosc
	 *
	 * //HSSFCellStyle cellStyle = workbook.createCellStyle();
	 *
	 * }
	 *
	 * workbook.write(fileOut); fileOut.flush(); fileOut.close(); } catch
	 * (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e)
	 * { e.printStackTrace(); }
	 *
	 * return "Excel Created";
	 *
	 * }
	 */

	private static void saveToExcel(String[] val, String outputFile) {

		try {

			CsvWriter csvOutput = new CsvWriter(outputFile);

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

				// write out a few records
				csvOutput.write(val[i]);
				// csvOutput.write("sdsds");
				csvOutput.endRecord();
			}

			csvOutput.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}