import java.util.Random;

public class Simple3
{
    private static final double TARGET = 100.0;          // Number for algorithm to find.
    private static final int MAX_INPUTS = 50;            // Number of chromosomes in population.
    private static final int MAX_EPOCHS = 10000;         // Arbitrary number of test cycles.
    private static final double MUTATION_RATE = 0.001;
    private static final double MUTATION_RATE2 = 0.03;   // Stagnation avoidance mutation rate.

    private static final boolean SHOW_VERBOSE_RESULTS = false;
/*
    0000 0000 0000 0000 0000 0000 0000 0000 0000

    Four bits are required to represent the range of characters used:
    DIGITS:                Operators:
       0: 0000                 +: 1010
       1: 0001                 +: 1011
       2: 0010                 -: 1100
       3: 0011                 -: 1101
       4: 0100                 *: 1110
       5: 0101                 /: 1111
       6: 0110
       7: 0111
       8: 1000
       9: 1001
*/
    private static final int MAX_SIZE = 36;
    
    private static final int DIGITS[][] = new int[][] {{0, 0, 0, 0}, 
                                                       {0, 0, 0, 1}, 
                                                       {0, 0, 1, 0}, 
                                                       {0, 0, 1, 1}, 
                                                       {0, 1, 0, 0}, 
                                                       {0, 1, 0, 1}, 
                                                       {0, 1, 1, 0}, 
                                                       {0, 1, 1, 1}, 
                                                       {1, 0, 0, 0}, 
                                                       {1, 0, 0, 1}};

    private static final int OPERATORS[][] = new int[][] {{1, 0, 1, 0}, 
                                                         {1, 0, 1, 1}, 
                                                         {1, 1, 0, 0}, 
                                                         {1, 1, 0, 1}, 
                                                         {1, 1, 1, 0}, 
                                                         {1, 1, 1, 1}};

    private static int inputs[][] = new int[MAX_INPUTS][MAX_SIZE];    // Current population.
    private static int nextGen[][] = new int[MAX_INPUTS][MAX_SIZE];   // Next population.
    private static double totals[] = new double[MAX_INPUTS];          // Decoded values.
    private static double fitness[] = new double[MAX_INPUTS];         // Fitness as percentage.
    private static boolean selected[] = new boolean[MAX_INPUTS];      // Eligible parents.
    private static int childCount = 0;
    private static int nextMutation = 0;                              // For scheduling mutations.
    private static int mutations = 0;
    private static int NaNAvoidanceCalls = 0;
    private static boolean stopTest = false;

    //  Note that as a floating point value, I can be a little more lenient with the algorithm's solutions.
    //  I've arbitrarily chosen the range between 99.999 and 100.001 as acceptable solutions.

    private static void geneticAlgorithm()
    {
        int epoch = 0;
        boolean done = false;

        initializeChromosomes();
        nextMutation = getRandomNumber((int)Math.round(1.0 / MUTATION_RATE));

        while(!done)
        {
            for(int i = 0; i < MAX_INPUTS; i++)
            {
                totals[i] = decodeInput(i);
                if(Math.abs(totals[i] - TARGET) <= 0.001 || epoch == MAX_EPOCHS){
                    done = true;
                }
            }

            getFitness();

            if(epoch == 0 || SHOW_VERBOSE_RESULTS == true || done == true){
                for(int i = 0; i < MAX_INPUTS; i++)
                {
                    for(int j = 0; j < MAX_SIZE; j++)
                    {
                        System.out.print(inputs[i][j]);
                    } // j
                    System.out.print(" = " + totals[i]);
                            System.out.print("\t" + fitness[i] + "%\n");
                } // i
                System.out.println();
            }

            selection();

            mating();

            prepNextEpoch();

            epoch += 1;

            // Stop all testing if user clicks Button2.
            if(stopTest == true){
                done = true;
            }
        }

        System.out.println("done.");
        if(epoch != MAX_EPOCHS){
            System.out.print(GetDecodedFunction());
        }
        System.out.println("Completed " + epoch + " epochs.");
        System.out.println("Encountered " + mutations + " mutations in " + childCount + " offspring.");
        System.out.print("NaN avoidance routine called " + NaNAvoidanceCalls + " times.");

        return;
    }

