Download the raw code.
#!/usr/local/bin/perl6
sub MAIN($target is copy)
{
my (Int @bfsq, Array of Int $curr, Int $i, Int $j, Int $sum);
my @tmp = ( 1 );
my %seen;
# Complain if given unreasonable arguments.
say "Argument must be positive." and exit(1) if $target < 1;
say "Argument must be integer." and exit(1) if $target.Int != $target;
$target = $target.Int;
push @bfsq, item @tmp;
# Handle degenerate case directly; speeds core searcher slightly
# by allowing us to print the result right after we compute the
# sum, rather than when extracting from the BFS queue.
if ($target eq 1) { say "(1)"; exit(0); }
# Do a simple BFS search for the shortest addition chains to reach
# the target value.
while ($curr = shift @bfsq) {
for 0 ..^ $curr.elems -> $i {
for $i ..^ $curr.elems -> $j {
$sum = $curr[$i] + $curr[$j];
next if ($sum > $target || %seen{$sum});
%seen{$sum} = 1; # Filter out the many, many redundant sums
if ($sum < $target) {
my @next = (@($curr), $sum);
push @bfsq, $(@next);
} else {
say "(", $curr.join(", "), ", $sum)";
exit(0);
}
}
}
}
}
The code produces shortest addition chains for up to 76. For 77, it prints
(1, 2, 3, 5, 7, 14, 19, 38, 76, 77)
Which is one element longer than necessary, optimal would be
(1, 2, 4, 8, 9, 17, 34, 68, 77)
The problem is rooted deeply in the BFS approach. Weeding out duplicate ways to write the same number as sums can produce imperfect results when searching for higher numbers. Considering all duplicates makes the BFS unbearably slow for larger numbers.
The code sometimes uses
parenthesis around if
/while
conditionals, but not around the for
lists.
Straightforward and easy to follow.
This is a fast solution... by sacrificing correctness.
Not much to note besides the presence of a MAIN
sub. 0 ..^ $curr.elems
could have been written more idiomatically as ^$curr
.
Short and to the point, without feeling crammed.