Skip to content

Instantly share code, notes, and snippets.

@fracai
Created January 30, 2011 05:15
Show Gist options
  • Save fracai/802567 to your computer and use it in GitHub Desktop.
Save fracai/802567 to your computer and use it in GitHub Desktop.
An OK solution to "Dropbox Diet" from http://www.dropbox.com/jobs/challenges
#!/usr/bin/env perl
use strict;
use warnings;
my %options = ();
my $lines = 0;
foreach my $line (<>) {
if ($line =~ m/^(\d+)$/) {
$lines = $1;
}
if (0 == $lines) { last; }
if ($line =~ m/^([^ ]+) (-?\d+)$/) {
$options{$1} = $2;
$lines --;
}
}
my @options = (sort keys %options);
my @comb_options = combinations(0..$#options);
foreach my $pick (@comb_options) {
if ( -1 == $#{$pick} ) { next; }
my $total = 0;
map $total += $options{$options[$_]}, @{$pick};
if (0 == $total) {
my @solution = ();
foreach my $index (@{$pick}) { push @solution, $options[$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