    private static void initializeChromosomes()
    {
        int getRand = 0;
        int l = 0;

        for(int i = 0; i < MAX_INPUTS; i++)
        {
            l = 0;
            for(int j = 0; j <= 8; j++)
            {
                if(j % 2 == 0){
                    // j is even; this is an operand
                    getRand = getRandomNumber(9);
                    for(int k = 0; k <= 3; k++)
                    {
                        inputs[i][l] = DIGITS[getRand][k];
                        l += 1;
                    } // k
                }else{
                    // j is odd; this is an operator
                    getRand = getRandomNumber(5);
                    for(int k = 0; k <= 3; k++)
                    {
                        inputs[i][l] = OPERATORS[getRand][k];
                        l += 1;
                    } // k
                }
            } // j
        } // i
        return;
    }

    private static double decodeInput(int InputIndex)
    {
        // Take a chromosome, decode it, evaluate it mathematically, and return the answer.
        // Ignore the usual rules of algebraic evaluation, and simple go from left to right.
        int pointer = 0;
        boolean done = false;
        int operator = 0;
        int operand = 0;
        double total = 0.0;
/*
        0-3:   operand
        4-7:   operator
        8-11:  operand
        12-15: operator
        16-19: operand
        20-23: operator
        24-27: operand
        28-31: operator
        32-35: operand
*/
        pointer = 0;
        // Get first operand...
        for(int i = 3; i >= 0; i--)
        {
            total += inputs[InputIndex][pointer] * Math.pow(2, i); // B2D
            pointer += 1;
        } // i

        done = false;
        while(!done)
        {
            // Get next operator...
            operator = 0;
            for(int i = 3; i >= 0; i--)
            {
                operator += inputs[InputIndex][pointer] * Math.pow(2, i); // B2D
                pointer += 1;
            }

            // Get next operand...
            operand = 0;
            for(int i = 3; i >= 0; i--)
            {
                operand += inputs[InputIndex][pointer] * Math.pow(2, i); // B2D
                pointer += 1;
            } // i

            if(operator == 10 || operator == 11){
                // Addition
                total += operand;
            }else if(operator == 12 || operator == 13){
                // Subtraction
                total -= operand;
            }else if(operator == 14){
                // Multiplication
                total *= operand;
            }else{
                // Division
                if(operand != 0){ // Avoid divide-by-zero errors.
                    total /= operand;
                }
            }

            if(pointer >= 35){
                done = true;
            }
        }
        return total;
    }

    private static void getFitness()
    {
        // Lowest errors = 100%, Highest errors = 0%
        double bestScore = 0.0;
        double worstScore = 0.0;
        int NaNCount = 0; // Monitors fitness scores for non-real numbers
    
            // The worst score would be the one furthest from the Target.
            worstScore = Math.abs(TARGET - totals[maximum(totals)]);
    
            // The best would be the closest.
            bestScore = Math.abs(TARGET - totals[minimum(totals)]);
    
            // Convert to a weighted percentage.
            bestScore = worstScore - Math.abs(TARGET - totals[minimum(totals)]);
            for(int i = 0; i < MAX_INPUTS; i++)
            {
                fitness[i] = (worstScore - (Math.abs(TARGET - totals[i]))) * 100 / bestScore;
                if(Double.isNaN(fitness[i])){
                    NaNCount += 1;
                }
            }
    
            // Prepare to shake up population if all fitness scores become NaN.
            if(NaNCount == MAX_INPUTS){
                breakNaN();
            }
        return;
    }

    private static void selection()
    {
        // We start out with n individuals, and will stay with n.
        // To do this, pick out the most fit, mate them, then replace the least fit
        // with the new offspring.  The parents will remain for the next
        // population. Basically, the least fit are always being weeded out.
        int getRand = 0;

        for(int i = 0; i < MAX_INPUTS; i++)
        {
            getRand = getRandomNumber(100);
            if(fitness[i] >= getRand){
                selected[i] = true;
            }else{
                selected[i] = false;
            }
        }
        return;
    }

