package sokobanevo.evolution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import sokobanevo.pathfinding.Astar;

/**
 * Most important class of the project.
 * 
 * Contains all core functions and constants required for our Evolutionary Sokoban solving.
 * Constants's names are self-explanatory.
 * Individuals in population are represented in pairs of numbers: eg. 0214.. which means box 0 push to direction 2 (right), box 1 to position 4..
 * 
 * @author Payne
 */
public class EvolutionSokoSolver {
    
    static final int GENERATION_SIZE = 100;
    static final int MAX_INDIVIDUM_SIZE = 300;
    static final int MIN_INDIVIDUM_SIZE = 10;
    static final int THREADS_NUMBER = 4;
    static final int DISTANCE_FROM_GOAL_PENALTY = 50;
    static final int UNABLE_TO_PERFORM_MOVE_PENALY = 0;
    static final int STATIC_DEADLOCK_PENALTY = 5000;
    static final int FREEZE_DEADLOCK_PENALTY = 5000;
    static final int STEP_PENALTY = 1;
    static final int ELITARISM_COUNT = 5;
    static final int CROSSOVER_COUNT = 80;
    static final int MUTATION_COUNT = 20;
    static final int MUTATION_BITS = 10;
    
    /**
    * Function, creates next generations from already existing population.
    *  
    * On CROSSOVER_COUNT individuals is performed roulette crossover. 
    * ELITARISM_COUNT individuals is copied unchanged to next generation.
    * On max. MUTATION_COUNT individuals is performed which randomly changes max. MUTATION_BITS.
    * So next generations contains exactly GENERATION_SIZE individuals, the rest of individuals are fresh new.
    * 
    * @param baseMap contains the base (unchanged) map on which the Sokoban solving is performed.
    * @param generationFitnessArray every individual on position population[some_index] has its fitness stored here on position generationFitnessArray[some_index]
    * @param population contains population of individuals.
    * 
    * @return new population
    */
    public static ArrayList<char[]> createNextGeneration(ArrayList<char[]> population, int[] generationFitnessArray, ArrayList<char[]> baseMap){
        ArrayList<char[]> newGeneration = new ArrayList<char[]>();
        int n = generationFitnessArray.length;
        int[] indexes = new int[n];
              
        int i,j;
        for(i = 0; i < n; i++){
            indexes[i] = i;
        }
        
        //bubble sort, triedi aj indexy na zaklade zoradovania fitness, nech si zapamatame ktory fitness je pre ktoreho jedinca..
        for(int pass=1; pass < n; pass++) {  
            for(i=0; i < n-pass; i++) {
                if (generationFitnessArray[i] < generationFitnessArray[i+1]) {
                    int temp = generationFitnessArray[i];  generationFitnessArray[i] = generationFitnessArray[i+1];  generationFitnessArray[i+1] = temp;
                    temp = indexes[i];  indexes[i] = indexes[i+1];  indexes[i+1] = temp;
                }
            }
        }
        
        /*System.out.println("Najlepsi fitness: "+generationFitnessArray[0]+" pre index:"+indexes[0]);
        System.out.println("jedinec:");
        EvolutionSokoSolver.traceIndividum(population.get(indexes[0]));
        System.out.println();
        System.out.println("Najhorsi fitness: "+generationFitnessArray[99]+" pre index:"+indexes[99]);
        System.out.println("jedinec:");
        EvolutionSokoSolver.traceIndividum(population.get(indexes[99]));
        System.out.println();*/
        
        //Calculate number of boxes in map for mutation and creating new individum
        int numberOfBoxes = 0;
        for(i = 0; i < baseMap.size(); i++){
            for(j = 0; j < baseMap.get(i).length; j++){
                if(baseMap.get(i)[j] == '$'){
                    numberOfBoxes++;
                }
            }
        }
        
        //CROSSOVER
        EvolutionSokoSolver.doRoulleteCrossover(CROSSOVER_COUNT, population, generationFitnessArray, indexes, newGeneration);
        
        //APPLY MUTATIONS
        Random generator = new Random();
        int mutationIndex = 0;
        int bitIndex = 0;
        for(i = 0; i < MUTATION_COUNT; i++){
            mutationIndex = generator.nextInt(CROSSOVER_COUNT);
                for(j = 0; j < MUTATION_BITS; j++){
                    bitIndex = generator.nextInt(newGeneration.get(mutationIndex).length);
                    if(bitIndex % 2 == 0){
                        newGeneration.get(mutationIndex)[bitIndex] = (char)generator.nextInt(numberOfBoxes);
                    }else{
                        newGeneration.get(mutationIndex)[bitIndex] = (char)generator.nextInt(4);
                    }
                }
        }
        
        //TOP ELITARISM_COUNT INDIVIDUALS WILL SURVIVE TO NEXT GENERATION
        for(i = 0; i < ELITARISM_COUNT; i++){
            newGeneration.add(population.get(indexes[i]).clone());
        }
        
        //FILL UP GENERATION WITH SOME BRAND NEW INDIVIDUALS
        for(i = 0; i < GENERATION_SIZE - (CROSSOVER_COUNT + ELITARISM_COUNT); i++){
            newGeneration.add(EvolutionSokoSolver.createNewIndividum(numberOfBoxes, generator));
        }
        
        return newGeneration;
    }
    
