import std.stdio;
import std.algorithm;
import std.random;
import std.array;
import std.math;

struct city{
    int x;
    int y;
}

struct chromosome{
    city[] dna;
}

chromosome[2] crossOver(chromosome mother, chromosome father){
    assert(mother.dna.length==father.dna.length);

    foreach(a;mother.dna)
        assert(mother.dna.count(a)==father.dna.count(a));

    //we map 1 dna unit from the mother to a corresponding unit of the father (and vice versa)
    // 4 1 2 3 5
    // 5 3 1 2 4
    //
    // if we map 1 => 3
    // 4 3 2 1 5
    // 5 1 3 2 4

    int mapIndex=uniform(0,mother.dna.length);

    auto point1=mother.dna.dup[mapIndex];
    auto point2=father.dna.dup[mapIndex];

    //we're mapping point1 to point1
    swap(mother.dna[mother.dna.countUntil(point1)],mother.dna[mother.dna.countUntil(point2)]);
    swap(father.dna[father.dna.countUntil(point1)],father.dna[father.dna.countUntil(point2)]);

    return [mother,father];
}

chromosome mutate(chromosome victim){
    int from=uniform(0,victim.dna.length);
    int to=uniform(0,victim.dna.length);
    swap(victim.dna[from],victim.dna[to]);
    return victim;
}

chromosome[] reproduce(chromosome mother,chromosome father){
    //we reproduce
    //mother's and father's dna are preserved because they contain a good solution
    //we also add a mutation of mother/father
    //a crossing over of mother/father
    //and a crossing over + mutation
    chromosome[] returnvalue;
    returnvalue~=mother;
    returnvalue~=father;

    returnvalue~=mutate(mother);
    returnvalue~=mutate(father);

    chromosome[] crossedOver=crossOver(mother,father);
    chromosome[] crossedOverAndMutated=array(map!(x => mutate(x))(crossedOver));

    returnvalue~=crossedOver;
    returnvalue~=crossedOverAndMutated;

    return returnvalue;
}
void main(){
    city[] cities=[city(20,0),city(50,50),city(75,30),city(0,10),city(25,25),city(10,65)];
    chromosome[] workers;
    while(workers.length<60){
        randomShuffle(cities);
        if(!canFind(workers,chromosome(cities)))
            workers~=chromosome(cities.dup);
    }

    bool fitnessCompare(chromosome first,chromosome second){
        return fitness(first)>fitness(second);
    }

    while(true){
        workers=array(sort!(fitnessCompare)(workers));

        writeln(workers[0]);
        stdout.flush();

        chromosome[] newWorkers;
        for(int x=0;x<10;x+=2)
            newWorkers~=reproduce(workers[x],workers[x+1]);

        workers=newWorkers;
    }

}

float fitness(chromosome victim){
    city[] cities=victim.dna;

    //we need to start from home and return to home
    cities=city(0,0) ~ cities;
    cities~=city(0,0);

    float travelled=0f;
    for(int x=0;x<cities.length-1;x++)
        travelled+=distance(cities[x],cities[x+1]);
    writeln(100/travelled);
    return 100/travelled;
}

float distance(city from,city to){
    return sqrt(cast(float)(pow(to.x-from.x,2) + pow(to.y-from.y,2)));
}