Download the raw code.
#!/usr/bin/env perl6
# This is perl6 version 2011.12-18-ga7fd89e built on parrot 3.11.0 revision RELEASE_3_11_0
my @ANS of Int;
my Int $TARGET;
sub solve( @nums ) {
if 0 < @ANS.elems <= @nums.elems {
# Do nothing. We already have a better solution.
}
elsif @nums[*-1] < $TARGET {
# Try adding the largest numbers first so that the first
# solution will have approximately log $TARGET elements.
for @nums.reverse -> $k {
@nums.push( @nums[*-1] + $k );
solve( @nums );
@nums.pop;
}
}
elsif @nums[*-1] == $TARGET {
@ANS = @nums;
}
}
sub MAIN {
for lines() {
$TARGET = $_.Int;
@ANS = ();
my @nums of Int = 1; # The only array needed for all calculations.
solve( @nums );
printf "(%s)\n", @ANS.join( ", " );
}
}
# The C++ equivalent allocates approximately 10 kb of memory.
# Rakudo burns hundreds of megabytes, and it gets much worse
# for multi-line input. (memory leak?)
Same solution as the first one by this author, except with one less call to
.sort
:
@@ -31,5 +31,5 @@
solve( @nums );
- printf "(%s)\n", @ANS.sort.join( ", " );
+ printf "(%s)\n", @ANS.join( ", " );
}
}
Which makes sense, if you consider that we're always only pushing numbers which
are sums of earlier (positive) numbers, so @ANS
has to end up sorted already.