Re: [SPOILER] Solution for QOTW 23

Jonathan Weed <jweed-Zy/[email protected]>:
> I can't wrap my head around precisely what's happening or, even more
> murky, how you thought this one up.  Can you shed some light for the
> not-quite-perl /algorithmic-hackers?

I can explain how I thought it up, although I'm not sure whether the
explanation will be helpful or whether it will sound like "I just
counted the legs and divided by four."

I had originally planned to write a recursive solution, but before I
started I thought it would be smart to investigrate alternative
representations.   One of the representations I looked at was the one
mentioned by Pr. Burton West elsewhere on this list.  In this
representation, a string of one "(" followed by n ")"'s becomes the
number n, so

        ()()()()        1111
        ()()(())        1102
        ()(())()        1021
        ()(()())        1012
        ()((()))        1003
        (())()()        0211
        (())(())        0202
        (()())()        0121
        (()()())        0112
        (()(()))        0103
        ((()))()        0031
        ((())())        0022
        ((()()))        0013
        (((())))        0004

Now if you look at the right-hand column, and at the way the numbers,
change, it will seem awfully familiar.  Or at least, it felt familiar
to me.  It reminded me very strongly of a counting process.  

The essence of a counting process is that you find the rightmost
column that has a certain property, and then you do a little
transformation on it so that it gets a little less of that property
and the columns to the right get reset to have more of it.

I realize that if you've never thought of it that way that is going to
sound totally bizarre, so here's an example.  Let's count base-10
numerals.  The magic property in this case is the property of being
less than 9.  You find the rightmost column that is less than 9 and
then you do a little transformation on it so that it has a little more
of that property, so that it is closer to 9:

        387
        388
        389

after you have done that a few times, you get to a point where the
rightmost column's less-than-9-ness has been entirely depleted and you
can't change it any more.  So you move to the next column to the left
and deplete that one instead, and you reset the rightmost column so
that it is full of less-than-9-ness again:

        390

and then you continue

        391
        392
        ...
        399

and now you have to deplete the less-than-9-ness of the third column,
and reset the two to its right:

        400

Tis may be a weird way to look at counting, but it describes all sorts
of useful processes.   To count in base 2, you allow the columns to
hold 0's and 1's, and the property of interest is the property of
being a 0; you find the rightmost column that is a 0, and change it to
a 1, and change the columns to its right back to 0's.

Probably the next simplest example is when the property of interest is
that the n'th column contains a number less than or equal to n:

        0000
        0010
        0100
        0110
        0200
        0210
        1000
        1010
        1100
        1110
        1200
        1210
        2000
        2010
        ...
        3210

This turns out to be really useful if you are trying to enumerate
permutations; I wrote about it at some length in my book.
(http://perl.plover.com/book)

Another example I was already familiar with was the one that is like
the base-2 counting example, but with the added restriction that you
can't have two adjacent 1's:

        0000000
        0000001
        0000010
        0000100
        0000101
        0001000
        0001001
        0001010
        0010000
        0010001
        0010010
        0010100
        0010101
        0100000
        ...

We could imagine that someone is doing

        s/00((10?)*)$/"01" . "0" x length $1/e;

over and over.

(This pattern has close relations to the Fibonacci sequence.  For
example, the Nth pattern has the form 0*10+ exactly when N is a
Fibonacci number.  Also every positive integer has a unique
representation as a sum of distinct Fibonacci numbers, and this
counting thing tells you how to represent it that way.  This is
analogous to the way that every positive integer has a unique
representation as a sum of powers of 2, and the binary expansion tells
you what the representation is.)

So anyway, I was already familiar with this idea, and when I saw the
parenthesis numbers, it reminded me strongly of one of these counting
processes:

        1111
        1102        
        1021
        1012
        1003
        0211
        0202
        0121
        0112
        0103
        0031
        0022
        0013
        0004

Here the rule seems to be that you always decrement the rightmost
nonzero number, except that you're not allowed to decrement the very
rightmost column.  The rules about nesting of parentheses impost the
constraint that the sum of the leftmost K columns cannot exceed K.
Under this restriction, "1111" is clearly the first pattern, and the
1's can only move rightward.  So to go from "1111" to "1102", the
rightmost moveable 1, which is in the third column, is moving to the
right. Now the rightmost 1 is in the second column.  so we reset the
columns to the right of that (getting back 1111) and then move the 1
from the second to the third columns, yielding 1021.  Now the 1's in
the third column can move right, yielding 1012 and then 1003.

Now we'll need to move the 1 from the first to the second column, so
we reset the columns to the right of that (getting back 1111 again)
and move the 1 from the first to the second column, yieling 0211.
Then the 1 in the third column moves, yielding 0202, and then we reset
the third and fourth columns back to 0211 so that we can move a from
the second to the third column, yielding 0121.

My first cut at implementing this actually had

output while s/([1-9])(0*)([1-9])$/($1-1).($3-length($2)+1).1x length($2)/e;

manipulating digit strings like "1021" directly.  This meant it
wouldn't work for N>9.  But after I thought about it some more, I
realized I didn't need to deal with the digit strings; I could
directly manipulate the parentheses in the corresponding way.  This
was faster, simpler, and got rid of the N<10 restriction.

Translated back into parentheses, the algorithm might even be simpler
to understand.  In "()()()...()", the open parentheses are as far to
the right as they can be.  So this represents a sort of minimal
configuration.  At each step, we're going to find the rightmost
moveable open parenthesis, and we're going to move it one step to the
left.  And if there are other immovable parentheses to the right of
that one, we'll reset them into their minimal configuration.

        ()()()()                        1111

Here the rightmost movable ( is the fourth one, so we move it left
one space.

        ()()(())                        1102

Now the rightmost moveable ( is the third one; moving the fourth one
left one space doesn't change anythig. So we move the third one a
space left, and reset the later parentheses to the minimal
configuration:

       ()(())()                         1021

Now the fourth open parenthesis can move again:

       ()(()())                         1012

And again:

       ()((()))                         1003

Now the second one will move, and we reset the third and fourth:

        (())()()                        0211

etc.

After I had implemented that, I realized there was nothing stopping me
from reversing everything and doing the substitutions at the left end
of the string instead of at the right end.  This is always much
cheaper in perl's regex engine because it doesn't have to guess where
to start matching in the target string.  So I reversed the whole
thing.  It no longer produced the parentheses in lexicographic order
(unless you read right to left) but it was substantially faster.

I hope that was of some value.