t1/edgar

Download the raw code.

# -*- 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);

Correctness

This produces correct output on Niecza. Since it was written before Niecza supported sub MAIN properly, it contains an explicit call to MAIN(|@*ARGS) at the end, which means it produces double output on newer versions of Niecza. Of course that doesn't shed negative light on this solution, rather it highlights the high development velocity of Niecza.

Consistency

Some parts are beautifully vertically aligned, others have missed that opportunity.

Clarity of intent

All the names are carefully chosen, the subroutines short and to the point. It could be argued that parenthesized is not an excellent name for a method that sometimes parenthesizes its argument, and sometimes not.

It could be seen as odd that Term gets its own class, but the operators are kept in an array that acts as an ad-hoc data type.

It is laudable that unary minus is taken fully into account, with a complexity tracker to avoid infinitely repeated application of it.

The comments, only repeating what subsequent code already expresses clearly, mostly take up extra lines and don't add anything.

# A term
class Term {

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

Algorithmic complexity

Fine.

Idiomatic use of Perl 6

Many nice idioms appear in the code, including Whatever-currying, higher order functions, the cross operator and hyper method calls.

The only surprise for a seasoned Perl 6 programmer is the ues of type constraints when a sigil would have done, for example Array $term and Callable $can-combine. These can be better written @term and &can-combine, respectively.

Brevity

Not brief. On the upside it does more than the other solutions, first by properly taking unary minus into account, and secondly by tracking precedence levels to avoid some unnecessary uses of parenthesis.