Re: Some random reflections on tpr05a

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