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