Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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 ];
}
}
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.