Was kind'a bored, so i worked on a perl solution. This should be much faster:
#!/usr/bin/perl
use strict;
use warnings;
my $desired_postage = $ARGV[0] || 1.51;
$desired_postage = int $desired_postage * 100;
my @stamps =
sort { $a <=> $b }
grep { chomp; $_ < $desired_postage }
map { int $_ * 100 }
grep { ! /^#/ }
<DATA>;
my $exact = grep { $_ == $desired_postage } @stamps;
print "Exact postage: " . $exact / 100 . "\n" if $exact;
my $dim_max = 6;
recurse( $desired_postage, [] );
sub recurse {
my( $rest, $select ) = @_;
if ( $rest == 0 ) {
print $_ / 100 . " " for @$select;
print "\n";
return;
}
return if @$select >= $dim_max;
my @filtered = grep {
$_ >= $rest / ($dim_max - @$select)
and $_ <= $rest
} @stamps;
@filtered = grep{ $_ <= $select->[-1] } @filtered if $select->[-1]
+;
for my $stamp ( sort{ $b <=> $a } @filtered ) {
recurse( $rest - $stamp, [ @$select, $stamp ] );
}
return;
}
Also i made integers of all values, because apearently on a Pentium IV 1.51 - 0.87 - 0.42 - 0.1 - 0.1 - 0.02 != 0
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|