On Mon, 9 Sep 2002, Eugene van der Pijll wrote:
> 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.
what an understatement =)
> 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
i had the something about the same in the postorder hole.
every "finished" leaf/subtree had a newline before it,
so .* would not match it the next time. but i didn't
think this trick could be applied to this hole in any way...
[further explanation]
thanks, i think i roughly got it. i will have a look at the details...
> 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
you wouldn't need two markers. a\d+ would be enough cause
after a number there will always follow a non-digit.
that's what our solution made:
put every innermost expression in the stack, (that means expressions
in parentheses or surrounded by '+' or '-') and replace it with
'a'.index of stack element.
=> 1+2*3+4*(5+6)+7
--- ---
a0 = 5+6 = 5 6 +
a1 = 2*3 = 2 3 *
=> 1+a1+4*a0+7
---- ----
a2 = 1+a1 = 1 a1 +
a3 = 4*a0 = 4 a0 *
=> a2+a3+7
a4 = a2+a3 = a2 a3 +
=> a4+7
a5 = a4+7 = a4 7 +
=> a5
now roll it out again with the values in the stack:
1 while s/a(\w+)/$stack[$1]/
stack:
a0 = 5 6 +
a1 = 2 3 *
a2 = 1 a1 +
a3 = 4 a0 *
a4 = a2 a3 +
a5 = a4 7 +
=> a5
--
=> a4 7 +
--
=> a2 a3 + 7 +
-- --
=> 1 a1 + 4 a0 * + 7 +
-- --
=> 1 2 3 * + 4 5 6 + * + 7 +
> 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].
no, thanks for the explanation. at least i can say we had one similar idea
with the "a"-marker =)
i hope the description of our only 165 strokes-solution wasn't too boring...
tina
--
http://www.tinita.de/ \ enter__| |__the___ _ _ ___
http://Movies.tinita.de/ \ / _` / _ \/ _ \ '_(_-< of
http://PerlQuotes.tinita.de/ \ \ _,_\ __/\ __/_| /__/ perception
