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);
}