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

dropbox-diet.pl

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