    private static void mating()
    {
        int pointer1 = 0;
        int pointer2 = 0;
        int maxChild = 0;
        int canMate = 0;
        int cannotMate[] = new int[MAX_INPUTS];
        int parentA = 0;
        int parentB = 0;
        int newChild[] = new int[MAX_SIZE];

        for(int i = 0; i < MAX_INPUTS; i++)
        {
            cannotMate[i] = -1;
        }

        // Determine total who can mate.
        pointer1 = 0;
        pointer2 = 0;
        for(int i = 0; i < MAX_INPUTS; i++)
        {
            if(selected[i] == true){
                canMate += 1;
                // Copy selected individuals to next generation.
                for(int j = 0; j < MAX_SIZE; j++)
                {
                    nextGen[pointer1][j] = inputs[i][j];
                } // j
                pointer1 += 1;
            }else{ // Cannot mate.
                cannotMate[pointer2] = i;
                pointer2 += 1;
            }
        } // i

        maxChild = MAX_INPUTS - canMate; // Total number of offspring to be created.

        if(canMate > 1 && pointer2 > 0){
            for(int i = 0; i < maxChild; i++)
            {
                parentA = chooseparent();
                parentB = chooseparent(parentA);
                crossover(parentA, parentB, newChild);
                for(int j = 0; j < MAX_SIZE; j++)
                {
                    nextGen[pointer1][j] = newChild[j];
                } // j

                if(childCount == nextMutation){
                    mutation(pointer1);
                }

                pointer1 += 1;
                childCount += 1;

                // Schedule next mutation.
                if(childCount % (int)Math.round(1.0 / MUTATION_RATE) == 0){
                    nextMutation = childCount + getRandomNumber((int)Math.round(1.0 / MUTATION_RATE));
                }
            } // i
        }
        return;
    }

    private static int chooseparent()
    {
        // Overloaded function, see also "Chooseparent(ByVal parentA As Integer)".
        int parent = 0;
        boolean done = false;

        while(!done)
        {
            // Randomly choose an eligible parent.
            parent = getRandomNumber(MAX_INPUTS - 1);
            if(selected[parent] == true){
                done = true;
            }
        }

        return parent;
    }

    private static int chooseparent(int parentA)
    {
        // Overloaded function, see also "Chooseparent()".
        int parent = 0;
        boolean done = false;

        while(!done)
        {
            // Randomly choose an eligible parent.
            parent = getRandomNumber(MAX_INPUTS - 1);
            if(parent != parentA){
                if(selected[parent] == true){
                    done = true;
                }
            }
        }

        return parent;
    }

    private static void crossover(int chromA, int chromB, int[] newChrom)
    {
        // select a random gene along the length of the
        // chromosomes and swap all genes after that point.
        int randomPoint = 0;

        // We want the point to be at a logical place, so that valid operands and
        // operators are kept intact.
        randomPoint = getRandomNumber(8);
        randomPoint *= 4;

        for(int i = 0; i < MAX_SIZE; i++)
        {
            if(i < randomPoint){
                newChrom[i] = inputs[chromA][i];
            }else if(i >= randomPoint){
                newChrom[i] = inputs[chromB][i];
            }
        } // i
        return;
    }

    private static void mutation(int childIndex)
    {
        int j = 0;
        int randomPoint = 0;
        int randomItem = 0;

        // We want the point to be at a logical place, so that valid operands and
        // operators are kept intact.
        randomPoint = getRandomNumber(8);

        if(randomPoint % 2 == 0){
            // randomPoint is even; this is an operand
            randomItem = getRandomNumber(9);
        }else{
            // randomPoint is odd; this is an operator
            randomItem = getRandomNumber(5);
        }

        j = 0;
        for(int i = 0; i < MAX_SIZE; i++)
        {
            if((i > (randomPoint * 4) - 1) && (i < (randomPoint * 4) + 4)){
                if(randomPoint % 2 == 0){
                    nextGen[childIndex][i] = DIGITS[randomItem][j];
                }else{
                    nextGen[childIndex][i] = OPERATORS[randomItem][j];
                }
                j += 1;
            }else{
                nextGen[childIndex][i] = inputs[childIndex][i];
            }
        } // i

        mutations += 1;
        return;
    }

