# HG changeset patch
# User revcompgeek
# Date 1204597690 25200
# Node ID 4b2e8e8a633e2a230bc01fa8b98ac460e4957d4c

Repository setup.

diff -r 000000000000 -r 4b2e8e8a633e branches/.hidden
diff -r 000000000000 -r 4b2e8e8a633e downloads/.hidden
diff -r 000000000000 -r 4b2e8e8a633e tags/.hidden
diff -r 000000000000 -r 4b2e8e8a633e trunk/aid/astar.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/aid/astar.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,42 @@
+/*+++++++++++++++++++++++++++++++++++++++++++
+ +               A* algorithm               +
+ +             By Matt Peterson             +
+ +++++++++++++++++++++++++++++++++++++++++++*/
+
+module aid.astar;
+
+import mintl.arrayheap;
+
+class Node(DATA) {
+    int xloc;
+    int yloc;
+    int fitness;
+    private int fitg;
+    Node* parent = null;
+    DATA data;
+    
+    this(DATA d, int g){
+        data = d;
+        fitness = g;
+        fitg = g;
+    }
+    this(DATA d, int g, Node* p){
+        data = d;
+        parent = p;
+        if(parent) fitness = parent.fitness + g;
+        fitg = g;
+    }
+    int opCmp(Node other){
+        return this.fitness - other.fitness;
+    }
+}
+
+class AStar(DATA) {
+    alias Node!(DATA) Node;
+    alias DATA[] delegate(DATA) getChildren;
+    ArrayHeap!(Node) openList;
+    ArrayHeap!(Node) closedList;
+    DATA[] run(DATA start){
+        
+    }
+}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/aid/containers/heap.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/aid/containers/heap.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,282 @@
+/*++++++++++++++++++++++++++++++++++++++++++++
+ +              Heap sorted array            +
+ +               By Matt Peterson            +
+ ++++++++++++++++++++++++++++++++++++++++++++*/
+
+/*class Heap(Value) {
+    Value[] array;
+    int tail;
+    public int capacity(){
+        // This returns the current capacity of the heap.
+        return array.length;
+    }
+    public int size(){
+        // This returns the number of items in the heap.
+        return tail;
+    }
+    
+    void capacity(int c){
+        // This sets the capacity to c.
+        if(c < tail) c = tail;
+        array.length = c;
+    }
+    void insert(Value v){
+        // Inserts a value and sorts it to it's correct position.
+        if(tail >= size()) capacity(size()+10);
+        array[++tail] = v;
+        int i = tail;
+        while(i > 0 && array[i/2] > array[i]){
+            array[i] = array[i/2];
+            array[i/2] = v;
+            i /= 2;
+        }
+    }
+    Value removeHead(){
+        Value ret = array[0];
+        array[0] = array[tail];
+        tail--;
+        i = 0;
+        while(
+    }
+    
+}*/
+
+struct Heap(Value, Alloc = GCAllocator) {
+
+  alias ArrayHeap   ContainerType;
+  alias Value       ValueType;
+  alias size_t      IndexType;
+
+  Value[] data;   ///< backing array. null by default, grows as needed
+
+  invariant {
+    assert( tail <= data.length );
+  }
+
+  /** signature for a custom comparison function */
+  alias int delegate(Value* a, Value* b) CompareFcn;
+
+  /** Set custom comparison function.   */
+  void compareFcn(CompareFcn cmp) {
+    cmpFcn = cmp;
+  }
+
+  /** Get heap contents as dynamic array slice of backing array.   */
+  Value[] values() {
+    return data[0..tail];
+  }
+
+  /** Adds an item to the heap. Increases capacity if needed.   */
+  void addTail(Value v) {
+    capacity(tail+1);
+    data[tail++] = v;
+    fixupTail();
+  }
+
+  /** Removes and returns the head item of the heap. If the target
+   * heap is empty an IndexOutOfBoundsException is thrown unless
+   * version=MinTLNoIndexChecking is set.
+   */
+  Value takeHead() {
+    version (MinTLNoIndexChecking) {
+      // no error checking
+    } else {
+      if (tail == 0)
+	throw new IndexOutOfBoundsException();
+    }
+    Value val = data[0];
+    data[0] = data[--tail];
+    data[tail] = Value.init;
+    fixupHead();
+    return val;
+  }
+
+  /** Removes the head item of the heap.   */
+  void removeHead() {
+    version (MinTLNoIndexChecking) {
+      // no error checking
+    } else {
+      if (tail == 0)
+	throw new IndexOutOfBoundsException();
+    }
+    data[0] = data[--tail];
+    data[tail] = Value.init;
+    fixupHead();
+  }
+
+  /** Get the length of heap.   */
+  size_t length() {
+     return tail;
+  }
+
+  /** Test if container is empty.   */
+  bool isEmpty() { 
+    return tail == 0;
+  }
+
+  /** Clear all contents. */
+  void clear() {
+    static if (is(Alloc == GCAllocator)) {
+    } else {
+      if (data.ptr)
+	Alloc.gcFree(data.ptr);
+    }
+    *this = ArrayHeap.init;
+  }
+
+  /** Get the nth item in the heap from head.   */
+  Value opIndex(size_t n) {
+    return data[n];
+  }
+
+  /** Get a pointer to the nth item in the heap   */
+  Value* lookup(size_t n) {
+    return &data[n];
+  }
+
+  /** Set the nth item in the heap.   */
+  void opIndexAssign(Value val, size_t n) {
+    data[n] = val;
+  }
+
+  /** Duplicates a heap.   */
+  ArrayHeap dup() {
+    ArrayHeap res;
+    static if (is(Alloc == GCAllocator)) {
+      res.data = data.dup;
+    } else {
+      Value* p = cast(Value*)Alloc.malloc(data.length * Value.sizeof);
+      res.data = p[0 .. data.length];
+      res.data[] = data[];
+    }
+    res.tail = tail;
+    res.cmpFcn = cmpFcn;
+    return res;
+  }
+
+  /** Test for equality of two heaps.   */
+  int opEquals(ArrayHeap c) {
+    size_t len = length;
+    if (len !is c.length)
+      return 0;
+    size_t a,b;
+    a = 0;
+    b = 0;
+    TypeInfo ti = typeid(Value);
+    for (size_t k = 0; k < len; k++) {
+      if (!ti.equals(&data[a],&c.data[b]))
+	return 0;
+      a++;
+      b++;
+    }
+    return 1;
+  }
+
+  /** Compare two heaps.   */
+  int opCmp(ArrayHeap c) {
+    size_t len = length;
+    if (len > c.length)
+      len = c.length;
+    size_t a,b;
+    a = 0;
+    b = 0;
+    TypeInfo ti = typeid(Value);
+    for (size_t k = 0; k < len; k++) {
+      int cmp = ti.compare(&data[a],&c.data[b]);
+      if (cmp)
+	return cmp;
+      a++;
+      b++;
+    }
+    return cast(int)length - cast(int)c.length;
+  }
+
+  /** Returns a short string representation of the heap. */
+  char[] toString() {
+    return "[ArrayHeap length " ~ std.string.toString(tail) ~ "]";
+  }
+
+  /** Iterates over the heap from head to tail calling delegate to
+   * perform an action. The value is passed to the delegate.
+   */
+  int opApplyNoKey(int delegate(inout Value x) dg){
+    int res = 0;
+    for (size_t k=0; k < tail; k++) {
+      res = dg(data[k]);
+      if (res) break;
+    }
+    return res;
+  }
+
+  /** Iterates over the heap from head to tail calling delegate to
+   * perform an action. The index from 0 and the value are passed
+   * to the delegate.
+   */
+  int opApplyWithKey(int delegate(inout size_t n, inout Value x) dg){
+    int res = 0;
+    for (size_t k=0; k < tail; k++) {
+      res = dg(k,data[k]);
+      if (res) break;
+    }
+    return res;
+  }
+
+  alias opApplyNoKey opApply;
+  alias opApplyWithKey opApply;
+
+  /** Ensure the minimum capacity of heap.   */
+  void capacity(size_t cap) {
+    if (cap > data.length) {
+      cap = (cap+1)*2;
+      static if (is(Alloc == GCAllocator)) {
+	data.length = cap;
+      } else {
+	Value* p = data.ptr;
+	p = cast(Value*)Alloc.gcRealloc(p,cap*Value.sizeof);
+	p[data.length .. cap] = Value.init;
+	data = p[0 .. cap];
+      }
+    }
+  }
+
+  // Helper functions
+
+  // enforce heap invariant after a new head
+  private void fixupHead() {
+    size_t n = 0;
+    TypeInfo ti = typeid(Value);
+    if (cmpFcn is null) {
+      cmpFcn = cast(CompareFcn)&ti.compare;
+    }
+    for (;;) {
+      size_t n1 = 2*n+1;
+      if (n1 >= tail) break;
+      if ((n1 != tail-1) && (cmpFcn(&data[n1],&data[n1+1]) < 0))
+	n1++;
+      if (cmpFcn(&data[n],&data[n1]) < 0) {
+	ti.swap(&data[n],&data[n1]);
+	n = n1;
+      } else {
+	break;
+      }
+    }
+  }
+
+  // enforce heap invariant after a new tail
+  private void fixupTail() {
+    size_t n = tail-1;
+    TypeInfo ti = typeid(Value);
+    if (cmpFcn is null) {
+      cmpFcn = cast(CompareFcn)&ti.compare;
+    }
+    size_t n1 = (n-1)>>1;
+    while ((n > 0) && (cmpFcn(&data[n],&data[n1]) > 0)) {
+      ti.swap(&data[n],&data[n1]);
+      n = n1;
+      n1 = (n-1)>>1;
+    }
+  }
+
+  private CompareFcn cmpFcn;
+  private size_t tail;
+}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/aid/ga.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/aid/ga.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,226 @@
+/***********************************
+ *    Provides a set of classes    *
+ *  for using Genetic Algorithms.  *
+ *                                 *
+ * Author: Matt P.                 *
+ * Version: 0.1                    *
+ ***********************************/
+
+module aid.ga;
+
+import tango.math.Random;
+import tango.io.Stdout;
+
+void removeIndex(Gene[] array, uint index){
+	//scope(failure) Stdout.format("E: removeIndex {}", index).newline;
+	if (index == 0)
+		array = array[1..$];
+	else if (index == array.length)
+		array = array[0..$-1];
+	else
+		array = array[0..index-1] ~ array[index+1..$];
+}
+
+class Gene {
+	char[] geneSequence;
+	private double fit = -1; // Save the fitness value so that it doesn't have to be calculated more than once.
+	private GeneticAlgorithm* ga;
+	
+	this(GeneticAlgorithm* a){
+		ga = a;
+	}
+	
+	this(Gene g, GeneticAlgorithm* a){
+		scope(failure) Stdout("E: Gene clone").newline;
+		geneSequence = g.geneSequence.dup;
+		this(a);
+	}
+	
+	double fitness(){ // Get property
+		if (fit == -1){
+			fit = ga.calculateFitness(geneSequence);
+		}
+		return fit;
+	}
+	
+	Gene[] crossover(Gene other){
+		Gene gene1 = new Gene(this,ga),gene2 = new Gene(other,ga);
+		auto r = Random.shared;
+		auto len = geneSequence.length;
+		char[] temp;
+		
+		//scope(failure) Stdout.format("E: crossover {}").newline;
+		
+		if (ga.crossoverType == 2){
+			//Stdout("1").flush;
+			uint point1 = r.next(len-2)+1;
+			uint point2 = r.next(len-2)+1;
+			while (point1 == point2)
+				point2 = r.next(len);
+			if (point2 < point1){
+				scope uint t = point1;
+				point1 = point2;
+				point2 = t;
+			}
+			//Stdout("2").newline;
+			scope(failure) Stdout.format("Ed: {},{}",point1,point2).newline;
+			//Stdout(point1)(", ")(point2).newline;
+			temp = gene1.geneSequence[point1..point2].dup;
+			//Stdout("4").flush;
+			gene1.geneSequence[point1..point2] = gene2.geneSequence[point1..point2].dup;
+			//Stdout("5").flush;
+			gene2.geneSequence[point1..point2] = temp;
+			//Stdout("6").flush;
+		} else if (ga.crossoverType == 1) {
+			uint point = r.next(len-2)+1;
+			temp = gene1.geneSequence[point..$].dup;
+			gene1.geneSequence[point..$] = gene2.geneSequence[point..$];
+			gene2.geneSequence[point..$] = temp;
+		} else { // Uniform crossover
+			for (int i = 0; i < len / 2; i++){
+				uint point = r.next(len);
+			
+				auto t = gene1.geneSequence[point];
+				gene1.geneSequence[point] = gene2.geneSequence[point];
+				gene2.geneSequence[point] = t;
+			}
+		}
+		return [gene1,gene2];
+	}
+	
+	Gene mutate(){
+		Gene g = new Gene(this,ga);
+		uint i = Random.shared.next(g.geneSequence.length);
+		g.geneSequence[i] = ga.getRandomChar(i);
+		return g;
+	}
+}
+
+class Generation {
+	private Gene[] genes;
+	private uint population;
+	private GeneticAlgorithm* ga;
+	
+	public this(GeneticAlgorithm* g, bool generate = false){
+		ga = g;
+		population = ga.startPopulation;
+		if (generate) generateGenes();
+	}
+	
+	public this(Generation gen){
+		genes = gen.genes;
+		ga = gen.ga;
+	}
+	
+	public Generation evolve(){
+		Generation newGen = new Generation(ga);
+		
+		// Use tournament selection to create a new Generation
+		uint livingPop = cast(uint)(population * ga.survivalRate);
+		newGen.population = population;
+		newGen.genes.length = population;
+		for (auto i = 0; i < livingPop; i++){
+			uint t = tournamentSelect();
+			newGen.genes[i] = genes[t];
+			//genes.removeIndex(t);
+		}
+		
+		// Cross over the left over genes
+		for (auto i = livingPop; i < population; i+=2){
+			uint i1 = tournamentSelect(), i2 = tournamentSelect();
+			while (i1 == i2)
+				i2 = tournamentSelect();
+			Gene g1 = genes[i1], g2 = genes[i2];
+			
+			Gene[] gs = g1.crossover(g2);
+
+			newGen.genes[i..i+2] = gs[];
+			if (ga.deleteOnCrossover){
+				genes.removeIndex(i1);
+				genes.removeIndex(i2);
+			}
+		}
+		
+		// Mutate a small amount of genes
+		for (auto i = 0; i < population * ga.mutationRate; i++){
+			uint index = Random.shared.next(newGen.genes.length);
+			newGen.genes[index] = newGen.genes[index].mutate();
+		}
+		
+		return newGen;
+	}
+	
+	private void generateGenes(){
+		scope(failure) Stdout("E: generateGenes").newline;
+		genes.length = population;
+		for (uint i = 0; i < population; i++){
+			Gene t = new Gene(ga);
+			t.geneSequence = ga.getRandomGenotype();
+			genes[i] = t;
+		}
+	}
+		
+	private uint tournamentSelect(){
+		Gene[4] gens;
+		uint[4] indices;
+		scope(failure) Stdout("E: tournamentSelect").newline;
+		for (uint i = 0; i < 4; i++){
+			indices[i] = Random.shared.next(genes.length);
+			gens[i] = genes[indices[i]];
+		}
+		double max = gens[0].fitness;
+		uint index = indices[0];
+		foreach (i,g; gens){
+			if (g.fitness > max){
+				max = g.fitness;
+				index = indices[i];
+			}
+		}
+		return index;
+	}
+}
+
+class GeneticAlgorithm {
+	public double delegate(char[]) calculateFitness; // Set these before you do anything with the library
+	public char[] delegate() getRandomGenotype;
+	public char delegate(uint index) getRandomChar;
+	public double survivalRate = 0.5;
+	public double mutationRate = 0.05;
+	public bool deleteOnCrossover = true;
+	public int crossoverType = 1; // 1 point crossover
+	public uint startPopulation = 1000;
+	public bool verbose = false;
+	public uint bailout = 1000;
+	
+	public double fitnessThreshold;
+	
+	public uint run(){
+		//Stdout("t").flush;
+		Generation currGen = new Generation(&this,true);
+		//Stdout("test").flush;
+		bool stop = false;
+		uint generation = 1;
+		double average;
+		double max;
+		while (true){
+			if (verbose) max = 0;
+			if (verbose) average = 0;
+			foreach (Gene g; currGen.genes){
+				if (verbose) average += g.fitness;
+				
+				if (verbose) if (g.fitness > max) max = g.fitness;
+				if (g.fitness >= fitnessThreshold){
+					stop = true;
+				}
+			}
+			if (verbose) average /= currGen.genes.length;
+			if (verbose) Stdout.formatln("Gen: {} Avg: {:.4}  Max: {:.4}",generation, average, max);
+			if (stop || generation >= bailout) return generation;
+			currGen = currGen.evolve();
+			generation++;
+		}
+	}
+}
+
+
+
diff -r 000000000000 -r 4b2e8e8a633e trunk/aid/maze/generate.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/aid/maze/generate.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,18 @@
+module ai.maze.generate;
+
+import tango.math.Random;
+
+class MazeGenerator {
+public:
+	MazeCell[][] generate(uint w, uint h){
+		Random r = Random.shared;
+		MazeCell[][] maze = new MazeCell[w][h];
+		uint x = r.next(w);
+		uint y = r.next(h);
+		
+	}
+}
+
+struct MazeCell {
+	bool n=true,w=true,s=true,e=true,visited=false;
+}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/bcd/sys/times.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/bcd/sys/times.cc	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,67 @@
+/* THIS FILE GENERATED BY bcd.gen */
+#include <stdlib.h>
+#include <string.h>
+#include "../bind.h"
+#include "times.h"
+extern "C" {
+void _BCD_delete_3tms( *This) {
+delete This;
+}
+typedef long unsigned int _BCD__67___darwin_clock_t;
+typedef _BCD__67___darwin_clock_t _BCD__6_clock_t;
+typedef  * _BCD__8___darwin_ucontext64_t;
+typedef  * _BCD__10___darwin_ucontext_t;
+typedef  * _BCD__12___darwin_stack_t;
+typedef unsigned char _BCD_array__13[16];
+typedef _BCD_array__13 _BCD__14___darwin_uuid_t;
+typedef unsigned int _BCD__83___uint32_t;
+typedef _BCD__83___uint32_t _BCD__16___darwin_useconds_t;
+typedef _BCD__83___uint32_t _BCD__17___darwin_uid_t;
+typedef int _BCD__84___int32_t;
+typedef _BCD__84___int32_t _BCD__19___darwin_suseconds_t;
+typedef _BCD__83___uint32_t _BCD__20___darwin_sigset_t;
+typedef  * _BCD__22___darwin_pthread_t;
+typedef  * _BCD__24___darwin_pthread_rwlockattr_t;
+typedef  * _BCD__26___darwin_pthread_rwlock_t;
+typedef  * _BCD__28___darwin_pthread_once_t;
+typedef  * _BCD__30___darwin_pthread_mutexattr_t;
+typedef  * _BCD__32___darwin_pthread_mutex_t;
+typedef long unsigned int _BCD__33___darwin_pthread_key_t;
+typedef  * _BCD__35___darwin_pthread_condattr_t;
+typedef  * _BCD__37___darwin_pthread_cond_t;
+typedef  * _BCD__39___darwin_pthread_attr_t;
+typedef _BCD__84___int32_t _BCD__40___darwin_pid_t;
+typedef long long int _BCD__82___int64_t;
+typedef _BCD__82___int64_t _BCD__42___darwin_off_t;
+typedef short unsigned int _BCD__85___uint16_t;
+typedef _BCD__85___uint16_t _BCD__44___darwin_mode_t;
+typedef  * _BCD__46___darwin_mcontext64_t;
+typedef  * _BCD__48___darwin_mcontext_t;
+typedef unsigned int _BCD__78___darwin_natural_t;
+typedef _BCD__78___darwin_natural_t _BCD__50___darwin_mach_port_name_t;
+typedef _BCD__50___darwin_mach_port_name_t _BCD__49___darwin_mach_port_t;
+typedef _BCD__83___uint32_t _BCD__51___darwin_ino_t;
+typedef _BCD__83___uint32_t _BCD__52___darwin_id_t;
+typedef _BCD__83___uint32_t _BCD__53___darwin_gid_t;
+typedef unsigned int _BCD__54___darwin_fsfilcnt_t;
+typedef unsigned int _BCD__55___darwin_fsblkcnt_t;
+typedef _BCD__84___int32_t _BCD__56___darwin_dev_t;
+typedef _BCD__84___int32_t _BCD__57___darwin_blksize_t;
+typedef _BCD__82___int64_t _BCD__58___darwin_blkcnt_t;
+typedef long int _BCD__64___darwin_time_t;
+typedef long int _BCD__65___darwin_ssize_t;
+typedef _BCD__83___uint32_t _BCD__66___darwin_socklen_t;
+typedef int _BCD__68___darwin_wint_t;
+typedef int _BCD__70___darwin_wchar_t;
+typedef _BCD__70___darwin_wchar_t _BCD__69___darwin_rune_t;
+typedef char * _BCD__72___darwin_va_list;
+typedef long unsigned int _BCD__73___darwin_size_t;
+typedef int _BCD__74___darwin_ptrdiff_t;
+typedef union  _BCD__76___darwin_mbstate_t;
+typedef int _BCD__77___darwin_ct_rune_t;
+typedef long int _BCD__79___darwin_intptr_t;
+typedef long long unsigned int _BCD__81___uint64_t;
+typedef short int _BCD__87___int16_t;
+typedef unsigned char _BCD__89___uint8_t;
+typedef signed char _BCD__91___int8_t;
+}
diff -r 000000000000 -r 4b2e8e8a633e trunk/bcd/sys/times.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/bcd/sys/times.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,17 @@
+/* THIS FILE GENERATED BY bcd.gen */
+module bcd.sys.times;
+align(4):
+//public import bcd.sys._types;
+alias uint clock_t;
+extern (C) uint times(tms *);
+struct tms {
+uint tms_utime;
+uint tms_stime;
+uint tms_cutime;
+uint tms_cstime;
+}
+long iutime(){
+	tms t;
+	times(&t);
+	return t.tms_utime;
+}
diff -r 000000000000 -r 4b2e8e8a633e trunk/dsss.conf
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/dsss.conf	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,5 @@
+[aid]
+exclude=aid/maze/
+[ga_code.d]
+[ga_maze.d]
+[mazegen.d]
diff -r 000000000000 -r 4b2e8e8a633e trunk/ga_code.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/ga_code.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,2 @@
+/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 + Genetic Algorithm Code Test                            +
 + Author: Matt P.                                        +
 + Version: 0.5                                           +
 +                                                        +
 + Runs a genetic algorithm test using a simple code      +
 + guessing algorithm.                                    +
 +                                                        +
 + Usage: ga_code [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 how long the code to be guessed is.     +
 +      Default: 20                                       +
 +                                                        +
 + -n integer                                             +
 +      Specifies how many possibilities there are for    +
 +      each character of the code string.                +
 +      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                                        +
 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/


module ga_code;

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[] target;

int numChars = 20;
int stringLen = 20;

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

class Foo {
	public double calculateFitness(char[] gene){
		double fitness=0;
		for (uint i = 0; i < stringLen; i++){
			if (gene[i] == target[i])
				fitness += 1;
		}
		return fitness;
	}
	
	public char[] getRandomGenotype(){
		char[] t;
		t.length = stringLen;
		for (int i = 0; i < stringLen; i++){
			t[i] = Random.shared.next(numChars) + 'a';
		}
		return t;
	}
	
	public char getRandomChar(uint index){
		return cast(char)(Random.shared.next(numChars)+'a');
	}
}

void usage(){
	auto s = 
		"Usage: ga_test [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 how long the code to be guessed is.    \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 = stringLen;
	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 "-n":
				numChars = Integer.parse(args[++i]);
				break;
			case "-r":
				rep = Integer.parse(args[++i]);
				break;
			case "-v":
				ga.verbose = true;
				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;
		}
	}
	
