/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 + Genetic Algorithm Maze Test                            +
 + Author: Matt P.                                        +
 + Version: 0.5                                           +
 +                                                        +
 + Runs a genetic algorithm test using a maze generation  +
 + and guessing algorithm.                                +
 +                                                        +
 + Usage: ga_maze [options]                               +
 + Options:                                               +
 + -h                                                     +
 +      Prints this information.                          +
 + -v                                                     +
 +      Turns on verbose output.                          +
 + -m float                                               +
 +      Specifies the mutation rate for each generation.  +
 +      Default: 0.05                                     +
 +                                                        +
 + -d float                                               +
 +      Specifies the survival rate for each generation.  +
 +      Default: 0.5                                      +
 +                                                        +
 + -p integer                                             +
 +      Specifies the population for each generation.     +
 +      Default: 1000                                     +
 +                                                        +
 + -l integer                                             +
 +      Specifies the maximum length of the solution code.+
 +      Default: 20                                       +
 +                                                        +
 + -r integer                                             +
 +      Specifies the number of times to repeat the test. +
 +      Default: 20                                       +
 +                                                        +
 + -c char                                                +
 +      Specifies the crossover type                      +
 +       s / 1 - One point crossover                      +
 +       t / 2 - Two point crossover                      +
 +       u / 3 - Uniform crossover                        +
 +      Default: s                                        +
 +                                                        +
 + -s integer integer                                     +
 +      Specifies the size of the maze                    +
 +      Default: 7 7                                      +
 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/


module ga_maze;

import aid.ga;
import tango.math.Random;
import tango.math.Math;
import tango.io.Stdout;
//import tango.text.String;
import Float = tango.text.convert.Float;
import Integer = tango.text.convert.Integer;

import bcd.sys.times;

char[] chars = "NESW";

//int numChars = 20;
int stringLen = 28;

bool[][] maze;
int w = 7;
int h = 7;

double average(double[] array){
	double avg = 0;
	foreach (double v; array)
		avg += v;
	avg /= array.length;
	return avg;
}

double stdDev(double[] array){
	double avg = average(array);
	double stddev = 0;
	foreach (double v; array){
		stddev += (v - avg) * (v - avg);
	}
	stddev = sqrt(stddev/array.length);
	return stddev;
}

bool[][] generateMaze(uint width, uint height){
	bool[][] maze;
	
	maze.length = width;
	
	for (auto i = 0; i < width; i++){
		maze[i].length = height;
	}
	
	bool rowStart = true;
	bool vertical;
	for (auto i = 1; i < width; i+=2){
		vertical = rowStart;
		rowStart = !rowStart;
		
		for (auto j = 1; j < height; j+=2){
			maze[i][j] = true;
			if (vertical)
				maze[i + ((Random.shared.next(2)-1)?-1:1)][j] = true;
			else
				maze[i][j + ((Random.shared.next(2)-1)?-1:1)] = true;
			vertical = !vertical;
		}
	}
	
	return maze;
}

void printMaze(bool[][] m, bool[][] trail = null,char e = '.', char f = 'X', bool outline = true){
	if (outline){
		Stdout("+");
		for (auto j = 0; j < m[0].length; j++){
			Stdout("-");
		}
		Stdout("+").newline;
	}
	
	for (auto i = 0; i < m.length; i++){
		if (outline) Stdout("|");
		for (auto j = 0; j < m[i].length; j++){
			if(m[i][j]) Stdout(""~f);
			else if(trail && trail[i][j]) Stdout("+");
			else Stdout(""~e);
		}
		if (outline) Stdout("|").newline;
	}
	if (outline){
		Stdout("+");
		for (auto j = 0; j < m[0].length; j++){
			Stdout("-");
		}
		Stdout("+").newline;
	}
}

/++++++++++++++++++++++++++ Foo ++++++++++++++++++++++++++++++/

class Foo {
	int count = 0;
	public double calculateFitness(char[] gene){
		
		bool canMove(int x, int y){
			return ((x >= 0) && (x < w) && (y >= 0) && (y < h) && (!maze[x][y]));
		}
		
		double square(int v){
			return v*v;
		}
		
		/*bool[][] trail;
		
		trail.length = w;
		for(uint i = 0; i < w; i++){
			trail[i].length = h;
		}*/
		
		double fitness=0;
		int x = 0;
		int y = 0;
		for (uint i = 0; i < gene.length; i++){
			//trail[x][y] = true;
			//Stdout(""~gene[i]);
			if(gene[i] == 'N' && canMove(x,y-1)) y--;
			if(gene[i] == 'E' && canMove(x+1,y)) x++;
			if(gene[i] == 'S' && canMove(x,y+1)) y++;
			if(gene[i] == 'W' && canMove(x-1,y)) x--;
			
			if (x == w-1 && y == h-1){
				return 100;
			}
		}
		
		fitness = 100 - sqrt(square(x-(w-1)) + square(y-(h-1)));
		/*if(count < 20){
			Stdout.format("{} {:.4}",gene,fitness).newline;
			//printMaze(maze,trail);
			count++;
		}*/
		return fitness;
	}
	
