DEBUG

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
use Storable qw(dclone);

my $print_debug=64;

####global scope####
my @A__=(0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,1);
my @B__=(0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,1,0,0,0,1);
my @C__=(0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,1,0,0,1);
my @D__=(1,0,0,1,0,0,0,1,0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0);

my $max_depth =3;
#Hash to contain victorious actions for max
my %rs=();

my @hs;
# array to contain depth
my @pruned;
my @tree;

my @branch;

my %stock_values =(
					'A'=>10,
					'B'=>10,
					'C'=>10,
					'D'=>10
					);





sub init
{

# array to contain depth

#Hash to contain victorious actions for min
my %mini_records;

#max
my @player_1=('A', 'B');

#mini
my @player_2=('C', 'D');


push(@branch, \@player_1);

depth(\@tree, \@branch, 0, \@player_1, \@player_2);
}

init();
sub depth
{

my $tree = shift;
my $branch = shift;
#current depth
my $current_depth= shift;
my $player_1=shift;
#mini
my $player_2=shift;

# RETURNS IF PARENT IS IN PRUNED LIST
if(prune($branch, $current_depth))
{
	return;
}

#EVALUATES STOCK VALUE BASED ON DEPTH
my ($stock_values, $flag) = stock_evaluate($player_1, $player_2, $current_depth, $branch);

#RETURNS IF COMBINED PROFILE OF A PLAYER IS EQUAL OR LESS THAN ZERO
if($flag)
{
	print"RECORDING RESULT\n";
	record_results($branch, $stock_values, $current_depth);
	return;
}

#IF MAX DEPTH HAS BEEN REAHED
if ($current_depth >= $max_depth)
{
	print"RECORDING RESULT\n";
	record_results($branch, $stock_values, $current_depth);
	return;
}


debug("value of  stock depth : ".$current_depth, $stock_values);

#generates one level at a time, this is actually breadth
$tree[$current_depth]->[0]= generate($player_1, $player_2);


debug("current player 1 depth :".$current_depth, $player_1);
debug("current branch depth :".$current_depth, $branch);

push($branch, $tree[$current_depth]->[0]->[0] );
debug("current branch after push depth :".$current_depth, $branch);

debug("current  tree[current_depth] depth :".$current_depth,  $tree[$current_depth]);
debug("current  tree[current_depth]->[0] depth :".$current_depth,  $tree[$current_depth]->[0]);
debug("current tree[current_depth]->[0]->[0] depth :".$current_depth,  $tree[$current_depth]->[0]->[0]);
# if($current_depth)
# {
# die;
# }
	depth(
			$tree, 
			$branch, 
			$current_depth+1, 
			$tree[$current_depth]->[0]->[0], 
			compliment($tree[$current_depth]->[0]->[0]->[0], $tree[$current_depth]->[0]->[0]->[1]) 
			);

#already explored leftmost node, remove it from the stack
shift($tree[$current_depth]->[0]);


#work around cause shifting on multi-array ref is no good ???
my $i=0;

foreach(@{$tree[$current_depth]->[0]})
{	

	pop(@{$branch});

	push(@{$branch}, $_);


	depth(	
		    # breadth
			$_,

			# current branch being traversed
			$branch, 

			
			$current_depth+1, 

			#player one
			$tree[$current_depth]->[0]->[$i], 
			#player 2
			compliment($tree[$current_depth]->[0]->[$i]->[0], $tree[$current_depth]->[0]->[$i]->[1])
			);
	$i++;

	

}

pop(@branch);



return;

}

sub revalute
{
	my $stock_values = $_[4];


	if($_[0])
	{
		$stock_values->{'A'} = $stock_values->{'A'} + 1;
	} else
		{
			$stock_values->{'A'} = $stock_values->{'A'} - 1;

		}
	if($_[1])
	{
		$stock_values->{'B'} = $stock_values->{'B'} + 1;
	} else
		{
			$stock_values->{'B'} = $stock_values->{'B'} - 1;

		}
	if($_[2])
	{
		$stock_values->{'C'} = $stock_values->{'C'} + 1;
	} else
		{
			$stock_values->{'C'} = $stock_values->{'C'} - 1;

		}
	if($_[3])
	{
		$stock_values->{'D'} = $stock_values->{'D'} + 1;
	} else
		{
			$stock_values->{'D'} = $stock_values->{'D'} - 1;

		}
	return $stock_values;
}

