[SPOILER] Quiz #23 (and a solution that outputs in exactly the same order as the original :-)

I didnt see any mention of anything like two solutions I came up with
for Quiz #23 so i thought id send them through.

My first attempt used binary to generate the patterns and then
validated each appropriate bitstring. Basically we only(!?) need to
iterate the odd integers
0..2**$N-1 (where $N=2n) to find all the possibilitie and then walking
each ones bits to keep track of whether its got a valid pattern .
Obviously this isnt going to scale that well (it takes 13 seconds to
n=10) but it works nicely for smaller numbers. And also paints an
interesting picture. I used 0='(' and 1=')' which means that it
outputs the exact order of the one posted by MJD.

The second attempt uses a queue and perls regex engine to recurse over
the string and build all the possible substrings that can be built by
turning )( into (). I have a feeling that this search can be pruned
better to get better times but I havent worked out how.

For testing purposes and stuff I put the two solutions into their own
subroutines which return a list. I suppose in some respects this isnt
that smart as for larger N it would be a lot more memory efficient to
just print them out straight away. Which actually highlights a
strength in the _int version and weakness in the _rex version. The
latter needs to maintain a hash of previously seen solutions so is
unsuitable for larger N, wheras the _int solution has almost no memory
overhead (were it not building an @array)

Heres the code with output for n=0..4, the number in the parens is the
integer value the pattern represents.

Anyway, this is my first posting here, i hope I have done this right
in terms of ettiquette and this is interesting to you all.

demerphq

#!perl
use strict;
use warnings;

sub parens_permute_int {
    my $n=shift;
    return unless $n;
    my $verbose=shift;
    my $N=2*$n;
    my @paren=qw[ ( ) ];
    my $count=0;
    my @results;
    NUM:
    for(my $int=2**$n-1;$int<2**($N-1);$int+=2) {
        my @bit=split //,sprintf "%0*b",$N,$int;
        my $sum=0;
        BIT:
        for my $pos (0..$#bit) {
            my $digit=$bit[$pos];
            $sum+=$digit ? -1 : 1;
            next NUM if $sum<0          # too many close brackets
                     or $sum>@bit-$pos; # too many open brackets
        }
        if ($verbose) {
            push @results,sprintf "%4d(%4d) %s",++$count,$int,
                    join "",map $paren[$_],@bit;
        } else {
            push @results,join '',map($paren[$_],@bit);
        }
    }
    return @results
}

sub parens_permute_rex {
    my $n=shift;
    return unless $n;
    our (@pattern,%seen);
    local @pattern=("()" x $n);
    local %seen=(@pattern,1);
    my $cur=0;
    while ($cur<@pattern) {
        $pattern[$cur++]=~m/^\((.*?)\)(.*)\((.*?)\)$
          (??{my $str="($1($2)$3)";
              push @pattern,$str unless $seen{$str}++; 'a'})/x;
    }
    #print "$_:$seen{$_}\n" for reverse sort keys %seen;
    return @pattern;
}

unless (@ARGV) {
    warn "Testing.\n";
    for my $n (0..4) {
        print "For \$n=$n:\n";
        my @res1=parens_permute_int($n,1);
        my @res2=sort(parens_permute_rex($n));
        my $num=$#res1>=$#res2 ? $#res1 : $#res2;
        foreach my $i (0..$num) {
            print $res1[$i]=~/\Q$res2[$i]\E/ ? '= ' 
                   : '? ',$res1[$i]||'missing',"  # 
",$res2[$i]||'missing',"\n";
        }
        print "----\n";
    }
} else {
    my ($n,$ver)=@ARGV;
    if ($ver and $ver=~/int/) {
      parens_permute_int();
    } else {
      parens_permute_rex();
    }
}

__END__
Testing.
For $n=0:
----
For $n=1:
=    1(   1) ()  #  ()
----
For $n=2:
=    1(   3) (())  #  (())
=    2(   5) ()()  #  ()()
----
For $n=3:
=    1(   7) ((()))  #  ((()))
=    2(  11) (()())  #  (()())
=    3(  13) (())()  #  (())()
=    4(  19) ()(())  #  ()(())
=    5(  21) ()()()  #  ()()()
----
For $n=4:
=    1(  15) (((())))  #  (((())))
=    2(  23) ((()()))  #  ((()()))
=    3(  27) ((())())  #  ((())())
=    4(  29) ((()))()  #  ((()))()
=    5(  39) (()(()))  #  (()(()))
=    6(  43) (()()())  #  (()()())
=    7(  45) (()())()  #  (()())()
=    8(  51) (())(())  #  (())(())
=    9(  53) (())()()  #  (())()()
=   10(  71) ()((()))  #  ()((()))
=   11(  75) ()(()())  #  ()(()())
=   12(  77) ()(())()  #  ()(())()
=   13(  83) ()()(())  #  ()()(())
=   14(  85) ()()()()  #  ()()()()
----




-- 
First they ignore you, then they laugh at you, then they fight you,
then you win.
  +Gandhi