Re: Perl Quiz of the Week #23

On Thu, 2 Sep 2004 23:05:03 -0700, Yitzchak Scott-Thoennes
<[email protected]> wrote:
> On Wed, Sep 01, 2004 at 12:50:14PM -0400, Mark Jason Dominus wrote:
> > and for argument '4', the output should be:
> >
> >         (((())))
> >         ((()()))
> >         ((())())
> >         ((()))()
> >         (()(()))
> >         (()()())
> >         (()())()
> >         (())(())
> >         (())()()
> >         ()((()))
> >         ()(()())
> >         ()(())()
> >         ()()(())
> >         ()()()()
> >
> > in some order.
> 
> That's a very strange sample order; I have a hard time picturing an
> algorithm coming up with it.  I'd expect "((()))()" to come after
> "(()()())".

I think my program produces this exact order if I reverse one loop.

> It's going to be a long 60 hours; I've got a simple recursive solution
> (that I haven't had the patience to see if it will finish 15 pairs), a
> somewhat faster iterative by generation solution (that runs out of
> memory for 16 pairs), and am working on a memory-friendly subroutine
> that looks up the Nth string of a given width, that I'm hoping to
> transmogrify into a memory-friendly but fast-enough full solution.

Mine uses lots of memory :-(