public
Created

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.

  • Download Gist
dropbox-diet.pl
Perl
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
#!/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 ];
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.