#! perl6

use fatal;

# TODO:
#  eliminate extraneous ()'s in the output.
#  eliminate negatives when positives would do.
#  faster.
#  code cleanup.

# Utility class to manage our allowable infix ops.
class Infix {
    has Str  $.op;
    has Bool $.assoc;
    has Int  $.level;
}

# An number composed entirely of 9s.
class Nineber {
    has $.value;
    has $.source;
    has $.nines;

    # for our "core" nines.
    method new(Int $nine) {
        my $code = $nine;
        self.bless(*,
            :source($code),
            :value($nine),
            :nines($nine.abs.log10.Int + 1) # num digits
        );
    }

    method build(Nineber $l, Infix $op, Nineber $r) {
        my $code = "(" ~ $l.source ~ $op.op ~ $r.source ~ ")";
        self.bless(*,
            :source($code),
            :value(eval $code),
            :nines($l.nines + $r.nines)
        );
    }
}

# keep track of all the Ninebers we know about
class Nines {
    has %.nines = {}; # first by depth, then by value

    has $!max_depth; # How "long" can our Ninebers be?

    # What operands can we attempt to use?
    has Infix @!ops = (
       Infix.new(:op('*'), :assoc(True),  :level(1)),
       Infix.new(:op('+'), :assoc(True),  :level(2)),
       Infix.new(:op('/'), :assoc(False), :level(1)),
       Infix.new(:op('%'), :assoc(False), :level(1)),
       Infix.new(:op('-'), :assoc(False), :level(2))
    );

    submethod BUILD {
        $!max_depth = 4;
        
        # learn our basics.
        self.memorize(Nineber.new(9));
        self.memorize(Nineber.new(-9));
    }

    method memorize(Nineber:D $nine) returns Bool {
        if $nine.value.abs ~~ Inf ||
           $nine.value ~~ NaN ||
           $nine.nines > $!max_depth {
            return False;
        }

        # autoviv doesn't work in nom.
        if !self.nines{$nine.nines} {
            self.nines{$nine.nines} = {};
            self.nines{$nine.nines}{$nine.value} = $nine;
        } else {
            # prefer the new one if it's shorter.
            my $cur = self.nines{$nine.nines}{$nine.value};
            if !$cur || $cur.source.length > $nine.source.length {
                self.nines{$nine.nines}{$nine.value} = $nine;
            }
        }

        return True;
    }

    # Starting with the basics, learn as much as possible.
    # when starting out, compare everything against everything.
    # for future runs, we only need to compare the new items.

    # when generating numbers to test, don't bother if we know it'll
    # fail ahead of time (# of contained 9s is too large).

    method learn() {
        my @learning = self.getNines();
        while (@learning.elems) {
            my @current_batch = @learning;
            @learning = ();
            for self.getNines() X @current_batch -> $l, $r {
                next if $r.nines + $l.nines > $!max_depth;
                for @!ops -> $op {
                    try {
                        my $nine = Nineber.build($l, $op, $r);
                        if self.memorize($nine) {
                            @learning.push($nine);
                        }
                    }
                    # if our operand is NOT associative
                    # be sure to test it both ways.
                    if !$op.assoc {
                        try {
                            my $nine = Nineber.build($r, $op, $l);
                            if self.memorize($nine) {
                                @learning.push($nine);
                            }
                        }
                    }
                }
            }
        }
    }

    method getNines() {
        my @nines;
        for self.nines.keys -> $depth {
            for self.nines{$depth}.values -> $value {
                @nines.push($value);
            }
        }
        return @nines;
    }

    method hasNine(Int $nine) {
        try {
            self.getNine($nine).elems;
            CATCH {
               return False;
            }
        }
        return True;
    }

    method getNine(Int $nine) {
        my $a = self.nines{$!max_depth}{$nine};

        if $a {
            return $a;
        } else {
             die "no Nine found.";
        }
    }
}

sub MAIN(Int $limit, :$max_depth = 4) {
    my Nines $nines = Nines.new();
    $nines.learn();

    for 0..$limit -> $num {
        if $nines.hasNine($num) {
            say "$num = " ~ $nines.getNine($num).source;
        } else {
            say $num;
        }
    }
}