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);
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.
Some parts are beautifully vertically aligned, others have missed that opportunity.
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;
Fine.
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.
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.