+	target = ga.getRandomGenotype();
	
	double[] time;
	double[] gens;
	long start,end;
	
	for(auto i = 0; i < rep; i++){
		if(dotime) start = iutime();
		uint 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)
}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/ga_maze.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/ga_maze.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,331 @@
+/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ + 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)
+}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/mazegen.d
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/mazegen.d	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,128 @@
+/++++++++++++++++++++++++++++++++++++++++++++++++
+ +               Maze Generation                +
+ +               Author: Matt P.                +
+ +                 Version: 1.0                 +
+ +                                              +
+ + Generates a simple maze with odd dimensions. +
+ ++++++++++++++++++++++++++++++++++++++++++++++++/
+
+module mazegen;
+
+import tango.math.Random;
+import tango.io.Stdout;
+import Integer = tango.text.convert.Integer;
+
+void usage(){
+	Stdout(
+"Usage: mazegen width height [options]\n"
+"Width and height must be odd and greater than or equal to 5.\n"
+"Options:\n"
+"  -e char\n"
+"     Set the empty block character to char.\n"
+"  -f char\n"
+"     Set the filled block character to char.\n"
+"  -b\n"
+"     Disables printing of the border.\n"
+"  -i\n"
+"     Prints out how many possible mazes there are for that size and quit.\n").flush;
+}
+
+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,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).flush;
+			else Stdout(""~e).flush;
+		}
+		if (outline) Stdout("|").newline;
+	}
+	if (outline){
+		Stdout("+");
+		for (auto j = 0; j < m[0].length; j++){
+			Stdout("-");
+		}
+		Stdout("+").newline;
+	}
+}
+
+void main(char[][] args){
+	char empty = ' ';
+	char filled = 'X';
+	
+	if(args.length < 3){
+		usage();
+		return;
+	}
+	
+	uint width = Integer.parse(args[1]);
+	uint height = Integer.parse(args[2]);
+	bool frame = true;
+	
+	if (width % 2 != 1 || height % 2 != 1 || width < 5 || height < 5){
+		usage();
+		return;
+	}
+	
+	for (auto i = 3; i < args.length; i++){
+		char[] arg = args[i];
+		switch (arg){
+			case "-h":
+				usage();
+				return;
+			case "-e":
+				empty = args[++i][0];
+				break;
+			case "-f":
+				filled = args[++i][0];
+				break;
+			case "-i":
+				Stdout("There are 2^")( (( width - 1 ) / 2 ) * (( height - 1 ) / 2 ) )(" different maze types for that size.").newline;
+				return;
+			case "-b":
+				frame = false;
+			default:
+				Stdout.format("Unknown parameter: {}",arg).newline;
+				usage();
+				return;
+		}
+	}
+	
+	bool[][] maze = generateMaze(width,height);
+	
+	printMaze(maze,empty,filled,frame);
+}
\ No newline at end of file
diff -r 000000000000 -r 4b2e8e8a633e trunk/test.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/test.py	Mon Mar 03 19:28:10 2008 -0700
@@ -0,0 +1,60 @@
+#!/usr/bin/python
+
+from subprocess import *
+
+def frange(*args):
+	l = len(args)
+	if l == 1: # only to
+		f = 0
+		t = args[0]
+		step = 1
+	elif l == 2: # from, to
+		start, stop = args
+		step = 1
+	elif l == 3:
+		start, stop, step = args
+	k = (stop-start)/step+1
+	return map(lambda x, f=start, s=step: f+s*x, range(max(0, int(k))))
+
+prefix = "/Users/matthew/Desktop/D/ai/"
+output_prefix = "/Users/matthew/Desktop/D/ai/tests/"
+
+print "Running..."
+
+
+repetitions=100
+
+tests = [
+	["ga_code","mutation-rate", "-m",frange(0.0,0.05,0.01) + frange(0.1,1,0.05),[]],
+	["ga_code","population",    "-p",frange(500,5000,500),[]],
+	["ga_code","survival-rate", "-d",frange(0.2,0.8,0.05),[]],
+	["ga_code","crossover-type","-c",frange(1,3,1),[]],
+	["ga_code","code-length",   "-l",frange(10,30,1),[]],
+	
+	["ga_maze","mutation-rate","-m",frange(0.0,0.05,0.01) + frange(0.1,1,0.05),[]],
+	["ga_maze","population",   "-p",frange(500,5000,500),["-s","9","9"]],
+	["ga_maze","survival-rate", "-d",frange(0.2,0.8,0.05),[]],
+	["ga_maze","crossover-type","-c",frange(1,3,1),[]],
+	["ga_maze","code-length",   "-l",frange(10,30,1),[]]
+]
+
+def runTest(exe,name,switch,vrange,addparams):
+	f  = open(output_prefix + ("%s_%s_generations.csv" % (exe,name)),"w")
+	f2 = open(output_prefix + ("%s_%s_times.csv" % (exe,name)),"w")
+	
+	for i in vrange:
+		print i
+		p = Popen([prefix + exe,switch,str(i),"-r",str(repetitions),"-b","100"]+addparams,stdout=PIPE,bufsize=-1)
+		p.wait()
+		r = "".join(p.stdout.readlines())
+		r = r.split(",");
+		f.write("%s,%s,%s\n" % (str(i),r[0],r[1]))
+		f2.write("%s,%s,%s" % (str(i),r[2],r[3]))
+	f.close()
+	f2.close()
+#try:
+for test in tests:
+	print "%s: %s" % (test[0],test[1])
+	runTest(test[0],test[1],test[2],test[3],test[4])
+#except:
+#	print "Stopped"
\ No newline at end of file