t2/ian

Download the raw code.

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

Correctness

Yes, correct.

This is the only solution that took into account that there can be more than two ways to write a sum of cubes and that was efficient enough for us to observe it. Thumbs up.

Consistency

The code is laid out consistently, and vertically aligned where it makes sense.

For no apparent reason, there are two spaces after the my in the first four declarations in solve_for. The rest of the declarations have one space as usual.

Clarity of intent

It is easy to follow the author's line of thought. The variable names are expressive.

Algorithmic efficiency

This is the fastest solution that has been submitted for task 2. Enough said.

Idiomatic use of Perl 6

Pleasant use of max= and array slicing.

Some constructs could have been visually optimized in small ways, for example @in_order[ 0 .. $n - 1] could be written as @in_order[ ^$n ], and use of //= or ||= could simplify hash element initialization.

Superstitious parentheses in the innermost for loop.

Brevity

One of the shorter solutions.