use v6;
# Problem 3 -- Calculate addition chains.
# The minimum path to a particular target can be found by doing a breadth
# first search through all the possibilities.
# I prune nodes that get to a target value at less than the optimal length. There
# were no differences with the guarunteed optimal non-pruning version out to a depth
# of 13 nodes, which was the farthest I was willing to push my optimized ada program
# (It took 6 GB of memory to get that far).
# Because of the large number of nodes created and the fact that these sequences
# have a lot of shared representation, I implemented the sequences as singly
# linked lists using Pairs.
# Helper method to turn our hand rolled list into the more usable perl6 list.
sub shared-list-to-list($sequence)
{
my @list;
sub iterate($sequence)
{
unshift(@list, $sequence.key);
if defined $sequence.value
{
return iterate($sequence.value);
}
}
iterate($sequence);
return @list;
}
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 %length;
my @queue = ("Marker", 1 => Mu);
my $length = 1;
# Breadth first search
loop
{
my $sequence = shift @queue;
# We put a string marker to denote when we've moved to a new depth in our
# search. This is done so that we don't have to store the length in every
# sequence or be forced to do a O(n) length lookup.
if ($sequence ~~ Str) {
$length = $length + 1;
say $length;
push(@queue, "Marker");
next;
}
my $last = $sequence.key;
loop (my $next = $sequence; defined $next; $next = $next.value)
{
my $sum = $last + $next.key;
if $sum == $target
{
my @final-sequence = shared-list-to-list($sum => $sequence);
say "(@final-sequence.join(', '))";
exit 0;
}
elsif $sum < $target
{
# If this is the first time we've seen this sum, mark it.
if !%length.exists: $sum
{
%length{$sum} = $length;
}
# Prune sequences that don't arrive within the optimal length.
elsif %length{$sum} < $length
{
next;
}
# Push it onto our sequence queue.
@queue.push($sum => $sequence);
}
}
}