# t3/zbiciak

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

## Correctness

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.

## Consistency

The code sometimes uses parenthesis around `if`/`while` conditionals, but not around the `for` lists.

## Clarity of intent

Straightforward and easy to follow.

## Algorithmic efficiency

This is a fast solution... by sacrificing correctness.

## Idiomatic use of Perl 6

Not much to note besides the presence of a `MAIN` sub. `0 ..^ \$curr.elems` could have been written more idiomatically as `^\$curr`.

## Brevity

Short and to the point, without feeling crammed.