sub stock_evaluate
{
	my $player_1 = shift;
	my $player_2 = shift;
	my $current_depth = shift;
	my %istock_values = %stock_values;
	my $ref_val = \%istock_values;

	if($current_depth==0)
	{
		#no need to evalute stock worth
		return ($ref_val, 0);
	}

	my $index=0;
	for(my $i=0; $i<$current_depth; $i++)
	{
		if($index == 31)
		{
			$index=0;
		}
		$ref_val = revalute($A__[$index], $B__[$index], $C__[$index], $D__[$index], $ref_val);
		# my @traded_stock = array_diff_return($branch[$index], $branch[$index+1]);
		# print Dumper(\@traded_stock);
		# sleep(2);
		
		# $ref_val->{$traded_stock[0]} = $ref_val->{$traded_stock[0]} +1;
		# $ref_val->{$traded_stock[1]} = $ref_val->{$traded_stock[1]} +1;
		$index++;
	}

			#first stock
		
		debug("player_1 at reval", $player_1);
		debug("player_2 at reval", $player_2);

	my $stock_1 = $ref_val->{$player_1->[0]};
	my $stock_2 = $ref_val->{$player_1->[1]};
		debug("stock 1 at reval", $stock_1);
		debug("stock_2 at reval", $stock_2);
		
	my $stock_3 = $ref_val->{$player_2->[0]};
	my $stock_4 = $ref_val->{$player_2->[1]};
			debug("stock 3 at reval", $stock_3);
		debug("stock 4 at reval", $stock_4);

		debug("reval", $ref_val);

		# die;
	if (($stock_1+$stock_2) <= 0) 
	{
		return ($ref_val,1);
	}

	if(($stock_3+$stock_4) <= 0)
	{
		return ($ref_val,1);
	}



		
	return ($ref_val,0);
	




}

sub record_results
{
my $tree= shift;
my @branch=@{$tree};
my $stock=shift;
my $current_depth = shift;



my @data_new = @{ dclone(\@branch) };
my %data_stock = %{ dclone($stock) };
my @last_node = $data_new[$current_depth];
my @parent =@{ dclone(\@branch) };
my $raw = $stock->{$last_node[0]->[0]} +  $stock->{$last_node[0]->[1]};

my %has_new =(branch => \@data_new,
			  stock => \%data_stock,
			  value=>  $raw,
			  parent=> $parent[1]
				);

#  my @trouble;
# push(@trouble, @branch);


if(prune_time($parent[1], $raw))
{
push(@pruned, $parent[1]);
}else{


push (@hs, \%has_new);
}
# # print Dumper(\@branch);
# # sleep(5);

}

sub prune_time
{
	my $parent = shift;
	my $value = shift;
	foreach(@hs)
	{
		
		if (array_diff($parent,$_->{'parent'}))
		{
			if($_->{'value'} >= $value)
			{
				return 1;
			}
		} 
	}
	return 0;
}

sub prune
{
my $branch = shift;
my $current_depth=shift;

if($current_depth ==0)
{
	return 0;
}
foreach(@pruned)
{
	# print Dumper($branch[1], $_);
	# sleep (5);
	if(array_diff($branch[1],$_))
	{
		# sleep(2);
	return 1;
	}
}
 return 0;
}

sub generate
{
	my @tree;
	my $player_1 = $_[0];
	my $player_2 = $_[1];
	foreach(@{$player_1})
	{
		my $unit = $_;
		my @baby_tree;
		foreach(@{$player_2})
		{
			my @ar;
			push(@ar, $unit, $_);
			push(@tree, \@ar);
		}
	}
	return \@tree;
}


sub compliment
{
	my @list =('A','B','C','D');
	my @compliments;
	my $compa = $_[0];
	my $compb = $_[1];
	foreach(@list)
	{
		if(!($compa =~ /$_/) && !($compb =~ /$_/) )
		{
			push(@compliments, $_);
		}
	}
	return(\@compliments);
}


sub debug
{

	if ($print_debug)
	{
		  # print Dumper ($_[0],$_[1]);
	}

}

sub array_diff 
{
	my $arry_1 = shift;
	my $arry_2 = shift;
	my $num=0;
	foreach(@{$arry_1})
	{
		my $unit = $_;
		foreach(@{$arry_2})
		{
			if($unit eq $_)
			{
				$num++;
			}
		}

	}   
	if($num == 2)
	{
		return 1;
	}
	return 0;
}

sub array_diff_return 
{
	my $arry_1 = shift;
	my $arry_2 = shift;
	my $num=0;
	my $changed;

	my @arr;
	push(@arr, @{$arry_1}, @{$arry_2}); 

	my @un = uniq(@arr);

	return @un;
}


sub uniq {
  my %seen;
  return grep { !$seen{$_}++ } @_;
}


print"\n\n\n\n";

print Dumper (\%rs);
print"\n\n\n\n";

print Dumper (\@hs);