Download the raw code.
use v6;
# Problem 2 -- List the numbers which are sums of cubes in more ways than one.
# I follow a pretty simple solution for this program. Just generate all the
# cube sums in sequence and match the ones that are sums of multiple. It's
# possible this solution will print out a duplicate line if there are 3 ways to
# make a given sum, but I didn't see that out into the hundreds of millions, so
# I'm hopeful it's not possible.
die "Maximum index argument required." unless @*ARGS;
my $max-count = @*ARGS[0].Int;
die "Maximum index argument must be an integer" if $max-count ne @*ARGS[0];
# Generate the list of cubes.
my $cubes = map * ** 3, 0 .. *;
my %cube-sum;
my $count = 0;
my $max-sum = -1;
my @sums;
# Generate the cube-pairs. There's no guaruntee that we're generating them in
# order, so we have to queue them up for later printing.
for 2 .. * -> $i
{
# If we know there's no possible sum that is smaller than the smallest we've
# generated so far, print it out so the user can see progress on longer
# iterations.
if @sums && $cubes[$i] >= @sums[0].key {
say @sums.shift.value;
--$max-count; --$count;
}
last if $count >= $max-count && $cubes[$i] >= $max-sum;
# If it wasn't about twice as slow, it would make sense to delete cube sums
# that could no longer even have a chance of matching future cube sums.
# %cube-sum.delete($_) if $_ < $cubes[$i] for %cube-sum.keys;
for 1 .. $i -> $j
{
my $sum = $cubes[$i] + $cubes[$j];
last if $count >= $max-count && $sum > $max-sum;
# If we've already seen this sum, queue it up for user notification.
if (%cube-sum.exists: $sum) {
push(@sums, $sum => "$sum = %cube-sum{$sum} = $i ** 3 + $j ** 3");
@sums = @sums.sort;
if (++$count >= $max-count) {
$max-sum = min($max-sum, $sum);
}
}
# Don't bother storing sums that can't possibly match anything the
# future cubes will be able to generate.
elsif $sum > $cubes[$i + 1] {
%cube-sum{$sum} = "$i ** 3 + $j ** 3";
}
}
}
# Catch any sums we didn't print out. The current implementation can only
# print out the last element in this loop.
for ^$max-count {
say @sums[$_].value;
}
The solution correctly finds the first 97 sums of cubes, but then starts to skip some numbers. The first one it incorrectly misses is
4607064 = 166 ** 3 + 32 ** 3 = 135 ** 3 + 129 ** 3
There are two errors in the logic that lead to misses, both related to
$sum
not increasing monotonically.
Firstly:
my $sum = $cubes[$i] + $cubes[$j];
last if $count >= $max-count && $sum > $max-sum;
Since $sum
is not monotonic, it is unfit for comparing it to a limit,
and terminating the computation based on the result.
The other flaw is here:
# Don't bother storing sums that can't possibly match anything the
# future cubes will be able to generate.
elsif $sum > $cubes[$i + 1] {
%cube-sum{$sum} = "$i ** 3 + $j ** 3";
}
It is wrong to discount smaller values $sum
-- they can still produce
matches in later iterations of the outermost loop.
The solution fails to account for the eventuality that some sum of cubes can be written in more than two ways, even though the author is aware of that possibility.
Placement of braces is not consistent: After an if
, the opening brace is
on the same line, but after a for
there is a newline between the loop
header and the opening brace -- except for the last loop, which is again
laid out in K&R style.
There is also a pair of round parentheses around the conditonal of an
if
-statement, which is otherwise avoided.
The code is easy to read and well commented.
Fast but wrong.
Inspiring use of infinite lists. Otherwise the code isn't packed with Perl 6 idioms, but neither does it feel like it misses many opportunities to be more idiomatic.
Could have used MAIN
instead of manual arguments handling near the top.
Not very much code, though the many comments make it seem a bit longer.