    /**
    * Function, performs roullete crossover over population.
    *  
    * Based on known algorhitm. Individuals with better fitness have higher chance of making offspring.
    * Picks two individuals and calls function doCrossover on them, which creates new offspring from their representations.
    *
    * @param howMany indicates how many individuals are to be created using crossover.
    * @param newGeneration newly created individuals are stored here.
    */
    public static void doRoulleteCrossover(int howMany, ArrayList<char[]> population, int[] generationFitnessArray, int[] indexes, ArrayList<char[]> newGeneration){
        int n = population.size();
        double[] cumulativeFitnesses = new double[n];
        int i,j;
        Random generator = new Random();

        cumulativeFitnesses[0] = generationFitnessArray[0];
        for(i = 1; i < n; i++){
            cumulativeFitnesses[i] = cumulativeFitnesses[i - 1] + generationFitnessArray[i];
        }

        /*System.out.println();
        System.out.print("probs:");
        for(i = 0; i < n; i++){
            System.out.print(cumulativeFitnesses[i]+"|");
        }
        System.out.println();*/

        int selected1Index;
        int selected2Index;
        double random;
        for(j = 0; j < howMany; j++){

            selected1Index = -1;
            double randomFitness = generator.nextDouble() * cumulativeFitnesses[cumulativeFitnesses.length - 1];
            selected1Index = Arrays.binarySearch(cumulativeFitnesses, randomFitness);
            if (selected1Index < 0){
                selected1Index = Math.abs(selected1Index + 1);
            }
            if(selected1Index == -1) { selected1Index = n - 1; }

            randomFitness = generator.nextDouble() * cumulativeFitnesses[cumulativeFitnesses.length - 1];
            selected2Index = Arrays.binarySearch(cumulativeFitnesses, randomFitness);
            if (selected2Index < 0){
                selected2Index = Math.abs(selected2Index + 1);
            }
            if(selected2Index == -1) { selected2Index = n - 1; }

            //System.out.println("selected 1:" +selected1Index + ",Selected 2:"+selected2Index);

            newGeneration.add(EvolutionSokoSolver.doCrossover(population.get(indexes[selected1Index]), population.get(indexes[selected2Index])));
        }
    }
    
    /**
    * Function, performs crossover using two individuals.
    *  
    * Takes part of first individual randomly n characters from its head and part of second individual from its tail.
    * New offspring has length at least MIN_INDIVIDUM_SIZE, max MAX_INDIVIDUM_SIZE.
    * 
    * @return new offspring
    */
    public static char[] doCrossover(char[] individum1, char[] individum2){
        Random generator = new Random();
        char[] newIndividum;
        int firstPart;
        int secondPart;
        
        int i;
        
        firstPart = MIN_INDIVIDUM_SIZE/2 + generator.nextInt(individum1.length-MIN_INDIVIDUM_SIZE/2);
        secondPart = MIN_INDIVIDUM_SIZE/2 + generator.nextInt(individum2.length-MIN_INDIVIDUM_SIZE/2);
        if(firstPart % 2 != 0){
            firstPart -= 1;
        }
        if(secondPart % 2 != 0){
            firstPart -= 1;
        }
        if(secondPart + firstPart < MIN_INDIVIDUM_SIZE){
            secondPart = MIN_INDIVIDUM_SIZE - firstPart;
        }
        if(secondPart + firstPart > MAX_INDIVIDUM_SIZE){
            secondPart = MAX_INDIVIDUM_SIZE - firstPart;
        }
        
        int newIndividumLength = firstPart + secondPart;
        //System.out.println("Created cross length "+newIndividumLength+" fp>"+firstPart+"sp>"+secondPart);
        newIndividum = new char[newIndividumLength];
        for(i = 0; i < firstPart; i++){
            newIndividum[i] = individum1[i];
        }
        
        for(i = individum2.length - 1; i >= individum2.length - secondPart; i--){
            newIndividum[newIndividumLength - (individum2.length - i)] = individum2[i];
        }
        
        /*System.out.println();
        System.out.print("from1:");
        for(i = 0; i < population.get(indexOfIndex1).length; i++){
            System.out.print((int)population.get(indexOfIndex1)[i]);
        }
        System.out.println();
        System.out.print("from2:");
        for(i = 0; i < population.get(indexOfIndex2).length; i++){
            System.out.print((int)population.get(indexOfIndex2)[i]);
        }
        System.out.println();
        System.out.print("tostr:");
        for(i = 0; i < newIndividum.length; i++){
            System.out.print((int)newIndividum[i]);
        }*/
        
        //System.out.println("Vytvoril som potomska s dlzkou:"+newIndividum.length+",z prveho:"+firstPart+",z druheho:"+secondPart+".");
        
        return newIndividum;
    }
    
