I can offer some explanation, along with a little theoretical backgound, of
my 109.51 solution (I was quite amazed to reach the same exact score as
Alexey Rudenko with a completely different solution!) which I recall here:
-p y/ //d;s/\b\D/x$&/g;s--$_=$1;s// $2 $1/while/x(.)(\PL+)/+/x([*\/])(\PL+)/;
$_-ewhile/(.+)x/+/\(([^()]+)\)/
At first, I wanted to bracket the parts that were left to be done (like the
a...z of Eugene); I quickly realized that only one kind of brackets was
required, so it was really quoting rather than bracketing. Remembering that
/\pL/ matches a letter (as opposed to /\w/ which matches an alphanumeric), a
trick that was used by mtve in a previous mini-golf course, I chose x to quote
my expression: an expression that was left to be done was matched by /x\PL+x/.
Also, the input was very easy to quote with the substitution s/\b/x/g (once the
whitespaces were removed; this was my favorit bit and I was a bit sad to remove
it later...)
A real improvement was achieved when I understood that I didn't need to quote
whole expressions: in this problem, the only thing that we needed to do was
to move the operators around a bit. Therefore, I needed only to mark operators
that were left to be done, and process them in order. The processing itself is
surprisingly easy: find the left-most marked operator in processing order,
unmark it, and move it right in front of the next marked operator, or the end
of the string.
Suppose that we are only dealing with flat infix expressions, with no
parentheses; processing 1 + 2 * 3 + 4 would look like:
preprocess the input: 1x+2x*3x+4
do the multiplication first: 1x+2 3 *x+ 4
do the first addition: 1 2 3 * +x+ 4
and the second one: 1 2 3 * + 4 +
We need two regular expressions to find the right processing order. At first,
I wrote something like:
s// $2 $1/ while /x([*\/])(\PL+)/ || /x([+-])(\PL+)/
this matches all marked * and / before matching any + or -. The use of || in
place of the more compact | was really frustrating, then I realized that since
| evaluates both operands (when || evaluates only the first if true), I could
simply change the order of the operands to get the desired result. Moreover,
since a mark could only be followed by an operator, I could simplify this
further:
s// $2 $1/ while /x(.)(\PL+)/ + /x([*\/](\PL+)/
(the + has the same effect as the | here, with the benefit of improving the
tie-breaker score, which I needed badly to match Alexey's score). Note here
that I am also exploiting the empty regex, which repeats the last match. I'll
be very sad to see it go in Perl 6.
The only problem left was the parentheses, which are treated bottom-up: process
the innermost parenthesized subexpression, removing the parentheses in the
process, and repeat while there are no parens left. The only problem was that
the main expression was not necessarily parenthesized; at first, I just put
parentheses around $_, but it was too costly stroke-wise. So I used the same
trick as above, that is matching any parenthesized expression or, if there are
none left, unparenthesized expressions. This leads to the outer iteration:
s//$_=$1;...;$_/e while /(.+)x/+/\(([^()]+))\)/
The last x was put during preprocessing because it is followed by a newline,
which is kept for the ouput. Then we just have to include the inner loop inside
the substitution, not forgetting the -e flag, and we are done! Whew.
On the theoretical side, the very simple idea of iterating a regular substution
until a fixed point is reached in order to recognized expressions that are not
regular is found in [1], for instance; I am also discussing it in my PhD thesis
which I am supposed to finish instead of playing perl golf. On the other hand,
I might include the parsing of infix arithmetic expressions using weighted
finite-state transducers as an example in my dissertation, so this round of
golf was really beneficial for me!
Sorry for the long post, I hope it was clear to everyone.
pom
[1] Emmanuel Roche: Two Parsing Algorithms by Means of Finite State
Transducers. Proceedings of COLING-94, pp. 431--435, Kyoto, Japan,
August 1994.
