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