Download the raw code.
#! 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;
}
}
}
This code produces the right output, when run with a recent revision of Rakudo.
The use of exceptions for non-exceptional control seems strangely out of place, given that the method that raises them does not do any out-of-bands checks, but simply checks the truth of the return value.
The code consists of three class declarations, each with its own purpose, and then a MAIN sub with just a small bit of code that instantiates one of the classes and produces the output. So far so good.
Signs of haste are clearly visible, in form a TODO list in the comments,
and artifacts like unused variables ($max_depth in MAIN) and even an unused
attribute ($.level in class Infix).
Others impair readability a bit more:
# 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
);
}
You can observe three different names ($nine, $code and source) for the
very same value, plus an unnecessary level of generality -- the comment even
says it's only for the "core" nines, which have always just one nine.
The problem with different names for the same thing reappears later on. What
is nines in class Nineber is called depth in class Nines.
Other parts of the code demonstrate why broadly catching all exceptions is often a bad idea:
# from method memorize
if !$cur || $cur.source.length > $nine.source.length {
self.nines{$nine.nines}{$nine.value} = $nine;
}
often throws an exception, because there is no method length in class Str
(it's called chars in Perl 6), but the broad use of try statements around
each call to memorize hides that bug.
We don't know where exactly it goes wrong, but something is wrong. Other solutions take between 5 and 15 seconds on one particular machine to generate all the possible expressions, whereas this one takes over three minutes.
Maybe it's because it doesn't proceed by depth, but instead repeatedly takes all known expressions and tries to recombine them to new ones, thus very often considering to generate expressions of too high a depth. The number of possible expressions increases exponentially with depth, making the approach inefficient.
There are several nice Perl 6 idioms, including iterating over .keys of an
array, sub MAIN, various ways of constructing objects and usage of the cross
operator X to iterate over all combinations of two lists.
On the other hand, several low-hanging shortcuts have not been taken, for
example :assoc(True) and :assoc(False) could have simply been :assoc and
:!assoc.
Not brief.