#!/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); } } } } }