Skip to content

@fracai /dropbox-diet.pl
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.