Dropbox Challenge - 3 The Dropbox Diet

solution.pl

#!/usr/bin/perl
use strict;
# dmn001 <at> gmail
# 31/01/2011

my %pos;
my %neg;
my $num_lines = <STDIN>;

while (<STDIN>){
	if (/^(.*?) (-?\d+)/){
		$pos{$2} = $1 if $2 > 0;
		$neg{$2} = $1 if $2 < 0;
		if ($2==0){print $1;exit;}
	}
	last if --$num_lines==0;
}

if ((scalar %pos ==0) or (scalar %neg == 0)){
	print "no solution";
	exit;
}

foreach my $x (sort keys %pos){
	foreach my $y (sort keys %pos){
		last if $pos{$x} eq $pos{$y};
		if (!defined $pos{$x+$y}){
			$pos{$x+$y} = "$pos{$x}!$pos{$y}";
		}
	}
}

foreach my $x (sort keys %neg){
	foreach my $y (sort keys %neg){
		last if $neg{$x} eq $neg{$y};
		if (!defined $neg{$x+$y}){
			$neg{$x+$y} = "$neg{$x}!$neg{$y}";
		}
	}
}

my $solution;
my $last = 0;
foreach my $x (sort {$a <=> $b} keys %pos){
	foreach my $y (sort {$b <=> $a} keys %neg){
		last if ($x + $y) < 0;
		#print "$x, $y\n";
		if (($x+$y) ==0){
			$solution = $pos{$x}."!".$neg{$y};
			$last = 1;
		}
		last if $last;
	}
	last if $last;
}

if ($last ==0){
	print "no solution";
	exit;
}

my @sol = sort split /!/,$solution;
my $sol = pop(@sol);
foreach(@sol){
	print "$_\n";
}
print $sol;