//--------------------------StartTS------------------------------------------

import java.io.*;

public class StartTS {

	public static void main(String[] args) 
    {
		int generation = 0;
        int mittel = 0;
        try {PrintWriter daten = new PrintWriter("recomb+greedy.dat");
        
        HauptTS ts = new HauptTS();
        ts.make_map();
        ts.how_long();
		for (ts.pc = (float) 0.9 ; ts.pc <= 0.95 ; ts.pc = (float) (ts.pc + 0.05))
        {
            for (ts.pm = (float) 0.2; ts.pm <= 0.25 ; ts.pm = (float) (ts.pm + 0.005))
            {
                for (int i = 0; i < 100; i++)
                {                
                    ts.make_genom();
                    while(ts.fett == false && generation < 1000)
                    {
                        ts.fitness();
                        ts.fitsort();
                        // CROSSOVER
                        ts.greedy();
                        ts.partial();
                        ts.fitness();
                        ts.fitsort();
                        // MUTATION
                        ts.mutate();
                        ts.fitness();
                        ts.fitsort();
                        // REPLICATION
                        //ts.replic_sh();
                        generation++;
                        //System.out.println("Fitness: " + ts.bestfit(1000000000));
                    }
                    mittel += generation;
                    System.out.println(">"+ ts.pc + " " + ts.pm + " " + generation);
                    generation = 0;
                    ts.fett = false;
               }
               mittel = mittel/100;
               System.out.println(">>>"+ts.pc + " " + ts.pm + " " + mittel);
               daten.println(ts.pc + " " + ts.pm + " " + mittel);
               mittel = 0;
            }
        }
        daten.close();
        } 
        catch (FileNotFoundException e) 
        {
                e.printStackTrace();
        }
    }
}

//-----------------------------------HauptTS-----------------------------------

import java.util.*;
import java.math.*;

public class HauptTS {
	
	//ARRAYS
	String[] auswahl;
	String[] repvalue = new String[2];
	double[] fit;
	int[][] karte;
	int[] baukarte; // Hilfsarray
	int[][] gene;
	int[][] hf;
	int[][] children;
	HashMap<String,Double> distance = new HashMap<String,Double> ();
	
