public
Last active

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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.