Instantly share code, notes, and snippets.

# fracai/dropbox-diet.pl Created Jan 30, 2011

Another, slightly faster, solution to "Dropbox Diet" from http://www.dropbox.com/jobs/challenges
 #!/usr/bin/env perl use strict; use warnings; my %exercise = (); my %food = (); my \$lines = 0; foreach my \$line (<>) { if (\$line =~ m/^(\d+)\$/) { \$lines = \$1; } if (0 == \$lines) { last; } if (\$line =~ m/^([^ ]+) (-?\d+)\$/) { if (\$2 > 0) { \$food{\$1} = \$2; } elsif (\$2 < 0) { \$exercise{\$1} = \$2; } \$lines --; } } my @exercise = (sort keys %exercise); my @food = (sort keys %food); my @comb_exercise = combinations(0..\$#exercise); my @comb_food = combinations(0..\$#food); foreach my \$pick_exercise (@comb_exercise) { foreach my \$pick_food (@comb_food) { if ( -1 == \$#{\$pick_exercise} || -1 == \$#{\$pick_food} ) { next; } my \$total = 0; map \$total += \$exercise{\$exercise[\$_]}, @{\$pick_exercise}; map \$total += \$food{\$food[\$_]}, @{\$pick_food}; if (0 == \$total) { my @solution = (); foreach my \$index (@{\$pick_exercise}) { push @solution, \$exercise[\$index]; } foreach my \$index (@{\$pick_food}) { push @solution, \$food[\$index]; } foreach my \$item (sort @solution) { print "\$item\n"; } exit; } } } print "no solution\n"; # permute and combinations from http://www.perlmonks.org/?node_id=24270 sub permute { my \$last = pop @_; unless (@_) { return map [\$_], @\$last; } return map { my \$left = \$_; map [@\$left, \$_], @\$last } permute(@_); } sub combinations { return [] unless @_; my \$first = shift; my @rest = combinations(@_); return @rest, map { [\$first, @\$_] } @rest; }