use v6;
=begin pod
A solution to problem 2 of the Perl 6 2011 Coding Contest
http://strangelyconsistent.org/blog/the-2011-perl-6-coding-contest
by Ian Fraser, 2012-01-29
Finds the first N numbers that can be expressed as a sum of two cubes
in more than one way
=end pod
sub solve_for(Int $n) {
my %sum_one_way;
my %candidates;
my $max_of_first_n = 0;
# We need to find the smallest $n solutions.
# Although there may be some candidates smaller than the first $n we find
# we don't need any that are larger than the mmaximum of the first $n.
my $i = 1;
repeat until (%candidates.elems >= $n && $i ** 3 >= $max_of_first_n) {
for (1 .. $i) -> $j {
# we're computing cubes more often than we need to here
# but indexing into a lazily computed list of cubes was slower
my $sum = $j ** 3 + $i ** 3;
my $formula = "$j ** 3 + $i ** 3";
if ! %sum_one_way.exists($sum) {
%sum_one_way{$sum} = $formula;
} else {
%candidates{$sum} = [ %sum_one_way{$sum} ] unless %candidates.exists($sum);
%candidates{$sum}.push($formula);
$max_of_first_n max= $sum if %candidates.elems <= $n;
}
}
$i++;
}
my @in_order = %candidates.pairs.sort( { +.key } );
for @in_order[ 0 .. $n - 1 ] -> $p {
say join(" = ", $p.key, $p.value.list);
}
}
multi MAIN(Int $n) {
return unless $n > 0;
solve_for($n);
}