Download the raw code.

```
#!/usr/local/bin/perl6
# Find expressions involving four 9s that evaluate to various
# non-negative integers. Expressions can involve the operators
# +,-,*,/ and %, and may use as many parentheses as they like.
#
# Since the search space is sufficiently small, this program
# uses an exhaustive search to evaluate all possible expressions
# involving four 9s. It also takes advantage of Perl 6's rational
# arithmetic to allow intermediate expressions to sometimes not
# be integral, as long as the final result is. (ie. 9/9/9*9)
my @Found;
sub show_all(Int $limit)
{
for 0..$limit {
if @Found[$_].defined {
say "$_ = @Found[$_]"
} else {
say $_;
}
}
exit(0);
}
sub record(Str $exp is copy, Rat $val)
{
my Int $vi = $val.Int;
if 0 <= $vi && $vi == $val && !@Found[$vi].defined {
$exp ~~ s:g/\(9\)/9/; # Minor easy cleanup
@Found[$vi] = $exp;
}
}
my @seen;
sub dfs(Str $exp, Rat $val, Int $nines, Bool $neg_ok)
{
# If we have all four 9s, try recording this expression.
if !$nines { record $exp, $val; return; }
# Optimize away redundant search trees
return if @seen[$nines].{$val.perl}++;
# Try a few creative ways of adding two 9s to the expression
if $nines >= 2 {
dfs("$exp + 9 / 9", $val + 1, $nines - 2, True);
dfs("$exp + 9 * 9", $val + 81, $nines - 2, True);
dfs("$exp - 9 / 9", $val - 1, $nines - 2, False);
dfs("$exp - 9 * 9", $val - 81, $nines - 2, False);
dfs("9 / 9 - ($exp)", 1 - $val, $nines - 2, False) if $neg_ok;
dfs("9 * 9 - ($exp)", 81 - $val, $nines - 2, False) if $neg_ok;
dfs("($exp) / (9 + 9)", $val / 18, $nines - 2, $neg_ok);
dfs("($exp) * (9 + 9)", $val * 18, $nines - 2, $neg_ok);
dfs("($exp) * (9 - 9)", 0/1, $nines - 2, False);
dfs("($exp) * 9 / 9", $val, $nines - 2, $neg_ok);
dfs("(9 + 9) / ($exp)", 18 / $val, $nines - 2, $neg_ok) if $val != 0;
dfs("(9 + 9) * ($exp)", 18 * $val, $nines - 2, $neg_ok) if $val != 0;
}
# Try adding exactly one 9 to the expression
dfs("$exp + 9" , $val + 9, $nines - 1, True );
dfs("$exp - 9" , $val - 9, $nines - 1, False );
dfs("9 - $exp" , 9 - $val, $nines - 1, False ) if $neg_ok;
dfs("($exp) * 9", $val * 9, $nines - 1, $neg_ok);
dfs("($exp) / 9", $val / 9, $nines - 1, $neg_ok);
dfs("($exp) % 9", $val % 9, $nines - 1, True );
dfs("9 / ($exp)", 9 / $val, $nines - 1, $neg_ok) if $val != 0;
dfs("9 % ($exp)", 9 % $val, $nines - 1, $neg_ok) if $val != 0;
# Try adding no new 9s to the expression as a last resort
dfs(" -($exp)", -$val, $nines, False) if $neg_ok;
}
sub MAIN($limit)
{
dfs("9 / 9", 1/1, 2, True);
dfs("9 - 9", 0/1, 2, False);
dfs("9 + 9", 18/1, 2, True);
dfs("9", 9/1, 3, False);
show_all($limit.Int);
}
```

This program produces the correct output on Niecza; Rakudo/nom does not like it due to its use of autovivification.

Nicely laid out, including nice vertical alignment. Thumbs up.

This solution implements a depth-first search, and differs from the others in
that it hard-codes not only the first level and simple operations, but also
parts of the expressions made of two nines (but why not `9 * 9`

?) and some
operations that involve adding two nines at once.

This makes it much harder to reason about the correctness of the solution, since from it's not obvious if all cases have been considered from just reading it.

On the plus side, it explicitly handles unary minus through special
flag `$neg_ok`

.

Since the programmer has put much thought into the possible solutions, the computer has to do less. Consequentially this is one of the fastest solutions.

Not many idioms new to Perl 6 have been used (`MAIN`

comes to mind),
but the solution is so simple in structure that it doesn't need any
whizz-bang features. You could write that solution in any programming
language that supports string interpolation and rational arithmetic,
and work around the absence of either.

The code seems a bit cluttered due to all the special cases, but it makes every line count without feeling crowded.