    //  This helps to break up the monotony a little...

    private static void breakNaN()
    {
        // If the entire population achieves a fitness score of NaN,
        // shake up the monotony with several mutations.
        int getRand = 0;

        for(int i = 0; i < MAX_INPUTS; i++)
        {
            getRand = getRandomNumber(100);
            if(getRand <= (1 / MUTATION_RATE2)){
                mutation(i);
            }
        }

        NaNAvoidanceCalls += 1;
        return;
    }

    private static void prepNextEpoch()
    {
        // Copy next generation into current generation input.
        for(int i = 0; i < MAX_INPUTS; i++)
        {
            for(int j = 0; j < MAX_SIZE; j++)
            {
                inputs[i][j] = nextGen[i][j];
            } // j
        } // i

        // Reset flags for selected individuals.
        for(int i = 0; i < MAX_INPUTS; i++)
        {
            selected[i] = false;
        } // i
        return;
    }

    private static String GetDecodedFunction()
    {
        int pointer = 0;
        int item  = 0;
        StringBuffer tempString = new StringBuffer();

        for(int i = 0; i < MAX_INPUTS; i++)
        {
            totals[i] = decodeInput(i);
            if(Math.abs(totals[i] - TARGET) <= 0.001){
                // Print the chromosome.
                for(int j = 0; j < MAX_SIZE; j++)
                {
                    tempString.append(inputs[i][j]);
                } // j
                tempString.append("\n");

                // Print the decoded function.
                pointer = 0;
                for(int j = 0; j <= 8; j++)
                {
                    item = 0;
                    for(int k = 3; k >= 0; k--)
                    {
                        item += inputs[i][pointer] * Math.pow(2, k); // B2D
                        pointer += 1;
                    } // k
                    if(item < 10){
                        tempString.append(item + " ");
                    }else{
                        if(item == 10 || item == 11){
                            // Addition
                            tempString.append("+ ");
                        }else if(item == 12 || item == 13){
                            // Subtraction
                            tempString.append("- ");
                        }else if(item == 14){
                            // Multiplication
                            tempString.append("* ");
                        }else{
                            // Division
                            tempString.append("/ ");
                        }
                    }
                } // j
                tempString.append("= " + totals[i] + "\n");
            }
        } // i

        return tempString.toString();
    }

    private static int getRandomNumber(int high)
    {
        return new Random().nextInt(high);
    }

    private static int minimum(double[] intArray)
    {
        // Returns an array index.
        int winner = 0;
        boolean foundNewWinner = false;
        boolean done = false;
        
        while(!done)
        {
            foundNewWinner = false;
            for(int i = 0; i < MAX_INPUTS; i++)
            {
                if(i != winner){             // Avoid self-comparison.
                    // The minimum has to be in relation to the Target.
                    if(Math.abs(TARGET - intArray[i]) < Math.abs(TARGET - intArray[winner])){
                        winner = i;
                        foundNewWinner = true;
                    }
                }
            }

            if(foundNewWinner == false){
                done = true;
            }
        }

        return winner;
    }

    private static int maximum(double[] intArray)
    {
        // Returns an array index.
        int winner = 0;
        boolean foundNewWinner = false;
        boolean done = false;
        
        while(!done)
        {
            foundNewWinner = false;
            for(int i = 0; i < MAX_INPUTS; i++)
            {
                if(i != winner){             // Avoid self-comparison.
                    // The minimum has to be in relation to the Target.
                    if(Math.abs(TARGET - intArray[i]) > Math.abs(TARGET - intArray[winner])){
                        winner = i;
                        foundNewWinner = true;
                    }
                }
            }

            if(foundNewWinner == false){
                done = true;
            }
        }

        return winner;
    }
    
    public static void main(String[] args)
    {
        geneticAlgorithm();
        return;
    }

}