Download the raw code.

use v6;

# Problem 3 -- Calculate addition chains.
# The minimum path to a particular target can be found by just doing a breadth
# first search through all the possibilities. We additionally prune the search
# by ignoring sequences that we've already found the minimum for and those that
# are larger than our target. We also know that any new sequences can only be
# generated using the last element in the sequence as one of the addends.
# Otherwise the sequence was already generated by our parent sequence.

die "Target chain argument required." unless @*ARGS;
my $target = @*ARGS[0].Int;

if $target == 1
    say "(1)";
    exit 0;
elsif $target <= 0 || $target ne @*ARGS[0]
    die "Unable to achieve @*ARGS[0]: must be a positive integer.";

my %seen;

my @sequences = ([1], );

# Breadth first search
    my @sequence = @(shift @sequences);
    my $last = @sequence[@sequence - 1];
    for @sequence -> $cur
        my $sum = $last + $cur;
        if $sum == $target
            say "(@sequence.join(', '), $sum)";
            exit 0;
        elsif $sum < $target
            @sequences.push([@sequence, $sum]) unless %seen{$sum}++;


As noted in the blog post, code which generates Brauer chains will work correctly... up until N = 12509, the shortest chain length at which no Brauer chain is minimal.


Looks nice and consistent.

Clarity of intent

The program is neat and gets to the point. It's easy to follow the author's line of thought.

Algorithmic efficiency

The solution breaks off from the crowd and makes a breadth-first search. No idea how that affects the efficiency, though.

Idiomatic use of Perl 6

A bit of manual argument handling at the start, where a MAIN method could easily have done the trick.

There seems to be a bit of residual apprehension, perhaps from Perl 5, that array assignments won't work correctly without a set of parentheses or @() conversion on the right-hand side. They will.


The code is fairly short.