# t1/zbiciak

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

## Correctness

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

## Consistency

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

## Clarity of intent

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`.

## Algorithmic complexity

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.

## Idiomatic use of Perl 6

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.

## Brevity

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