Skip to content

Instantly share code, notes, and snippets.

@rbucker
Created June 4, 2012 17:44
Show Gist options
  • Save rbucker/2869777 to your computer and use it in GitHub Desktop.
Save rbucker/2869777 to your computer and use it in GitHub Desktop.
given a set of weighted values what combination(s) equal 10?
#!/usr/bin/env perl
use strict;
use warnings;
use Math::BigInt;
use List::Util qw(first max maxstr min minstr reduce shuffle sum);
my %d = ("apple"=>3, "pear"=>2, "pineapple"=>9, "strawberry"=>1,
"kiwi"=>-5, "lime"=>15, "lemon"=>5, "orange"=>-1, "banana"=>5);
my $t = 10;
my @keys = keys %d;
my $l = sprintf("%d", scalar @keys);
my $x = Math::BigInt->new("2");
$x->bpow($l);
$x->bdec();
sub xdump($) {
my $arr = shift;
my $p;
print "[";
foreach $p (@$arr) {
print $p."(".$d{$p}."), ";
}
print "]\n";
}
xdump(\@keys);
while( $x->is_pos() ) {
my $by = substr('0' x $l . substr($x->as_bin(), 2),-1*$l);
my @y = split(//, $by);
my $i = -1;
my @k = reduce { $i++; if($b eq '1') {push($a,$keys[$i]);$a} else {$a}} [], @y;
my $k = $k[0];
my $sum = reduce { $a + $d{$b} } 0, @$k;
if( $sum == $t ) {
print $x.". .".$by.". .".$x->as_hex()." ";
xdump($k);
}
$x->bdec();
}
# __END__
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment