# -*- mode: cperl6; -*-

# 2011 Perl 6 Coding Contest
# Edgar Gonzàlez i Pellicer

use v6;


# A term
class Term {
  has Real $.value;
  has Str  $.expression;
  has Int  $.precedence;
  has Int  $.complexity;

  # Parenthesized
  # When precedence in the context is higher
  method parenthesized(Int $precedence) {
    if $precedence < $.precedence {
      return $.expression;
    }
    else {
      return "($.expression)";
    }
  }
}


# Applicability tests
sub all-ok(Term $, Term $) { True }
sub non-zero-divisor(Term $, Term $div) { $div.value != 0 }

# Available binary operations
my @binary =
  [ &all-ok,	       * + *, '+', 1 ],
  [ &all-ok,	       * - *, '-', 1 ],
  [ &all-ok,	       * * *, '*', 2 ],
  [ &non-zero-divisor, * / *, '/', 2 ],
  [ &non-zero-divisor, * % *, '%', 2 ];


# Combine with a binary
sub combine-binary(Term $left, Term $right, Callable $can-combine,
		   Callable $function, Str $symbol, Int $precedence) {
  # Can we combine?
  if $can-combine($left, $right) {
    # Parenthesize expressions (if needed)
    my $l-exp = $left.parenthesized($precedence);
    my $r-exp = $right.parenthesized($precedence);

    # Combine
    return Term.new(value      => $function($left.value, $right.value),
		    expression => "$l-exp $symbol $r-exp",
		    precedence => $precedence,
		    complexity => $left.complexity + $right.complexity + 1);
  }
}


# All binary combinations
sub binary-combinations(Term $left, Term $right) {
  return @binary.map: { combine-binary($left, $right, |$_) }
}


# Available unary operations
my @unary =
  [ - *, '-', 3 ];


# Combine with an unary
sub combine-unary(Term $term, Callable $fun, Str $symbol, Int $prec) {
  # Parenthesize expression if needed
  my $t-exp = $term.parenthesized($prec);

  # Combine
  return Term.new(value      => $fun($term.value),
		  expression => sprintf('%s%s', $symbol, $t-exp),
		  precedence => $prec,
		  complexity => $term.complexity + 1);
}


# All unary combinations
sub unary-combinations(Term $term) {
  return @unary.map: { combine-unary($term, |$_) }
}


# Simplest term (in terms of complexity)
sub simplest(Array $terms) {
  return $terms.min: { .complexity };
}


# Number of nines
constant $number-of-nines = 4;

# Nined values
my %nined-values;

# Find'em
sub find-nined() {
  # Constructed terms
  my @terms;

  # Terms with 0 and 1 nine
  @terms[0] = [];
  @terms[1] = [ Term.new(value      =>  9, expression =>  '9',
			 precedence =>  4, complexity =>   1),
		Term.new(value      => -9, expression => '-9',
			 precedence =>  3, complexity =>   2) ];

  # With more...
  for 2 .. $number-of-nines -> $n {
    # Current terms
    my @current;

    # Left-side size
    for 1 .. ($n - 1) -> $l {
      # Right-side size
      my $r = $n - $l;

      # Apply binary
      @current.push(
          (@terms[$l].list X @terms[$r].list).map: &binary-combinations);
    }

    # Apply unary
    @current.push(@current.map: &unary-combinations);

    # Find simplest ones
    @terms[$n] = (@current.classify: { .value })>>.value.map: &simplest;
  }

  # Index the last one
  for @terms[$number-of-nines].list -> $t {
    # Is the result integer?
    my $v = $t.value;
    if $v ~~ Int || ($v ~~ Rat && $v.denominator == 1) {
      # Store it
      %nined-values{$v.Int} = $t.expression;
    }
  }
}


# Main
multi sub MAIN(Str $limit) {
  # Find all nined values
  find-nined;

  # Find the values
  for 0 .. $limit.Int {
    # Is it a nined value?
    if %nined-values.exists($_) {
      say("$_ = %nined-values{$_}");
    }
    else {
      say($_);
    }
  }
}

# Call main
MAIN(|@*ARGS);