	public char[] getRandomGenotype(){
		char[] t;
		t.length = stringLen;
		for (int i = 0; i < stringLen; i++){
			t[i] = chars[Random.shared.next(chars.length)];
		}
		return t;
	}
	
	public char getRandomChar(uint index){
		return chars[Random.shared.next(chars.length)];
	}
}

/++++++++++++++++++++++ End Foo ++++++++++++++++++++++++++++++/

void usage(){
	auto s = 
		"Usage: ga_maze [options]                               \n"
		"Options:                                               \n"
		"-h                                                     \n"
		"     Prints this information.                          \n"
		"-v                                                     \n"
		"     Turns on verbose output.                          \n"
		"-m float                                               \n"
		"     Specifies the mutation rate for each generation.  \n"
		"     Default: 0.05                                     \n"
		"                                                       \n"
		"-d float                                               \n"
		"     Specifies the survival rate for each generation.  \n"
		"     Default: 0.5                                      \n"
		"                                                       \n"
		"-p integer                                             \n"
		"     Specifies the population for each generation.     \n"
		"     Default: 1000                                     \n"
		"                                                       \n"
		"-l integer                                             \n"
		"     Specifies the maximum length of the solution code.\n"
		"     Default: 20                                       \n"
		"                                                       \n"
		"-n integer                                             \n"
		"     Specifies how many possibilities there are for    \n"
		"     each character of the code string.                \n"
		"     Default: 20                                       \n"
		"                                                       \n"
		"-r integer                                             \n"
		"     Specifies the number of times to repeat the test. \n"
		"     Default: 20                                       \n"
		"                                                       \n"
		"-c char                                                \n"
		"     Specifies the crossover type                      \n"
		"      s / 1 - One point crossover                      \n"
		"      t / 2 - Two point crossover                      \n"
		"      u / 3 - Uniform crossover                        \n"
		"     Default: s                                          ";
	Stdout(s).newline;
}

void main(char[][] args){
	Foo f = new Foo();
	GeneticAlgorithm ga = new GeneticAlgorithm();
	ga.calculateFitness = &f.calculateFitness;
	ga.getRandomGenotype = &f.getRandomGenotype;
	ga.getRandomChar = &f.getRandomChar;
	ga.fitnessThreshold = 100;
	int rep = 20;
	bool dotime = true;
	
	
	for (auto i = 1; i < args.length; i++){
		char[] arg = args[i];
		switch (arg){
			case "-h":
				usage();
				return;
			case "-m":
				ga.mutationRate = Float.parse(args[++i]);
				break;
			case "-d":
				ga.survivalRate = Float.parse(args[++i]);
				break;
			case "-p":
				ga.startPopulation = Integer.parse(args[++i]);
				break;
			case "-l":
				stringLen = Integer.parse(args[++i]);
				//ga.fitnessThreshold = stringLen;
				break;
			case "-r":
				rep = Integer.parse(args[++i]);
				break;
			case "-v":
				ga.verbose = true;
				break;
			case "-s":
				w = Integer.parse(args[++i]);
				h = Integer.parse(args[++i]);
				stringLen = 2*(w+h);
				break;
			case "-c":
				auto t  = args[++i];
				switch (t){
					case "s","1":
						ga.crossoverType = 1;
						break;
					case "t","2":
						ga.crossoverType = 2;
						break;
					default:
						ga.crossoverType = 3;
				}
				break;
			case "-b":
				ga.bailout = Integer.parse(args[++i]);
				break;
			case "-t":
				dotime = false;
				break;
			default:
				Stdout.format("Unknown parameter: {}",arg).newline;
				usage();
				return;
		}
	}
	
	double[] time;
	double[] gens;
	long start,end;
	double generations;
	
	for(auto i = 0; i < rep; i++){
		maze=generateMaze(w,h);
		
		if(dotime) start = iutime();
		generations = ga.run();
		if(dotime) end = iutime() - start;
		
		if(dotime) time ~= end;
		gens ~= generations;
	}
	
	if(dotime) Stdout.format("{0}, {1:.5}, {2}, {3:.5}", average(gens),stdDev(gens),average(time),stdDev(time)).newline;
	else Stdout.format("{0}, {1:.5}", average(gens),stdDev(gens)).newline; //", {2}, {3:.5}" ,average(time),stdDev(time)
}