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