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
loop
{
    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}++;
        }
    }
}