#!/usr/bin/perl
use strict;
use warnings;

use List::Util qw(sum);
use Set::CrossProduct;
use Term::ANSIColor;
 
my $desired_postage = $ARGV[0] || 1.51;

my @stamps = 
	sort { $a <=> $b } 
	grep { chomp; $_ < $desired_postage } 
	grep { ! /^#/ } 
	<DATA>;

my $exact = grep { $_ == $desired_postage } @stamps;
print "Exact postage: $exact\n" if $exact;

my $dim = 1;
while( 1 )
	{
	my %combos;
		
	my $cross = Set::CrossProduct->new( [ ( \@stamps ) x ++$dim ] );
	print colored ['red'], 
		"For dim $dim, cardinality is ", $cross->cardinality, "\n";

	while( ! $cross->done )
		{
		my $combo = check( scalar $cross->get, $desired_postage );
		$combos{ $combo }++ if $combo;
		}

	foreach my $combo ( 
		sort { $a =~ tr/|// <=> $b =~ tr/|// || $b cmp $a 
			} keys %combos 
		
		)
		{
		my @stamps = split /\|/, $combo;
		
		printf +("%.2f " x @stamps ) . "\n", @stamps;
		}

	last if keys %combos > 15;
	}
	
sub check
	{
	my( $stamps, $desired_postage ) = @_;
	
	sum( @$stamps ) eq $desired_postage ? make_key( @$stamps ): ();
	}
	
sub make_key { join "|", sort { $b <=> $a } @_ }


__END__
# These are the stamp demoninations that I can buy
# The uncommented ones are the stamps that I have
#0.01
0.02
0.03
0.04
0.05
0.10
#0.17
#0.20
0.26
0.27
#0.39
#0.41
0.42
#0.55
#0.59
#0.62
#0.63
#0.72
#0.75
#0.76
0.80
#0.83
0.84
0.87
#0.94
#1.00
#4.80
5.00