// Natural selection. Created by Reinder Nijhoff 2019
// @reindernijhoff
//
// https://turtletoy.net/turtle/2f92cd6aa3
//
// A naive genetic algorithm is used to reconstruct the quote: "Natural selection is anything 
// but random." by Richard Dawkins.
///
// - The individuals of the first generation have random 'DNA' (41 characters).
// - The 'fittest' individual of each (generations/19)th generation is printed.
// - The fitness of an individual is given by the number of characters in its 'DNA' that match 
//   the quote.
// - The two fittest individuals of each generation reproduce using crossovers and mutations.
// 
// The chance that a fully random individual matches the quote is 1 : 95^41 ≈ 1 : 10^80.
// (10^80 is the estimated number of atoms in the known, observable universe)
//

const text = new Text();
const turtle = new Turtle(-92,-90);

const mutationRate = .02; // min=0.01, max=0.5, step=0.01
const populationSize = 2000; // min=10, max=2000, step=1
const generations = 40; // min=40, max=1000, step=10

const fittest = "Natural selection is anything but random.".split('');

//
// Individual
//
class Individual {
    constructor() { 
        this.dna = [];
        this.fitness = 0;
    }
    fillRandom() {
        fittest.forEach( (v,i) => {
            this.dna[i] = this.randomCharacter();
        } );
        this.calcFitness();
    }
    breed(p0, p1) {
        let s = Math.floor(Math.random()*(fittest.length-2))+1;
        // crossover
        if (Math.random() < .5) {
            this.dna = [...p0.dna.slice(0,s), ...p1.dna.slice(s)];
        } else {
            this.dna = [...p1.dna.slice(0,s), ...p0.dna.slice(s)];
        }
        // mutations
        this.dna.forEach( (v,i) => {
            if (Math.random() < mutationRate) {
                this.dna[i] = this.randomCharacter();
            }
        } );
        this.calcFitness();
    }
    calcFitness() {
        this.fitness = 0;
        fittest.forEach( (v,i) => {
            if (this.dna[i] == v) this.fitness++;
        });
    }
    randomCharacter() {
        return  String.fromCharCode(Math.floor(Math.random()*95)+32);
    }
}

//
// Generation
//
class Generation {
    constructor() {
        this.individuals = [];
        for (let i=0; i<populationSize; i++) {
            this.individuals[i] = new Individual();
        }
    }
    fillRandom() {
        this.individuals.forEach(i => i.fillRandom());
        return this.sortFittest();
    }
    breed(parentGeneration) {
        const p0 = parentGeneration.individuals[0];
        const p1 = parentGeneration.individuals[1];
        this.individuals.forEach(i => i.breed(p0, p1));
        return this.sortFittest();
    }
    sortFittest() {
        this.individuals.sort( (a, b) => b.fitness - a.fitness );
        return this;
    }
}

//
// Selection
//

let gen0 = new Generation().fillRandom();
let gen1 = new Generation();

function walk(i) {
    turtle.jump(-92, -90+i*10);
    text.print(turtle, gen0.individuals[0].dna.join(''),.21);
    
    for (let i=0; i<generations/40; i++) {
        gen1.breed(gen0)
        gen0.breed(gen1)
    }
    return i<18;
}

////////////////////////////////////////////////////////////////
// Text utility code - https://turtletoy.net/turtle/1713ddbe99
// !! MODIFIED TO MAKE IT MONOSPACED 
////////////////////////////////////////////////////////////////

function Text() {
    class Text {
        print (t, str, scale) {
            t.radians();
            let pos = [t.x(), t.y()], h = t.h(), o = pos;
            str.split('').map(c => {
                const i = c.charCodeAt(0) - 32;
                if (i < 0 ) {
                    pos = o = this.rotAdd([0, 48*scale], o, h);
                } else if (i > 96 ) {
                    pos = this.rotAdd([16*scale, 0], o, h);
                } else {
                    const d = dat[i], paths = d[2];
                    paths.map( p => {
                        t.up();
                    	p.map( s=> {
                        	t.goto(this.rotAdd([s[0]*scale , s[1]*scale], pos, h));
                        	t.down();
                        });
                    });
                    pos = this.rotAdd([22*scale, 0], pos, h);
                }
            });
        }
        rotAdd (a, b, h) {
            return [Math.cos(h)*a[0] - Math.sin(h)*a[1] + b[0], 
                    Math.cos(h)*a[1] + Math.sin(h)*a[0] + b[1]];
        }
    }
    
const dat = ('br>eoj^jl<jqirjskrjq>brf^fe<n^ne>`ukZdz<qZjz<dgrg<cmqm>`thZhw<lZlw<qao_l^h^e_caccdeefg'+
'gmiojpkqmqporlshsercp>^vs^as<f^h`hbgdeeceacaab_d^f^h_k`n`q_s^<olmmlolqnspsrrspsnqlol>]wtgtfsereqfph'+
'nmlpjrhsdsbraq`o`makbjifjekckaj_h^f_eaecffhimporqssstrtq>eoj`i_j^k_kajcid>cqnZl\\j_hcghglhqjulxnz>c'+
'qfZh\\j_lcmhmllqjuhxfz>brjdjp<egom<ogem>]wjajs<ajsj>fnkojpiojnkokqis>]wajsj>fnjniojpkojn>_usZaz>`ti'+
'^f_dbcgcjdofrisksnrpoqjqgpbn_k^i^>`tfbhak^ks>`tdcdbe`f_h^l^n_o`pbpdofmicsqs>`te^p^jfmfogphqkqmppnrk'+
'shserdqco>`tm^clrl<m^ms>`to^e^dgefhekenfphqkqmppnrkshserdqco>`tpao_l^j^g_ebdgdlepgrjsksnrppqmqlping'+
'kfjfggeidl>`tq^gs<c^q^>`th^e_dadceegfkgnhpjqlqopqorlshserdqcocldjfhigmfoepcpao_l^h^>`tpeohmjjkikfjd'+
'hcecddaf_i^j^m_oapepjoomrjshserdp>fnjgihjikhjg<jniojpkojn>fnjgihjikhjg<kojpiojnkokqis>^vrabjrs>]wag'+
'sg<amsm>^vbarjbs>asdcdbe`f_h^l^n_o`pbpdofngjijl<jqirjskrjq>]xofndlcicgdfeehekfmhnknmmnk<icgefhfkgmh'+
'n<ocnknmpnrntluiugtdsbq`o_l^i^f_d`bbad`g`jambodqfrislsorqqrp<pcokompn>asj^bs<j^rs<elol>_tc^cs<c^l^o'+
'_p`qbqdpfoglh<chlhoipjqlqopqorlscs>`urcqao_m^i^g_eadccfckdnepgrismsorqprn>_tc^cs<c^j^m_oapcqfqkpnop'+
'mrjscs>`sd^ds<d^q^<dhlh<dsqs>`rd^ds<d^q^<dhlh>`urcqao_m^i^g_eadccfckdnepgrismsorqprnrk<mkrk>_uc^cs<'+
'q^qs<chqh>fnj^js>brn^nnmqlrjshsfreqdndl>_tc^cs<q^cl<hgqs>`qd^ds<dsps>^vb^bs<b^js<r^js<r^rs>_uc^cs<c'+
'^qs<q^qs>_uh^f_daccbfbkcndpfrhslsnrppqnrkrfqcpan_l^h^>_tc^cs<c^l^o_p`qbqepgohlici>_uh^f_daccbfbkcnd'+
'pfrhslsnrppqnrkrfqcpan_l^h^<koqu>_tc^cs<c^l^o_p`qbqdpfoglhch<jhqs>`tqao_l^h^e_caccdeefggmiojpkqmqpo'+
'rlshsercp>brj^js<c^q^>_uc^cmdpfrisksnrppqmq^>asb^js<r^js>^v`^es<j^es<j^os<t^os>`tc^qs<q^cs>asb^jhjs'+
'<r^jh>`tq^cs<c^q^<csqs>cqgZgz<hZhz<gZnZ<gznz>cqc^qv>cqlZlz<mZmz<fZmZ<fzmz>brj\\bj<j\\rj>asazsz>fnkc'+
'ieigjhkgjfig>atpeps<phnfleiegfehdkdmepgrislsnrpp>`sd^ds<dhffhekemfohpkpmopmrkshsfrdp>asphnfleiegfeh'+
'dkdmepgrislsnrpp>atp^ps<phnfleiegfehdkdmepgrislsnrpp>asdkpkpiognfleiegfehdkdmepgrislsnrpp>eqo^m^k_j'+
'bjs<gene>atpepuoxnylzizgy<phnfleiegfehdkdmepgrislsnrpp>ate^es<eihfjemeofpips>fni^j_k^j]i^<jejs>eoj^'+
'k_l^k]j^<kekvjyhzfz>are^es<oeeo<ikps>fnj^js>[y_e_s<_ibfdegeifjijs<jimfoeretfuius>ateees<eihfjemeofp'+
'ips>atiegfehdkdmepgrislsnrppqmqkphnfleie>`sdedz<dhffhekemfohpkpmopmrkshsfrdp>atpepz<phnfleiegfehdkd'+
'mepgrislsnrpp>cpgegs<gkhhjfleoe>bsphofleieffehfjhkmlompopporlsisfrep>eqj^jokrmsos<gene>ateeeofrhsks'+
'mrpo<peps>brdejs<pejs>_ubefs<jefs<jens<rens>bseeps<pees>brdejs<pejshwfydzcz>bspees<eepe<esps>cqlZj['+
'i\\h^h`ibjckekgii<j[i]i_jakbldlfkhgjkllnlpkrjsiuiwjy<ikkmkojqirhthvixjylz>fnjZjz>cqhZj[k\\l^l`kbjci'+
'eigki<j[k]k_jaibhdhfihmjilhnhpirjskukwjy<kkimiojqkrltlvkxjyhz>^vamakbhdgfghhlknlplrksi<akbidhfhhill'+
'nmpmrlsisg>brb^bscsc^d^dsese^f^fsgsg^h^hsisi^j^jsksk^l^lsmsm^n^nsoso^p^psqsq^r^rs').split('>').map(
    r=> { return [r.charCodeAt(0)-106,r.charCodeAt(1)-106, r.substr(2).split('<').map(a => {const ret 
    = []; for (let i=0; i<a.length; i+=2) {ret.push(a.substr(i, 2).split('').map(b => b.charCodeAt(0)
    -106));} return ret; })]; });

    return new Text();
}