#!/usr/bin/perl

use Data::Dumper;
use Storable qw(dclone);

our %states = %{loadStateData("states.txt")};
our @evStates = @{indexByEVs(\%states)};
our @optimal = ();

# Treat each count of electoral votes as a subproblem, 
for $i (1...538)
	{
	# First, if possible create a dummy parent and see if there 
	# is a state with exactly the correct number of electoral botes
	my $bestPrevious = {states=>{}, total=>0};
	my $bestAddition = bestNew($bestPrevious, $evStates[$i]);

	# For each calculated optimal subproblem, check if there is a state with the 
	# right number of electoral votes to calculate the answer to this subproblem
	for $j (1...($i-1))
		{
		# Skip if there ie no parent subproblem, or if there are no states with the right number of electoral votes
		next unless($evStates[$i - $j] && defined($optimal[$j]));

		$prev = $optimal[$j]; 
		$parentBest = bestNew($prev, $evStates[$i-$j]); 
		
		# Skip if there's no eligible state to add
		next unless($parentBest); 

		if(!defined($bestAddition) || $prev->{total} + $states{$parentBest}->{ballots} < $bestPrevious->{total} + $states{$bestAddition}->{ballots})
			{
			$bestPrevious = $prev;
			$bestAddition = $parentBest;
			}
		}
	
	# If $bestAddition was set, either by the direct solution or by extending a 
	# previous solution, save it as the optimal for this subproblem
	if($bestAddition)
		{
		$optimal[$i] = extend($bestPrevious, $bestAddition);
		}
	}

bestSolution(\@optimal);

sub bestSolution
	{
	my $optimal = shift;

	$ballots = 1000000000;
	$best = -1;

	# Find the winning sollution that requires the fewest ballots
	for $i (270...$#optimal)
		{
		next unless($optimal->[$i]);

		if($optimal->[$i]{total} < $ballots)
			{
			$best = $i;
			$ballots = $optimal->[$i]{total};
			}
		}

	print("Best: $best evs from the following states\n"); 
	printSolution($optimal->[$best], 1); 
	
	for $i (1...$#optimal)
		{
		next unless($optimal->[$i]);
		printSolution($optimal->[$i], 0); 
		}
	}

sub printSolution
	{
	my $solution = shift;
	my $verbose = shift;

	my $evs = 0; 
	my $ballots = 0;

	if($solution->{total} <= 0)
		{
		print("Invalid solution found\n");
		return;
		}

	for $state (keys %{$solution->{states}})
		{
		$ballots += $states{$state}->{ballots};
		$evs += $states{$state}->{ev};

		print "  * $state (", $states{$state}->{ballots}, " / ",  $states{$state}->{ev}, ")\n" if($verbose);
		}

	my $totalBallots = 0; 
	for $state (keys %states)
		{
		$totalBallots += $states{$state}->{ballots};
		}

	printf STDERR "%d\t%d\t%d\t%d\t%5.2f\n", $evs, $ballots, $totalBallots, (.5001 * $ballots) ,(50.01 * $ballots) / $totalBallots;
	}

sub bestNew
	{
	my $selected = shift;
	my $available = shift;

	my $best = undef;
	my $ballots = 1000000000000;

	foreach $state (@$available)
		{
		next if($selected->{states}{$state});

		if($states{$state}->{ballots} < $ballots)
			{
			$best = $state;
			$ballots = $states{$state}->{ballots};
			}
		}
	
	return $best;
	}

sub extend
	{
	my $selected_source = shift;
	my $selected = dclone($selected_source);
	my $best = shift;

	my $ballots = $states{$best}->{ballots};

	$selected->{states}{$best} = $ballots;
	$selected->{total} += $ballots; 

	return $selected;
	}

sub indexByEVs
	{
	my $states = shift; 
	my $evStates = [];

	foreach $state (keys %$states)
		{
		my $ev = $states->{$state}{ev};
		if(!defined($evStates->[$ev]))
			{
			$evStates->[$ev] = [];
			}
			
		push @{$evStates->[$ev]}, $state;
		}

	return $evStates; 
	}

sub loadStateData
	{
	my $filename = shift;

	my $states = {};

	open STATES, $filename or die(<<EODIE
Could not open state data file $filename: $!
  * $filename should containe one line per state with the number of 
    ballots 
    cast and the number of Electoral Votes awarded
EODIE
);

	while(<STATES>)
		{
		chomp;
		my($state, $ballots, $ev) = split /	/;

		$states->{$state} = { ballots=>$ballots, ev=>$ev };
		}

	close STATES;

	return $states;
	}