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.sort.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?)
The code produces correct results.
Why is an array meant to contain integers called @nums
? :-)
The code is very clear and easy to read and understand in its entirety.
The sentence fragment @nums[*-1]
keeps showing up — would maybe have
been better to shove it into a variable near the start of &solve
?
Currently no implementation supports the syntax my @nums of Int
except
Rakudo, and it ignores the type trait — so using it provides
documentation but no type checking.
There is nothing especially fast or slow about this solution. It recursively tries all possible chains.
Nice chained operators.
There's nothing wrong with writing it my @nums of Int
, even though the form
my Int @nums
is more commonly seen. (It should be noted that both ways of
writing it have weaknesses in Rakudo when it comes to typechecking. The
my @nums of Int
happens to have one more weakness: you can assign non-Ints
to individual elements. You can't with my Int @nums
.)
This program is short without being compact.