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