public
Last active

Another, slightly faster, solution to "Dropbox Diet" from http://www.dropbox.com/jobs/challenges

  • 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
#!/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;
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.