    /**
    * Function, calculates fitness of whole population.
    *  
    * Divides the work over THREADS_NUMBER threads.
    * 
    * @param deadlockMap map where static deadlocks are highlighted. We use it when computing fitness of every individual.
    * @return array where every individual has its fitness stored
    */
    public static int[] computeFitnessOfGeneration(ArrayList<char[]> population, ArrayList<char[]> baseMap, ArrayList<char[]> deadlockMap){
        int i,j;
        int[] generationFitness = new int[GENERATION_SIZE];
        int oneThreadAmountToCompute = GENERATION_SIZE / THREADS_NUMBER;
        
        ArrayList<Thread> threads = new ArrayList<Thread>();
        for(i = 0; i < THREADS_NUMBER - 1; i++) {
            Runnable task = new IndividumFitness(i*oneThreadAmountToCompute, (i+1)*oneThreadAmountToCompute, generationFitness, baseMap, deadlockMap, population);
            Thread worker = new Thread(task);
            worker.start();
            threads.add(worker);
        }
        for(j = i; j < GENERATION_SIZE; j++){
            EvolutionSokoSolver.individumFitnessCompute(j, generationFitness, baseMap, deadlockMap, population.get(j));
        }
        int running;
        do{
            running = 0;
            for (Thread thread : threads) {
                if (thread.isAlive()) {
                    running++;
                }
            }
        }while (running > 0);
        
        return generationFitness;
    }
    
    /**
    * Functions, calculates fitness of individual in population.
    *  
    * Fitness is computed as penalty, which individual gets for:
    *   - Moving in map, every step gets it penalty of 1.
    *   - Distance of every box to nearest target. Every tile equals penalty of DISTANCE_FROM_GOAL_PENALTY.
    *   - Deadlocked boxes. Every box equals penalty of STATIC_DEADLOCK_PENALTY.
    *   - Frozen boxes (a.k.a dynamic deadlock). Every box equals penalty of FREEZE_DEADLOCK_PENALTY.
    * 
    * @param index index of individual's fitness in generationFitnessArray where newly computed fitness will be stored.
    * @param individum string representation of current individual.
    */
    public static void individumFitnessCompute(int index, int[] generationFitnessArray, ArrayList<char[]> baseMap, ArrayList<char[]> deadlockMap, char[] individum){
        ArrayList<char[]> currentMap = EvolutionSokoSolver.cloneMap(baseMap);
        int penalty = 0;
        
        penalty += EvolutionSokoSolver.MoveInMap(currentMap, individum);
        penalty += EvolutionSokoSolver.computeDistancesFromGoals(currentMap) * DISTANCE_FROM_GOAL_PENALTY;  
        penalty += EvolutionSokoSolver.computeBoxDeadlocked(currentMap, deadlockMap) * STATIC_DEADLOCK_PENALTY;
        penalty += EvolutionSokoSolver.freezeDetect(currentMap, deadlockMap) * FREEZE_DEADLOCK_PENALTY;
        
        generationFitnessArray[index] = penalty;
        
        /*System.out.println("Vypocital som penalty: "+penalty+" pre index:"+index);
        System.out.println("jedinec:");
        EvolutionSokoSolver.traceIndividum(individum);
        System.out.println();
        System.out.println("Pre mapku:");
        EvolutionSokoSolver.traceMap(currentMap);*/
    }
    
