[SPOILER] Solution for Quiz of the Week #23 : parens

I was expecting my solution to be unique, but I see that Kester Allena,
and yves had the same thoughts of using binary numbers to represent the
output. Once your map 0 -> '(' and 1 -> ')' you realize you can count
from '0'x$N . '1'x$N .. '01'x$N (eg: N=4; 00001111 -> 01010101) and
print out any string that has the same number of '('s as ')'s which you
can count and replace with tr///.

This could probably be optimized more since the difference
between consecutive numbers create a repeating pattern.  But anyway,
here is my small, but somewhat slow for large values of N, solution.

~% /usr/local/bin/perl -v
This is perl, v5.6.1 built for sun4-solaris

~/bin% uname -a
SunOS landsraad 5.8 Generic_108528-29 sun4u sparc SUNW,Sun-Fire-480R

~% /usr/bin/time ./parens 10 > /dev/null
real        0.9
user        0.9
sys         0.0

~% /usr/bin/time ./parens 12 > /dev/null
real       15.2
user       15.0
sys         0.1

~% cat ./parens
#!/usr/local/bin/perl
my @out = ();
my $N = shift;
my $N2 = $N * 2;
my $i = oct("0b" . "0"x$N . "1"x$N);
my $e = oct("0b" . "01"x$N);
do {
    $_ = sprintf("%0*b",$N2,$i);
    push(@out,$_) if (tr/0/(/ == tr/1/)/);
    $i += 2;
} while ($i <= $e);
print join("\n",@out) . "\n";

__END__


-- 
Kevin Earls                    Email:  [email protected]
Unix System Administrator      Voice:  (903) 868-7208
Standard Linear & Logic        Pager:  (903) 620-2067
Texas Instruments                FAX:  (903) 868-5616