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