En op 08 september 2002 sprak Tina Mueller:
> the thing which is interesting for me with every new hole is
> the algorithm. (i have yet to understand eugene's one =)
The algorithm is nothing special. It's just hard to see what's
happening because of the compactness of my shortest solution.
The winning solution:
#!perl -p
sub
w{s/
([@_^+-])(.*)/ $2 $1/g}sub
f{s/\(([^()]+)\)/f($_=$+)/e?&f:w~w;$_}f
s/\s//g/s/\d+/$&
/g
Rewritten:
#!perl -p
sub w{
s/\n([@_^+-])(.*)/ $2 $1/g
}
sub f{
s/\(([^()]+)\)/$_=$+;&f/e ? &f : w(~w);
$_
}
s/\s//g;
s/\d+/$&\n/g;
f
What happens is this:
First, all whitespace is removed. Then every operator is marked by a
newline. This newline indicates that this operator has not yet been put
into RPN:
1+2*3+4*(5+6)+7 => 1\n+2\n*3\n+4\n*(5\n+6\n)+7\n
The "\n" precedes each operator, but not always directly. When there are
parens, it's inside them. This is not a problem for my algorithm, since
it deletes the ()'s and leaves the \n's alone.
Now the parenthesised expressions are resolved, starting with the
innermost expressions. The logic is similar to that of
1 while s/\(([^()]+)\)/$_=$+;&f/e;
The result is:
1\n+2\n*3\n+4\n*5 6 +\n+7\n
The function w is called twice: once without arguments, and once with an
argument. w() without argument puts the multiplications (but only those
preceded by \n's) in the proper order:
1\n+2 3 *\n+4 5 6 + *\n+7\n
and w called with an argument treats the additions:
1 2 3 * + 4 5 6 + * + 7 +\n
Interestingly, this use of \n as a marker was not my idea at all, it
just haoppened. My idea was to use two markers, to indicate the parts of
the expression that were already in RPN. To start with, this would mean
only the numbers:
a1z + a2z * a3z + a4z * (a5z + a6z) + a7z
and then to remove those markers as soon as a part of the expression was
put into RPN:
=> a1z + a2z * a3z + a4z * a5 6 +z + a7z
=> a1z + a2 3 *z + a4 5 6 + *z + a7z
=> a1 2 3 * +z + a4 5 6 + *z + a7z
... => a1 2 3 * + 4 5 6 + * + 7 +z
Look at my 175.67 solution to see how that worked. This solution
contained the regexp m#z([*/])a(.*?)z# . Notice the non-greedy match,
which could also be written as a([^z])z. When I replaced the end marker
with a newline, I could just use (.*). And then I didn't need the -l
command switch. And it had a better tie-break score.
And later, I tried to remove the begin marker 'a', and it worked! This
was a big but not unwelcome suprise.
So my final solution used a different algorithm than my first, and that
happenedpurely by coincidence. I didn't even know how my solution
actually worked before I started writing this mail.
OK, this is probably more than you wanted to know, but "To write is to
delete, and this post wasn't worth the effort to delete", as a wise man
once said [1].
(-ugene
[1] Herman Finkers
--
The competent programmer is fully aware of the strictly limited size of
his own skull; therefore he approaches the programming task in full
humility, and among other things he avoids clever tricks like the
plague. -- (-dsger |)ijkstra
