import java.util.*;

public class Darwin {

    private static final String CHAR_LIST = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" +
        "0123456789!\"£$%^&*()_+-={}[];'#:@~\\|,./<>? ";
    private static final int NUM_CHARS = CHAR_LIST.length();
    private static final int LITTER_SIZE = 10;
    private static final int MAX_MUTATION = 5;
    private static final double MUTATION_RATE = 0.01;
    private static final int LEN_ERROR_PENALTY = NUM_CHARS / 2;
    private static final int PAUSE_BTW_GENS = 10;

    private String target, current;
    private String[] litter;
    private Random rgen;
    private int generation;

    public Darwin() {
        rgen = new Random();
        litter = new String[LITTER_SIZE];
    }

    public void evolve(String targetString) {
        target = filter(targetString);
        current = "" + getRandomChar();
        generation = 1;
        while (!current.equals(target)) {
            nextGeneration();
            try {Thread.sleep(PAUSE_BTW_GENS);}
            catch (InterruptedException ex) {}
        }
        System.out.println("---Finished---");
    }

    private String filter(String text) {
        StringBuilder filtered = new StringBuilder();
        for (char ch : text.toCharArray()) {
            if (CHAR_LIST.indexOf(ch) != -1) {
                filtered.append(ch);
            }
        }
        return filtered.toString();
    }

    private char getRandomChar() {
        return CHAR_LIST.charAt(rgen.nextInt(NUM_CHARS));
    }

    private void nextGeneration() {
        System.out.println("Generation " + generation + ":");
        for (int i = 0; i < LITTER_SIZE; i++) {
            litter[i] = getChild();
            System.out.println("Child" + i + ": " + litter[i]);
        }
        current = getWinner();
        System.out.println("Target: " + target);
        System.out.println("Winner: " + current);
        System.out.println();
        generation++;
    }

    private String getChild() {
        int newLen = current.length();
        if (rgen.nextDouble() <= MUTATION_RATE) {
            int tmp = newLen + randomMutation();
            newLen = tmp < 1 ? 1 : tmp;
        }
        StringBuilder child = new StringBuilder();
        for (int i = 0; i < newLen; i++) {
            char ch;
            if (i < current.length()) {
                ch = current.charAt(i);
                if (rgen.nextDouble() <= MUTATION_RATE) {
                    ch = mutate(ch);
                }
            } else {
                ch = getRandomChar();
            }
            child.append(ch);
        }
        return child.toString();
    }

    private char mutate(char ch) {
        int posInCharList = CHAR_LIST.indexOf(ch);
        posInCharList += randomMutation();
        while (posInCharList < 0) {
            posInCharList += NUM_CHARS;
        }
        while (posInCharList >= NUM_CHARS) {
            posInCharList -= NUM_CHARS;
        }
        return CHAR_LIST.charAt(posInCharList);
    }

    private int randomMutation() {
        int mutationSize = rgen.nextInt(MAX_MUTATION) + 1;
        return rgen.nextBoolean() ? mutationSize : -mutationSize;
    }

    private String getWinner() {
        int indexOfLowest = 0;
        int lowestScore = compareToTarget(litter[0]);
        for (int i = 1; i < litter.length; i++) {
            int score = compareToTarget(litter[i]);
            if (score < lowestScore) {
                indexOfLowest = i;
                lowestScore = score;
            }
        }
        return litter[indexOfLowest];
    }

    private int compareToTarget(String text) {
        int textLen = text.length();
        int targetLen = target.length();
        int score = 0;
        for (int i = 0; i < textLen && i < targetLen; i++) {
            int targetCharPos = CHAR_LIST.indexOf(target.charAt(i));
            int textCharPos = CHAR_LIST.indexOf(text.charAt(i));
            score += Math.abs(targetCharPos - textCharPos);
        }
        return score + (LEN_ERROR_PENALTY * Math.abs(textLen - targetLen));
    }

    public static void main(String[] args) {
        Darwin darwin = new Darwin();
        darwin.evolve("Methinks it is like a weasel.");
    }
}