Instantly share code, notes, and snippets.

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

What would you like to do?
A further solution to "Dropbox Diet" from http://www.dropbox.com/jobs/challenges This one performs much better with larger inputs by processing smaller combinations before larger.
 #!/usr/bin/env perl use strict; use warnings; my %exercise = (); my %food = (); my \$lines = 0; # read food and exercise options into separate lists based on positive or negative calories 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 @food = (keys %food); my @exercise = (keys %exercise); my %seen = (); # hash to track processed combinations # iterating using max, min, and \$current_max allows processing smaller combinations before bigger # as in: # 1,1 1,2 2,1 2,2 1,3 2,3 3,1 3,2 3,3 # rather than: # 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,2 for my \$current_max (1..max(\$#food+1,\$#exercise+1)) { for my \$food_size (1..min(\$current_max,\$#food+1)) { for my \$exercise_size (1..min(\$current_max,\$#exercise+1)) { if (defined \$seen{"\$food_size,\$exercise_size"}) { next; } \$seen{"\$food_size,\$exercise_size"} ++; # calculate the combinations my \$food_iter = combo(\$food_size, @food); my \$exercise_iter = combo(\$exercise_size, @exercise); # cache the exercise combinations because they'll be needed repeatedly my @exercise_cache = (); while ( my @pick_exercise = \$exercise_iter->() ) { push @exercise_cache, [@pick_exercise]; } # iterate over the combinations while ( my @pick_food = \$food_iter->() ) { foreach my \$pick_exercise (@exercise_cache) { my \$total = 0; map \$total += \$exercise{\$_}, @\$pick_exercise; map \$total += \$food{\$_}, @pick_food; # print the solution if (0 == \$total) { foreach my \$item (sort (@\$pick_exercise, @pick_food)) { print "\$item\n"; } exit; } } } } } } print "no solution\n"; sub max { my (\$a,\$b) = (@_); return (\$a>\$b?\$a:\$b); } sub min { my (\$a,\$b) = (@_); return (\$a<\$b?\$a:\$b); } # from http://www.perlmonks.org/?node_id=371228 sub combo { my \$by = shift; return sub { () } if ! \$by || \$by =~ /\D/ || @_ < \$by; my @list = @_; my @position = (0 .. \$by - 2, \$by - 2); my @stop = @list - \$by .. \$#list; my \$end_pos = \$#position; my \$done = undef; return sub { return () if \$done; my \$cur = \$end_pos; { if ( ++\$position[ \$cur ] > \$stop[ \$cur ] ) { \$position[ --\$cur ]++; redo if \$position[ \$cur ] > \$stop[ \$cur ]; my \$new_pos = \$position[ \$cur ]; @position[ \$cur .. \$end_pos ] = \$new_pos .. \$new_pos + \$by; } } \$done = 1 if \$position[0] == \$stop[0]; return @list[ @position ]; } }