	//VARIABELN
	boolean fett = false,protect_best = false;
	float pc = (float) 0.1, pm = (float) 0.2, replication_scheme = 0;
	int repanz = 10, repproz = 10, gridsize = 10, genelen = 36, genecnt = 100; // ACHTUNG VORBELEGT
	double max = genelen*genelen;
	
//Funktion für die Parameterübergabe
	public void uebergabe(String[] args, float upc, float upm) {

		for (int i = 0; i < args.length; i++) {
			auswahl = args[i].split("=");
			pc = upc;
			pm = upm;
/*			if (args[i].startsWith("genecnt")) {
				genecnt = Integer.parseInt(auswahl[1]);
			}

			if (args[i].startsWith("genelen")) {
				genelen = Integer.parseInt(auswahl[1]);
				max = genelen*genelen;
			}

			if (args[i].startsWith("replication_scheme")) {
				repvalue = auswahl[1].split("x");
				repanz = Integer.parseInt(repvalue[0]);
				repproz = Integer.parseInt(repvalue[1]);
			}

			if (args[i].startsWith("max_generations")) {
				max_generations = Float.parseFloat(auswahl[1]);
			}
			// Werte 1 für ja, 0 für nein
			if (args[i].startsWith("protect_best")) 
			{
				if (auswahl[1].equals("1")) {
					protect_best = true;
					//System.out.println("PROTECT BEST!!!");
			} 
			else 
			{
				protect_best = false;
			}
		}*/
	}
}
//Allgemeine Zufallsfunktion
	public int zufall(int z) {
		int rw = 0;
		Random rd = new Random(System.nanoTime());
		rw = Math.abs(rd.nextInt(z));
		return rw;
	}
	
//Erstellen der Karte Größe nach GridSize
	public void make_map() {
	 int zu = 0, co = 0;
	 karte = new int[gridsize][gridsize];
	 baukarte = new int[genelen];
	 //	Da auch 0 - mit Dummi füllen
	 for(int i = 0; i < genelen; i++){baukarte[i] = genelen*2;}
	 for(int i = 0; i < genelen; i++)
	 {	
		 zu = zufall(genelen);
		 if(baukarte[zu] == genelen*2)
		 {
			 baukarte[zu] = i; // Hilfsarray füllen
		 }
		 else{i--;}
	 }
	 //Füllen der Karte mit den Werten
	 for(int z = 0;z < (gridsize);z++)
	 {
		 for(int sp = 0;sp < (gridsize);sp++)
		 {
			 if(z == 0){karte[z][sp]= baukarte[co]; co++;}
			 else if(z == (gridsize-1)){karte[z][sp] = baukarte[co]; co++;}
			 else if(sp == (gridsize)-1 && z != 0 && z != (gridsize)-1)
			 {
				 karte[z][sp] = baukarte[co]; co++;
			 }
			 else if(sp == 0 && z != 0 && z != (gridsize)-1)
			 {
				 karte[z][sp] = baukarte[co]; co++;
			 }
			 else{karte[z][sp] = genelen*2;} // Dummi
		 }	 
	 }
	 
}
	
//Berechnen der Entfernungskarte und Erstellen einer HashMap
	public void how_long()
	{
		int dist1 = 0;
		int dist2 = 0;
		double pyt = 0;
		for(int i = 0;i < gridsize;i++) // Zeilen durchlaufen
		{
			for(int j = 0;j < gridsize;j++) //Spalten durchlaufen
			{
				if(karte[i][j] != genelen*2) // Nicht die Felder in der Mitte
				{
					for(int i2 = 0;i2 < gridsize;i2++) // Zeilen durchlaufen
					{
						for(int j2 = 0;j2 < gridsize;j2++) //Spalten durchlaufen
						{
					       if(karte[i2][j2] != genelen*2)
					       {
					    	   if(i > i2){dist1 = i - i2;}
					    	   else{dist1 = i2 - i;}
					    	   if(j > j2){dist2 = (j - j2);}
					    	   else{dist2 = (j2 - j);}
					    	   pyt = (dist1*dist1) + (dist2*dist2);
                               pyt = Math.sqrt(pyt);
                               // Hashtabel füllen
					    	   distance.put(karte[i][j]+"_"+karte[i2][j2],pyt);
					    	   //PRÜFAUSGABE
					    	   //System.out.println(i+","+j+" nach "+i2+","+j2+": "+pyt);           
					       }
						}
					}
				}
			}
		}
	}
	
//Erstellen der Gene
	public void make_genom() {
		int zu = 0;
		gene = new int[genecnt][genelen]; // Initilisierung gene
		for (int i = 0; i < genecnt; i++) // Gene durchlaufen
		{
			for(int x = 0; x < genelen; x++){gene[i][x] = genelen*2;} // Leerfeld füllen
			for (int j = 0; j < genelen; j++) // Länge durchgehen
			{
					 zu = zufall(genelen);
					 if(gene[i][zu] == genelen*2) // Nur wenn ein leeres Feld
					 {
						 gene[i][zu] = j;
					 }
					 else{j--;}
			} 
		}
	}

// Greedy Crossingover
	public void greedy() 
	{
		int elter1, elter2, checker, pos1, pos2;
        double edis1, edis2;
		children = new int[genecnt][genelen];
	// Schleife so oft wie Kinder durch Crossingover gebildet werden
		for(int ge = 0; ge < (int)(genecnt*pc); ge++)
		{
			elter1 = zufall(genecnt); elter2 = zufall(genecnt);
            for(int b = 0; b < genelen; b++){children[ge][b] = genelen*genelen;}
			for(int p = 0; p < genelen; p++) // Positionen im Kind
			{
               // für den ersten Durchlauf Elter1 an Position 1
				if(p == 0){children[ge][0] = gene[elter1][0];                    }
                    // get_pos liefert hierbei die Position der Stadt in dem jeweiligen Elter
                    pos1 = get_pos(gene[elter1],children[ge][p])+1;
                    pos2 = get_pos(gene[elter2],children[ge][p])+1;
                    // prüfen ob die nächste Position in Elter1 oder Elter2 schon da ist usw.
                    checker = check(children[ge],gene[elter1][pos1],gene[elter2][pos2]);
                    // Ergebnis aus check überprüfen
                        if(checker == 3) //Entscheidung nach Entfernung
                        {
                            edis1 = distance.get(children[ge][p]+"_"+gene[elter1][pos1]);
                            edis2 = distance.get(children[ge][p]+"_"+gene[elter2][pos2]);
                            if(edis1 < edis2){children[ge][p+1] = gene[elter1][pos1];}
                            else{children[ge][p+1] = gene[elter2][pos2];}
                        }
                        else if(checker == 1) // Wert in Elter1 noch frei
                        {
                            children[ge][p+1] = gene[elter1][pos1];
                        }
                        else if(checker == 2) // Wert in Elter2 noch frei
                        {
                            children[ge][p+1] = gene[elter2][pos2];
                        }
                        else if(checker == 0) // Beide Werte schon vergeben
                        {
                            int erg, zuf;
                            // Suchen der nächsten noch nicht verwendeten Stadt
                                for(int i = 0; i < genelen*genelen; i++)
                                {
                                    zuf = zufall(genelen);
                                    erg =  get_pos(children[ge],zuf);
                                    if(erg == -2)
                                    {
                                        children[ge][p+1] = zuf;
                                        break;
                                    }
                                }
                         }
			    }
        }
        
	//Restliche Plätze mit den Besten füllen Start bei genecnt*pc
		int start = (int) (genecnt*pc);
		for(int ch = start; ch < genecnt; ch++) 
		{
			for(int p = 0; p < genelen; p++) // Positionen
			{
				children[ch][p] = gene[ch-start][p];
			}
		}
		// Umkopieren von Children in Gene
		for(int i = 0; i < genecnt; i++) 
		{
			for(int j = 0; j < genelen; j++)
			{
				gene[i][j] = children[i][j];
			}
		}
	}
	
//Prüft Städte auf Vorhandensein usw.
	public int check(int[] ch, int e1, int e2)
	{
        // Wenn e1 und e2 nicht vorhanden sind: 3
        if(get_pos(ch,e1) ==  -2 && get_pos(ch,e2) ==  -2){return 3;}
        // Wenn e1 nicht vorhanden ist: 1
        else if(get_pos(ch,e1) ==  -2 && get_pos(ch,e2) > -2){return 1;}
        // Wenn e2 nicht vorhanden ist: 2
        else if(get_pos(ch,e2) ==  -2 && get_pos(ch,e1) > -2){return 2;}
        // Wenn beide Städte vorhanden sind: 0
        else{return 0;}
	}
    
//Gibt die Position einer Stadt in einem Gen zurück oder -2 wenn nicht da
    public int get_pos(int[] gen,int city)
    {
        int pos = 0;
        for(int item: gen)
        {
           if(item == city)
           {
              if(pos == genelen-1){return -1;}
              else{return pos;}
           }
           pos++;
        }
        return -2;
    }
   
// Partially Crossingover
	public void partial() 
	{
        int elter1, elter2, pos1, pos2, bstart, bende = 0,kopie;
        children = new int[genecnt][genelen];
    // Schleife so oft wie Kinder durch Crossingover gebildet werden sollen
        for(int ge = 0; ge < (int)(genecnt*pc); ge = ge + 2)
        {
            elter1 = zufall(genecnt); elter2 = zufall(genecnt);
            bstart = zufall(genelen); 
            while(bende > bstart + 1){bende = zufall(genelen);}
            // Eltern in Kinder übertragen komplett
            for(int b = 0; b < genelen; b++)
            {
                children[ge][b] = gene[elter1][b];
                children[ge+1][b] = gene[elter2][b];
            }
            // Positionen in den Kindern
            for(int p = bstart; p <= bende; p++) 
            {
               // Position in beiden Eltern im Bereich raussuchen, Pos der beiden Werte in beiden Eltern suchen und tauschen
                //1.Elternteil
                pos1 = get_pos(children[ge],children[ge][p]);
                pos2 = get_pos(children[ge],children[ge+1][p]);
                if(pos2 == -1){pos2 = genelen-1;}
                kopie = children[ge][pos1];
                children[ge][pos1] = children[ge][pos2];
                children[ge][pos2] = kopie;
                //2.Elterneteil
                pos1 = get_pos(children[ge + 1],children[ge + 1][p]);
                pos2 = get_pos(children[ge + 1],children[ge][p]);
                if(pos2 == -1){pos2 = genelen-1;}
                kopie = children[ge + 1][pos1];
                children[ge + 1][pos1] = children[ge + 1][pos2];
                children[ge + 1][pos2] = kopie;
            }
        }
        
    //Restliche Plätze mit den Besten füllen Start bei genecnt*pc
        int start = (int) (genecnt*pc);
        for(int ch = start; ch < genecnt; ch++) 
        {
            for(int p = 0; p < genelen; p++) // Positionen
            {
                children[ch][p] = gene[ch-start][p];
            }
        }
        // Umkopieren von Children in Gene
        for(int i = 0; i < genecnt; i++) 
        {
            for(int j = 0; j < genelen; j++)
            {
                gene[i][j] = children[i][j];
            }
        }		
	}
	
//Mutationfunktion: Tausch 2er Positionen (Städte)
	public void mutate() 
	{
		int zz = 0, zz2 = 0, zz3 = 0,zw = 0;
		for (int i = 1; i <= (genelen * genecnt * pm); i++) 
        {
			zz = zufall(genecnt);zz2 = zufall(genelen);zz3 = zufall(genelen);
			if (protect_best && zz == 0 && fit == null) {
				i--;
			} 
			else 
			{
				zw = gene[zz][zz2];
				gene[zz][zz2] = gene[zz][zz3];
				gene[zz][zz3] = zw;
			}
		}
	}
	
//Berechnen der Fitness nach Weg
	public void fitness() //Durchläuft alle Gene und speichert Fitness in Array
	{ 
		fit = new double[genecnt];
		double way = 0;
		for (int i = 0; i < genecnt; i++) //Gene
		{
			way = 0;
			for(int j = 0; j < genelen; j++) //Positionen
			{
				//Berechnung letzter Stelle umgehen
				if(j == genelen-1)
                {
                    way += distance.get(gene[i][j]+"_"+gene[i][0]);
                }
                else{way += distance.get(gene[i][j]+"_"+gene[i][j+1]);}
			}
			fit[i] = way;
			bestfit(fit[i]); // Merken der besten Fitness
			if (fit[i] <= genelen) //Beste Fitness erreicht
			{ 
				fett = true;
			}
		}
	}

//Sortieren nach Fitness
	public void fitsort() {
		hf = new int[genecnt][genelen];
		double max = 0;
		int ind = 0;
		for (int i = 0; i < genecnt; i++) //Gene
		{
			max = genelen*genelen;
			for (int i2 = 0; i2 < genecnt; i2++) //Gene
			{
				if (fit[i2] < max) // Das kleinste Gen suchen
				{
					max = fit[i2];
					ind = i2;
				}
			}
			// Umkopieren in Hilfsarray
			for(int p = 0;p < genelen;p++)
			{
			 	hf[i][p] = gene[ind][p];
			}
			//Damit das Gen aus der Fitnessberechnung raus ist
			fit[ind] = genelen*genelen*genelen;
		}
		//Umkopieren aus hf in Gene
		for (int q = 0; q < genecnt ; q++)
		{
			for (int u = 0; u < genelen; u++) 
			{
				gene[q][u] = hf[q][u];
			}
		}
	}

// Merken der besten Fitness
	public double bestfit(double fit) 
	{
		//Besser ist die kleinere Fitness!
		if (fit < max) 
		{
			max = fit;
		}
		return max;
	}

//Replication: nur 10x10 oder gar nich
	public void replic_sh() 
	{
		hf = new int[genecnt][genelen];
		//Kopieren in Hilfsarray
		for (int i = 0; i < genecnt; i++) 
		{
			for(int j = 0; j < genelen; j++)
			{
				hf[i][j] = gene[i][j];
			}
		}
		int u = 0, r = 0;
		//Prüfung ob auch 10 Gene vorhanden sind
		if (genecnt < repanz) 
		{
			System.out.println("Replikation nicht möglich!!! Genanzahl kleiner als Auswahlanzahl: "+repanz);
		}
		else 
		{
			for (int re = 0; re < repanz; re++) // So oft wie Replikation (z.B. 10)
			{
				for (int i = 0; i < (genecnt / repanz); i++) // Anzahl der Vermehrung (z.B. 10%) 
				{
					for (int j = 0; j < genelen; j++)
					{
						hf[i + u][j] = gene[re][j];
					}
				}
				// Damit der Abstand stimmt (z.B. 10% * 2)
				r++; 
				u = (genecnt / repanz) * r;
			}
			// Umkopieren vom Hilfsarray in Gene
			for (int i = 0; i < genecnt; i++) 
			{
				for (int j = 0; j < genelen; j++)
				{
					gene[i][j] = hf[i][j];
				}
			}
		}
	}
}