import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

public final class ASAGA {

    static Random random = new Random();

    static class Solution {
        int[] values;

        public Solution(int v[]) {
            values = v.clone();
        }

        public float fitness() {
            int err = 0;
            for(int i=0; i<values.length; i++)
                err += Math.pow(values[i] - i, 2);

            if(err == 0)
                return 1.1f;

            return 1.0f / err;
        }

        public Solution clone() {
            return new Solution(this.values);
        }

        public boolean compare(Solution x) {
            for(int i=0; i<values.length; i++) {
                if(values[i] != x.values[i]) return false;
            }
            return true;
        }
    }

    public static int[] randomDistribuction(int n) {
        Stack<Integer> numbers = new Stack<>();
        for(int i=0; i<n; i++)
            numbers.add(i);
        int[] distribuction = new int[n];
        Random r = new Random();
        for(int i=0; i<n; i++) {
            int valueIdx = r.nextInt(numbers.size());
            distribuction[i] = numbers.get(valueIdx);
            numbers.remove(valueIdx);
        }
        return distribuction;
    }

    public static Solution mutation(Solution a) {
        Solution mutated = a.clone();
        int rate = random.nextInt(1) + 1;
        for(int i=0; i<rate; i++) {
            int posA = random.nextInt(mutated.values.length);
            int posB = random.nextInt(mutated.values.length);
            int tmp = mutated.values[posA];
            mutated.values[posA] = mutated.values[posB];
            mutated.values[posB] = tmp;
        }
        return mutated;
    }

    public static Solution selection(List<Solution> population) {
        Stack<Float> roulet = new Stack<>();
        float fitnessAll = 0;
        for(Solution x : population) {
            fitnessAll += x.fitness();
        }
        float influence = 0;
        for(int i=0; i<population.size(); i++) {

            influence += (population.get(i).fitness() / (fitnessAll * 1.0));
            roulet.push(influence);
        }
        float s = random.nextFloat();
        for(int i=0; i<roulet.size(); i++) {
            if(s <= roulet.get(i)) {
                return population.get(i);
            }
        }
        //
        return population.get(population.size() - 1);
    }

    public static Solution bestSolution(List<Solution> solutions) {
        Solution best = null;
        for(Solution x : solutions) {
            if(best == null || x.fitness() > best.fitness())
                best = x;
        }
        return best;
    }

    public static List<Solution> filter(List<Solution> population) {
        float factor = random.nextFloat() * 0.2f + 0.1f;
        int newSize = (int) Math.ceil(population.size() * factor);

        Solution bestSolution = bestSolution(population);

        List<Solution> newPopulation = new ArrayList<>();
        newPopulation.add(bestSolution);

        population.remove(bestSolution);

        for(int i=0; i<newSize && population.size() > 0; i++) {
            Solution s = selection(population);
            newPopulation.add(s);
            population.remove(s);
        }

        return newPopulation;
    }


    public static Solution cross(List<Solution> population) {
        if(population.size() < 2) return null;

        Solution a = selection(population);
        population.remove(a);
        Solution b = selection(population);
        population.add(a);

        Solution c = a.clone();

        //
        int x = random.nextInt(a.values.length);
        int e = x;
        while(true) {
            c.values[x] = b.values[x];
            for(int i=0; i<b.values.length; i++) {
                if(b.values[i] == a.values[x]) {
                    x = i;
                    break;
                }
            }
            if(x == e)
                break;
        }

        if(c.compare(a) || c.compare(b)) return null;

        return c;
    }

    public static void main(String[] args) throws IOException, InterruptedException {
        List<Solution> population = new ArrayList<>();

        population.add(new Solution(randomDistribuction(100)));

        Scanner s = new Scanner(System.in);

        int generation = 1;

        while(true) {
            System.out.println("Geração: " + generation);
            System.out.println("População: " + population.size());
            System.out.println("Best Fitness: " + bestSolution(population).fitness());
            System.out.println("Best Solution: " + Arrays.toString(bestSolution(population).values));
            System.out.println();

            // Population
            if(population.size() > 10)
                population = filter(population);

            // Mutation
            int mutations = random.nextInt(10) + 1;
            for(int i=0; i<mutations; i++)
                population.add(mutation(selection(population)));

            // Crosss
            int cross = random.nextInt(10) + 1;
            for(int i=0; i<cross; i++) {
                Solution newMember = cross(population);
                if(newMember == null) continue;
                population.add(newMember);
            }
            //
            if(bestSolution(population).fitness() > 1) break;



            generation += 1;
        }
        //
        System.out.println("Best Solution: " + Arrays.toString(bestSolution(population).values));
    }
}