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)));
}