#!/usr/bin/perl

use strict;
use List::Util qw(shuffle);

#possible values the node of a tree can be
my(@node_values) = ("a1","a0","d0","d1","d2","d3","AND","OR","NOT");

#probability of one of the following next genereation functions will happen
my(@prob) = 	(10, #Reproduction
		95, #Crossover
		5);#Mutation

#the minimum fitness a person must have to be considered for any nexy genereation functions
my($min_fitness) = 10;

#defines the possible values for the truth table
my(%range) = ();

#will generate a logic equation and place it in a tree format
#it is done recursively to a certain depth (defined in level)
#this is called for intializing a population
sub generate_tree() {
	my( $node, $level) = @_;
	unless($node) {
		$node = {};
		$node->{left} = undef;
		$node->{right} = undef;
		$node->{op} = 0;
	}
	if($level > 0) {
		my($op) = @node_values[int(rand($#node_values))];
		if($op eq "AND") {
			&generate_tree($node->{left}, $level-1 );
			&generate_tree($node->{right}, $level-1 );
		}
		if($op eq "OR") {
			&generate_tree($node->{left}, $level-1 );
			&generate_tree($node->{right}, $level-1 );
		}
		if($op eq "NOT") {
			&generate_tree($level-1, $node->{left});
			$node->{right} = undef;
		}
		$node->{op} = $op;
	}
	if($level == 0) {
		$node = {};
		$node->{left} = undef;
		$node->{right} = undef;
		$node->{op} = (@node_values[int(rand(6))]);
	}
	$_[0] = $node;
	return;
}

#converts a decimal number to a binary string
#used to generate values for range
sub dec2bin {
	my $str = unpack("B32", pack("N", shift));
	$str =~ s/^0+(?=\d)//;   # otherwise you'll get leading zeros
	return $str;
}

#this initializes a population of possible solutions at a certain size
sub initialize() {
	my($size) = shift;
	my(@people) = {};
	print "Intial String:\n";
	for(my $i = 0; $i < $size; $i++) {
		$people[$i]{'fitness'} = 0;
		&generate_tree($people[$i]->{'tree'}, int(rand(6))+1 );
		print &string_tree($people[$i]->{'tree'}) . "\n";
	}
	#the following generates the truth table
	#the equation be looked for needs to match 
	for(my $i = 0; $i < 64; $i++) {
		my $value = &dec2bin($i);
		my($a0,$a1,$d0,$d1,$d2,$d3) = split(//,$value);
		$range{$value} = 0;
		if($a0 eq "0" && $a1 eq "0" && $d0 eq "1") {$range{$value} = 1;}
		if($a0 eq "1" && $a1 eq "0" && $d1 eq "1") {$range{$value} = 1;}
		if($a0 eq "0" && $a1 eq "1" && $d2 eq "1") {$range{$value} = 1;}
		if($a0 eq "1" && $a1 eq "1" && $d3 eq "1") {$range{$value} = 1;}
	}
	return(@people);
}

#takes a tree and evaluates it into an actual logical equation
sub eval_tree() {
	my($tree) = shift;
	my($value) = shift;
	if($tree->{op} eq "AND") {return(&eval_tree($tree->{left},$value) & &eval_tree($tree->{right}, $value));}
	if($tree->{op} eq "OR") {return(&eval_tree($tree->{left},$value) | &eval_tree($tree->{right}, $value));}
	if($tree->{op} eq "NOT") {return(!(&eval_tree($tree->{left},$value)));}
	if($tree->{op} eq "a0") {return(substr($value,0));}
	if($tree->{op} eq "a1") {return(substr($value,1));}
	if($tree->{op} eq "d0") {return(substr($value,2));}
	if($tree->{op} eq "d1") {return(substr($value,3));}
	if($tree->{op} eq "d2") {return(substr($value,4));}
	if($tree->{op} eq "d3") {return(substr($value,5));}
}

sub calc_fitness() {
	my(@people) = @_;
	for(my $i = 0; $i < $#people; $i++) {
		$people[$i]{'fitness'} = 0;
		foreach my $value (keys %range) {
			if(&eval_tree($people[$i]{'tree'}, $value) == $range{$value}) {$people[$i]{'fitness'}++;}
		}
	}
	return(@people);
}

#takes a tree and converts it into a string
sub string_tree() {
	my($tree) = shift;
	my($value) = shift;
	if($tree->{op} eq "AND") {return("(" . &string_tree($tree->{left},$value) . " AND " . &string_tree($tree->{right}, $value) . ")");}
	if($tree->{op} eq "OR") {return("(" . &string_tree($tree->{left},$value) . " OR " . &string_tree($tree->{right}, $value) . ")");}
	if($tree->{op} eq "NOT") {return("(NOT " . (&string_tree($tree->{left},$value)) . ")");}
	if($tree->{op} eq "a0") {return("a0");}
	if($tree->{op} eq "a1") {return("a1");}
	if($tree->{op} eq "d0") {return("d0");}
	if($tree->{op} eq "d1") {return("d1");}
	if($tree->{op} eq "d2") {return("d2");}
	if($tree->{op} eq "d3") {return("d3");}
}

sub found_solution() {
	my(@people) = @_;
	for(my $i = 0; $i < $#people; $i++) {
		if($people[$i]->{'fitness'} == 64) {
			print "Solution Found:\n";
			print &string_tree($people[$i]->{'tree'});
			return(1);
		}
	}
	return(0);
}

sub get_all_Descendents() {
	my($node) = shift;
	my(@children) = ();
	if($node->{left} ne undef) {push(@children, &get_all_Descendents($node->{left}));}
	push(@children, \$node);
	if($node->{right} ne undef) {push(@children, &get_all_Descendents($node->{right}));}
	return(@children);
}

for(my $size = 100; $size < 101; $size++) {
	print "Size: $size\n";
	my(@population) = &initialize($size);
	my($generation) = 0;
	my $quit = 0;
	while($quit == 0){
		@population = &calc_fitness(@population);
		if(&found_solution(@population)) {
			print "\tFinal Generation:	$generation\n";
			$quit = 1;
		} else{
			my(@children) = ();
			my($children_size) = 0;
			while($children_size < $size) {
				my($choice) = int(rand(100) + 1);
				if(($choice >= 1) && ($choice <= $prob[0])) {
					#Reproduction
					my($person_a) = int(rand($size));
					while($population[$person_a]->{'fitness'} < $min_fitness) {$person_a = int(rand($size));}
					push(@children,$population[$person_a]);
					$children_size++;
				}
				if(($choice > $prob[0]) && ($choice <= $prob[1])) {
					#Crossover
					my($person_a)= int(rand($size));
					my($person_b)= int(rand($size));
					while($population[$person_a]->{'fitness'} < $min_fitness && $population[$person_b]->{'fitness'} < $min_fitness) {
						$person_a = int(rand($size));
						$person_b = int(rand($size));	
					}
					print "Person A: ";
					print &string_tree($population[$person_a]{'tree'}) . "\n";
					my($child_a) = (shuffle &get_all_Descendents($population[$person_a]->{'tree'}))[0];
					my($child_b) = (shuffle &get_all_Descendents($population[$person_b]->{'tree'}))[0];
					($child_a, $child_b) = ($child_b, $child_a);
					print "Child A: " . &string_tree($population[$person_a]->{'tree'}) . "\n";
					push(@children,$population[$person_a]);
					push(@children,$population[$person_b]);
					$children_size+=2;
				}
				if(($choice > $prob[1]) && ($choice <= 100)) {
					#Mutations
					my($person_a) = int(rand($size));
					while($population[$person_a]->{'fitness'} < $min_fitness) {$person_a = int(rand($size));}
					my($child_a) = (shuffle &get_all_Descendents($population[$person_a]->{'tree'}))[0];
					&generate_tree($child_a, int(rand(3))+1);
					push(@children,$population[$person_a]);
					$children_size++;
				}
			}
			$generation++;
			@population = @children;
		}
	}
}