    /**
    * Function, checks how many boxes are in static deadlock.
    *  
    * Uses precomputed deadlockMap, where all the static deadlock places are highlighted, for detection.
    * 
    * @param deadlockMap map where static deadlocks are highlighted. 
    * @param map map after movement of individual.
    * @return amount of boxes statically deadlocked.
    */
    public static int computeBoxDeadlocked(ArrayList<char[]> map, ArrayList<char[]> deadlockMap){
        int boxes_deadlocked = 0;
        
        int i,j;
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '$'){
                   if(deadlockMap.get(i)[j] != 'v'){
                        boxes_deadlocked++;
                    }
                }
            }
        }
        
        return boxes_deadlocked;
    }
    
    /**
    * Function, computes distances of every box on map to nearest goal
    *  
    * Uses function findDisToClosestHoleInMap() for computation of distance of every box.
    * 
    * @param map map after movement of individual.
    * @return sum of distances of all boxes.
    */
    public static int computeDistancesFromGoals(ArrayList<char[]> map){
        int total = 0;
        
        int i,j;
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '$'){
                    total += EvolutionSokoSolver.findDisToClosestHoleInMap(i, j, map);
                }
            }
        }
            
        return total;
    }
    
    /**
    * Function, finds distance to closest goal in map.
    *  
    * First it finds all the empty holes.
    * Then it computes distances to those goals using A*.
    * 
    * @param ypos y coordinate of box in the map.
    * @param xpos x coordinate of box in the map.
    * @return length of path to closest goal.
    */
    public static int findDisToClosestHoleInMap(int ypos, int xpos, ArrayList<char[]> map){
        int min = Integer.MAX_VALUE;
        ArrayList<int[]> holesPositions = new ArrayList<int[]>();
        
        int i,j;
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '.' || map.get(i)[j] == 's'){
                    holesPositions.add(new int[]{i,j});
                }
            }
        }
        
        int currentDistance = 0;
        for(i = 0; i < holesPositions.size(); i++){
            currentDistance = Astar.lengthOfPathBetweenTilesInMap(map, xpos, ypos, holesPositions.get(i)[1], holesPositions.get(i)[0], true);
            if(currentDistance < min){ 
                min = currentDistance; 
            }
        }
        
        return min;
    }
    
    /**
    * Function, using its string representation, function moves individual over the map.
    * 
    * Map is changed during the process.
    * Stops if all the boxes are in goal position.
    * Uses A* for calculation shortest paths from current agent position to next pushing position.
    * 
    * @param map map, gets changed during the process.
    * @param individum String representation of individual.
    * @return number of steps used.
    */
    public static int MoveInMap(ArrayList<char[]> map, char[] individum){
        ArrayList<int[]> holesPositions = new ArrayList<int[]>();
        ArrayList<int[]> boxesPositions = new ArrayList<int[]>();
        
        int numberOfBoxes = 0;
        int i,j;
        boolean solved = false;
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '.'){
                    holesPositions.add(new int[]{i,j});
                }else if(map.get(i)[j] == '$' || map.get(i)[j] == 'x'){
                    numberOfBoxes++;
                    boxesPositions.add(new int[]{i,j});
                }
            }
        }
        
        int[] sokoPos = EvolutionSokoSolver.findSokoInMap(map);
        if(sokoPos[0] == -1){
            System.out.println("Chyba: 'Nenasiel sa sokoban v mapke!'");
            System.exit(0);
        }
        
        int steps = 0;
        int unableToPerformMove = 0;
        for(i = 0; i < individum.length; i += 2){
            
            int boxY = boxesPositions.get(individum[i])[0];
            int boxX = boxesPositions.get(individum[i])[1];
            
            int dist;
            switch(individum[i+1]){
                case 0:
                    dist = Astar.lengthOfPathBetweenTilesInMap(map, sokoPos[1], sokoPos[0], boxX, boxY+1, false);
                    if(dist != -1){
                        if(EvolutionSokoSolver.moveBoxTopIfPossible(map, boxX, boxY)){
                            EvolutionSokoSolver.teleportSokoTo(map, sokoPos[1], sokoPos[0], boxX, boxY);
                            boxesPositions.get(individum[i])[0] -= 1;
                            sokoPos[1] = boxX;
                            sokoPos[0] = boxY;
                            steps += dist;
                        }else{
                            unableToPerformMove++;
                        }
                    }else{
                        unableToPerformMove++;
                    }
                    break;
                case 1:
                    dist = Astar.lengthOfPathBetweenTilesInMap(map, sokoPos[1], sokoPos[0], boxX, boxY-1, false);
                    if(dist != -1){
                        if(EvolutionSokoSolver.moveBoxBottomIfPossible(map, boxX, boxY)){
                            EvolutionSokoSolver.teleportSokoTo(map, sokoPos[1], sokoPos[0], boxX, boxY);
                            steps += dist;
                            sokoPos[1] = boxX;
                            sokoPos[0] = boxY;
                            boxesPositions.get(individum[i])[0] += 1;
                        }else{
                            unableToPerformMove++;
                        }
                    }else{
                        unableToPerformMove++;
                    }
                    break;
                case 2:
                    dist = Astar.lengthOfPathBetweenTilesInMap(map, sokoPos[1], sokoPos[0], boxX-1, boxY, false);
                    if(dist != -1){
                        if(EvolutionSokoSolver.moveBoxRightIfPossible(map, boxX, boxY)){
                            EvolutionSokoSolver.teleportSokoTo(map, sokoPos[1], sokoPos[0], boxX, boxY);
                            steps += dist;
                            sokoPos[1] = boxX;
                            sokoPos[0] = boxY;
                            boxesPositions.get(individum[i])[1] += 1;
                        }else{
                            unableToPerformMove++;
                        }
                    }else{
                        unableToPerformMove++;
                    }
                    break;
                case 3:
                    dist = Astar.lengthOfPathBetweenTilesInMap(map, sokoPos[1], sokoPos[0], boxX+1, boxY, false);
                    if(dist != -1){
                        if(EvolutionSokoSolver.moveBoxLeftIfPossible(map, boxX, boxY)){
                            EvolutionSokoSolver.teleportSokoTo(map, sokoPos[1], sokoPos[0], boxX, boxY);
                            steps += dist;
                            sokoPos[1] = boxX;
                            sokoPos[0] = boxY;
                            boxesPositions.get(individum[i])[1] -= 1;
                        }else{
                            unableToPerformMove++;
                        }
                    }else{
                        unableToPerformMove++;
                    }
                    break;
            }
           
            solved = true;
            for(j = 0; j < holesPositions.size(); j++){
                if(map.get(holesPositions.get(j)[0])[holesPositions.get(j)[1]] != 'x'){
                    solved = false;
                    break;
                }
            }
            
            if(solved){
                System.out.println("Našlo sa riešenie!");
                break;
            }
        }
        
        return steps * STEP_PENALTY + unableToPerformMove * UNABLE_TO_PERFORM_MOVE_PENALY;
    }
    
    /**
    * Function, designed for use by MoveInMap function. 
    * 
    * Teleports agent to specific positions. Affect current agent's position and his next position in map.
    */
    public static void teleportSokoTo(ArrayList<char[]> map, int oldX, int oldY, int newX, int newY){
        switch(map.get(oldY)[oldX]){
            case 's':
                map.get(oldY)[oldX] = '.';
                break;
            case '@':
                map.get(oldY)[oldX] = ' ';
                break;
        }
        switch(map.get(newY)[newX]){
            case '.':
                map.get(newY)[newX] = 's';
                break;
            case ' ':
                map.get(newY)[newX] = '@';
                break;
        }
    }
    
    /**
    * Function, designed for use by MoveInMap function. 
    * 
    * Moves box top if possible.
    * 
    * @param map map, gets changed during the process.
    * @param boxX x coordinate of box to be moved in map.
    * @param boxY y coordinate of box to be moved in map.
    * @return true if box could be moved, else returns false.
    */
    public static boolean moveBoxTopIfPossible(ArrayList<char[]> map, int boxX, int boxY){
        char leavingMark;
        if(map.get(boxY)[boxX] == 'x'){
            leavingMark = '.';
        }else{
            leavingMark = ' ';
        }
        switch(map.get(boxY-1)[boxX]){
            case ' ':
                map.get(boxY-1)[boxX] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '.':
                map.get(boxY-1)[boxX] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '$':
                return false;
            case 'x':
                return false;
            case '#':
                return false;
            case '@':
                map.get(boxY-1)[boxX] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case 's':
                map.get(boxY-1)[boxX] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
        }
        return false;
    }
    
    /**
    * Function, designed for use by MoveInMap function. 
    * 
    * Moves box bottom if possible.
    * 
    * @param map map, gets changed during the process.
    * @param boxX x coordinate of box to be moved in map.
    * @param boxY y coordinate of box to be moved in map.
    * @return true if box could be moved, else returns false.
    */
    public static boolean moveBoxBottomIfPossible(ArrayList<char[]> map, int boxX, int boxY){
        char leavingMark;
        if(map.get(boxY)[boxX] == 'x'){
            leavingMark = '.';
        }else{
            leavingMark = ' ';
        }
        switch(map.get(boxY+1)[boxX]){
            case ' ':
                map.get(boxY+1)[boxX] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '.':
                map.get(boxY+1)[boxX] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '$':
                return false;
            case 'x':
                return false;
            case '#':
                return false;
            case '@':
                map.get(boxY+1)[boxX] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case 's':
                map.get(boxY+1)[boxX] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
        }
        return false;
    }
    
    /**
    * Function, designed for use by MoveInMap function. 
    * 
    * Moves box right if possible.
    * 
    * @param map map, gets changed during the process.
    * @param boxX x coordinate of box to be moved in map.
    * @param boxY y coordinate of box to be moved in map.
    * @return true if box could be moved, else returns false.
    */
    public static boolean moveBoxRightIfPossible(ArrayList<char[]> map, int boxX, int boxY){
        char leavingMark;
        if(map.get(boxY)[boxX] == 'x'){
            leavingMark = '.';
        }else{
            leavingMark = ' ';
        }
        switch(map.get(boxY)[boxX+1]){
            case ' ':
                map.get(boxY)[boxX+1] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '.':
                map.get(boxY)[boxX+1] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '$':
                return false;
            case 'x':
                return false;
            case '#':
                return false;
            case '@':
                map.get(boxY)[boxX+1] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case 's':
                map.get(boxY)[boxX+1] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
        }
        return false;
    }
    
    /**
    * Function, designed for use by MoveInMap function. 
    * 
    * Moves box left if possible.
    * 
    * @param map map, gets changed during the process.
    * @param boxX x coordinate of box to be moved in map.
    * @param boxY y coordinate of box to be moved in map.
    * @return true if box could be moved, else returns false.
    */
    public static boolean moveBoxLeftIfPossible(ArrayList<char[]> map, int boxX, int boxY){
        char leavingMark;
        if(map.get(boxY)[boxX] == 'x'){
            leavingMark = '.';
        }else{
            leavingMark = ' ';
        }
        switch(map.get(boxY)[boxX-1]){
            case ' ':
                map.get(boxY)[boxX-1] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '.':
                map.get(boxY)[boxX-1] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case '$':
                return false;
            case 'x':
                return false;
            case '#':
                return false;
            case '@':
                map.get(boxY)[boxX-1] = '$';
                map.get(boxY)[boxX] = leavingMark;
                return true;
            case 's':
                map.get(boxY)[boxX-1] = 'x';
                map.get(boxY)[boxX] = leavingMark;
                return true;
        }
        return false;
    }
    
    public static void moveLeftInMap(ArrayList<char[]> map){
        int[] sokoPos = EvolutionSokoSolver.findSokoInMap(map);
        if(sokoPos[0] == -1){
            System.out.println("Chyba: 'Nenasiel sa sokoban v mapke!'");
            return;
        }
        
        if(sokoPos[1] > 0){
            char sokoLeftMark = ' ';
            if(map.get(sokoPos[0])[sokoPos[1]] == 's'){
                sokoLeftMark = '.';
            }
                
            switch(map.get(sokoPos[0])[sokoPos[1]-1]){
                case ' ':
                    map.get(sokoPos[0])[sokoPos[1]-1] = '@';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '.':
                    map.get(sokoPos[0])[sokoPos[1]-1] = 's';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '$':
                    if(sokoPos[1] > 1){
                        if(map.get(sokoPos[0])[sokoPos[1]-2] == ' '){
                            map.get(sokoPos[0])[sokoPos[1]-2] = '$';
                            map.get(sokoPos[0])[sokoPos[1]-1] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0])[sokoPos[1]-2] == '.'){
                            map.get(sokoPos[0])[sokoPos[1]-2] = 'x';
                            map.get(sokoPos[0])[sokoPos[1]-1] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
                 case 'x':
                    if(sokoPos[1] > 1){
                        if(map.get(sokoPos[0])[sokoPos[1]-2] == ' '){
                            map.get(sokoPos[0])[sokoPos[1]-2] = '$';
                            map.get(sokoPos[0])[sokoPos[1]-1] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0])[sokoPos[1]-2] == '.'){
                            map.get(sokoPos[0])[sokoPos[1]-2] = 'x';
                            map.get(sokoPos[0])[sokoPos[1]-1] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
            }
        }
    }
    
    public static void moveBotInMap(ArrayList<char[]> map){
        int[] sokoPos = EvolutionSokoSolver.findSokoInMap(map);
        if(sokoPos[0] == -1){
            System.out.println("Chyba: 'Nenasiel sa sokoban v mapke!'");
            return;
        }
        
        if(sokoPos[0] < map.size() - 1){
            char sokoLeftMark = ' ';
            if(map.get(sokoPos[0])[sokoPos[1]] == 's'){
                sokoLeftMark = '.';
            }
                
            switch(map.get(sokoPos[0]+1)[sokoPos[1]]){
                case ' ':
                    map.get(sokoPos[0]+1)[sokoPos[1]] = '@';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '.':
                    map.get(sokoPos[0]+1)[sokoPos[1]] = 's';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '$':
                    if(sokoPos[0] < map.size() - 2){
                        if(map.get(sokoPos[0]+2)[sokoPos[1]] == ' '){
                            map.get(sokoPos[0]+2)[sokoPos[1]] = '$';
                            map.get(sokoPos[0]+1)[sokoPos[1]] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0]+2)[sokoPos[1]] == '.'){
                            map.get(sokoPos[0]+2)[sokoPos[1]] = 'x';
                            map.get(sokoPos[0]+1)[sokoPos[1]] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
                 case 'x':
                    if(sokoPos[0] < map.size() - 2){
                        if(map.get(sokoPos[0]+2)[sokoPos[1]] == ' '){
                            map.get(sokoPos[0]+2)[sokoPos[1]] = '$';
                            map.get(sokoPos[0]+1)[sokoPos[1]] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0]+2)[sokoPos[1]] == '.'){
                            map.get(sokoPos[0]+2)[sokoPos[1]] = 'x';
                            map.get(sokoPos[0]+1)[sokoPos[1]] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
            }
        }
    }
    
    public static void moveRightInMap(ArrayList<char[]> map){
        int[] sokoPos = EvolutionSokoSolver.findSokoInMap(map);
        if(sokoPos[0] == -1){
            System.out.println("Chyba: 'Nenasiel sa sokoban v mapke!'");
            return;
        }
        
        if(sokoPos[1] < map.get(sokoPos[0]).length - 1){
            char sokoLeftMark = ' ';
            if(map.get(sokoPos[0])[sokoPos[1]] == 's'){
                sokoLeftMark = '.';
            }
                
            switch(map.get(sokoPos[0])[sokoPos[1]+1]){
                case ' ':
                    map.get(sokoPos[0])[sokoPos[1]+1] = '@';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '.':
                    map.get(sokoPos[0])[sokoPos[1]+1] = 's';
                    map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                    break;
                case '$':
                    if(sokoPos[1] < map.get(sokoPos[0]).length - 2){
                        if(map.get(sokoPos[0])[sokoPos[1]+2] == ' '){
                            map.get(sokoPos[0])[sokoPos[1]+2] = '$';
                            map.get(sokoPos[0])[sokoPos[1]+1] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0])[sokoPos[1]+2] == '.'){
                            map.get(sokoPos[0])[sokoPos[1]+2] = 'x';
                            map.get(sokoPos[0])[sokoPos[1]+1] = '@';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
                 case 'x':
                    if(sokoPos[1] < map.get(sokoPos[0]).length - 2){
                        if(map.get(sokoPos[0])[sokoPos[1]+2] == ' '){
                            map.get(sokoPos[0])[sokoPos[1]+2] = '$';
                            map.get(sokoPos[0])[sokoPos[1]+1] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }else if(map.get(sokoPos[0])[sokoPos[1]+2] == '.'){
                            map.get(sokoPos[0])[sokoPos[1]+2] = 'x';
                            map.get(sokoPos[0])[sokoPos[1]+1] = 's';
                            map.get(sokoPos[0])[sokoPos[1]] = sokoLeftMark;
                        }
                    }
                    break;
            }
        }
    }
    
    /**
    * Function, finds agent (sokoban character) in given map.
    * 
    * @param map map where to look for in.
    * @return position when found, [-1,-1] when not found.
    */
    public static int[] findSokoInMap(ArrayList<char[]> map){
        int i,j;
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '@' || map.get(i)[j] == 's'){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{-1,-1};
    }
    
    /**
    * Function, marks all positions in given map, where box can be pulled. 
    * 
    * Used for static deadlock detection.
    * 
    * @param map map, gets changed during the process, visitable positions will be highlighted.
    */
    public static void markAllVisitablePositionsOnMap(ArrayList<char[]> map){
        int i,j;
        
        for(i = 0; i < map.size(); i++){
            for(j = 0; j < map.get(i).length; j++){
                if(map.get(i)[j] == '.'){
                    EvolutionSokoSolver.pullAllDirectionsAndMarkVisitedFrom(i,j,map);
                }
            }
        }
    }
    
    /**
    * Function, marks all the (max 4) positions where box can be pulled from given position. 
    * 
    * Used for static deadlock detection.
    * 
    * @param map map, gets changed during the process.
    * @param x x coordinate of box to be moved in map.
    * @param y y coordinate of box to be moved in map.
    */
    public static void pullAllDirectionsAndMarkVisitedFrom(int y, int x, ArrayList<char[]> map){
        map.get(y)[x] = 'v';
        
        if(y > 1 && map.get(y-1)[x] != 'v' && map.get(y-1)[x] != '#' && map.get(y-2)[x] != '#'){
            pullAllDirectionsAndMarkVisitedFrom(y-1,x,map);
        }
        
        if(y < map.size() - 2 && map.get(y+1)[x] != 'v' && map.get(y+1)[x] != '#' && map.get(y+2)[x] != '#'){
            pullAllDirectionsAndMarkVisitedFrom(y+1,x,map);
        }
        
        if(x > 1 && map.get(y)[x-1] != 'v' && map.get(y)[x-1] != '#' && map.get(y)[x-2] != '#'){
            pullAllDirectionsAndMarkVisitedFrom(y,x-1,map);
        }
        
        if(x < map.get(y).length - 2 && map.get(y)[x+1] != 'v' && map.get(y)[x+1] != '#' && map.get(y)[x+2] != '#'){
            pullAllDirectionsAndMarkVisitedFrom(y,x+1,map);
        }
    }
    
    /**
    * Function, detects some of dynamic deadlocks. 
    * 
    * Used for dynamic deadlock detection, when counting penalty.
    * 
    * @param currentMap map, after movement of agent.
    * @param deadlockMap map of static deadlocks.
    * @return 1 if freeze is detected, else returns 0.
    */
    public static int freezeDetect(ArrayList<char[]> currentMap, ArrayList<char[]> deadlockMap){
        int i,j;
        
        for(i = 0; i < currentMap.size(); i++){
            for(j = 0; j < currentMap.get(i).length; j++){
                if(currentMap.get(i)[j] == '$'){
                    if(EvolutionSokoSolver.freezeDetectBox(currentMap, deadlockMap, j, i, true, true)){
                        return 1;
                    }
                }
            }
        }
        
        return 0;
    }

    /**
    * Function, detects if given box is dynamically deadlocked.
    * 
    * Does not detect all possible dynamic deadlocks. Can be called recursively.
    * Detects freeze over each axis separately. Deadlocked if box is deadlocked over both axis.
    * 
    * @param currentMap map, after movement of agent.
    * @param deadlockMap map of static deadlocks.
    * @return true if box is dynamically deadlocked, else returns false.
    */
    public static boolean freezeDetectBox(ArrayList<char[]> currentMap, ArrayList<char[]> deadlockMap, int boxX, int boxY, boolean checkX, boolean checkY){
        boolean blockedX = false;
        boolean blockedY = false;
        
        if(!checkX){
            blockedX = true;
        }
        if(!checkY){
            blockedY = true;
        }
      
        if(!blockedX && (currentMap.get(boxY)[boxX-1] == '#' || currentMap.get(boxY)[boxX+1] == '#')){
            blockedX = true;
        }
        if(!blockedY && (currentMap.get(boxY-1)[boxX] == '#' || currentMap.get(boxY+1)[boxX] == '#')){
            blockedY = true;
        }
        if(!blockedX && (deadlockMap.get(boxY)[boxX-1] == ' ' && deadlockMap.get(boxY)[boxX+1] == ' ')){
            blockedX = true;
        }
        if(!blockedY && (deadlockMap.get(boxY-1)[boxX] == ' ' && deadlockMap.get(boxY+1)[boxX] == ' ')){
            blockedY = true;
        }
        if(!blockedX && (currentMap.get(boxY)[boxX-1] == '$' || currentMap.get(boxY)[boxX-1] == 'x')){
            ArrayList<char[]> map = EvolutionSokoSolver.cloneMap(currentMap);
            map.get(boxY)[boxX] = '#';
            if(EvolutionSokoSolver.freezeDetectBox(map, deadlockMap, boxX-1, boxY, false, true)){
                blockedX = true;
            }
        }
        if(!blockedX && (currentMap.get(boxY)[boxX+1] == '$' || currentMap.get(boxY)[boxX+1] == 'x')){
            ArrayList<char[]> map = EvolutionSokoSolver.cloneMap(currentMap);
            map.get(boxY)[boxX] = '#';
            if(EvolutionSokoSolver.freezeDetectBox(map, deadlockMap, boxX+1, boxY, false, true)){
                blockedX = true;
            }
        }
        if(!blockedY && (currentMap.get(boxY-1)[boxX] == '$' || currentMap.get(boxY-1)[boxX] == 'x')){
            ArrayList<char[]> map = EvolutionSokoSolver.cloneMap(currentMap);
            map.get(boxY)[boxX] = '#';
            if(EvolutionSokoSolver.freezeDetectBox(map, deadlockMap, boxX, boxY-1, true, false)){
                blockedY = true;
            }
        }
        if(!blockedY && (currentMap.get(boxY+1)[boxX] == '$' || currentMap.get(boxY+1)[boxX] == 'x')){
            ArrayList<char[]> map = EvolutionSokoSolver.cloneMap(currentMap);
            map.get(boxY)[boxX] = '#';
            if(EvolutionSokoSolver.freezeDetectBox(map, deadlockMap, boxX, boxY+1, true, false)){
                blockedY = true;
            }
        }
        
        if(blockedX && blockedY) {
            return true;
        }else{
            return false;
        }
    }

     
    /**
    * Function, creates brand new generation, totally randomly.
    * 
    * For every individual generates random number of pairs, from which first number represents number of box to be pushed
    * and second represents direction to which box will be pulled.
    * 
    * @param baseMap base map of sokoban problem.
    * @return list of string representations.
    */
    public static ArrayList<char[]> generateBrandNewGeneration(ArrayList<char[]> baseMap){
        Random generator = new Random();
        ArrayList<char[]> newGenration = new ArrayList<>();
        int numberOfBoxes = 0;
        int i,j;
        
        for(i = 0; i < baseMap.size(); i++){
            for(j = 0; j < baseMap.get(i).length; j++){
                if(baseMap.get(i)[j] == '$'){
                    numberOfBoxes++;
                }
            }
        }
        
        for(i = 0; i < GENERATION_SIZE; i++){
            newGenration.add(EvolutionSokoSolver.createNewIndividum(numberOfBoxes, generator));
        }
        
        return newGenration;
    }
    
    /**
    * Function, creates brand new individual.
    * 
    * Designed for use by generateBrandNewGeneration(). Check its docs for further explanation.
    * 
    * @return string representation of new individual.
    */
    public static char[] createNewIndividum(int numberOfBoxes, Random generator){
        int stringSize = MIN_INDIVIDUM_SIZE + generator.nextInt(MAX_INDIVIDUM_SIZE - MIN_INDIVIDUM_SIZE);
        if(stringSize % 2 != 0){
            if(stringSize == 30){
                stringSize = 32;
            }else{
                stringSize -= 1;
            }
        }
        char[] newIndividum =  new char[stringSize];
        for(int j = 0; j < stringSize; j += 2){
            newIndividum[j] = (char)generator.nextInt(numberOfBoxes);
            newIndividum[j+1] = (char)generator.nextInt(4);
        }
        
        return newIndividum;
    }
    
    /**
    * Help function.
    * 
    * Traces population to standard output.
    */
    public static void tracePopulation(ArrayList<char[]> population){
        for(int i = 0; i < population.size(); i++){
            for(int j = 0; j < population.get(i).length; j++){
                System.out.print((int)population.get(i)[j]);
            }
            System.out.println();
        }
    }
    
    /**
    * Help function.
    * 
    * Traces individual to standard output.
    */
    public static void traceIndividum(char[] individum){
        for(int i = 0; i < individum.length; i++){
            System.out.print((int)individum[i]);
        }
    }
    
    /**
    * Help function.
    * 
    * Traces map to standard output.
    */
    public static void traceMap(ArrayList<char[]> map){
        for(int i = 0; i < map.size(); i++){
            System.out.println(map.get(i));
        }
    }
    
    /**
    * Help function.
    * 
    * Clones map.
    */
    public static ArrayList<char[]> cloneMap(ArrayList<char[]> baseMap){
        ArrayList<char[]>newArray = new ArrayList<>(baseMap.size());
        for(char[] item: baseMap) {
            newArray.add(item.clone());
        }
        return newArray;
    }
}