Re: [SPOILER] Perl Quiz of the Week #23

Hello all,

I posted my script without testing for "0" and "1" in the
input.  The regex in the for(;;) doesn't work for these
special cases.

I append the script corrected to catch these special cases up
front.

For n == 2 to 13, the Catalan count published by Colin Rafferty
last week are correct in this script.  Here is the output of
"time parens $N > p$N", pasted against "wc -l < p$N".

2: 0.02u 0.02s 0:00.06 66.6%	       2
3: 0.03u 0.03s 0:00.05 120.0%	       5
4: 0.02u 0.03s 0:00.06 83.3%	      14
5: 0.01u 0.04s 0:00.06 83.3%	      42
6: 0.03u 0.02s 0:00.07 71.4%	     132
7: 0.11u 0.02s 0:00.13 100.0%	     429
8: 0.32u 0.02s 0:00.35 97.1%	    1430
9: 1.25u 0.03s 0:01.28 100.0%	    4862
10:5.06u 0.01s 0:05.11 99.2%	   16796
11:20.82u 0.08s 0:20.94 99.8%	   58786
12:86.09u 0.06s 1:26.30 99.8%	  208012
13:354.32u 0.20s 5:55.31 99.7%	  742900


Corrected script:
----------------------\/--------BEGIN---------\/----------------------
#!/usr/bin/env perl

# Intention: MJD's QOTW #23.

# $Id: matching-parens.pl,v 1.11 2004/09/07 15:31:45 ksundar Exp ksundar $

# Core idea:
# * Use "0" to indicate left parens and "1" for right parens.
# * Step from "0000...1111" (maximal nesting) to "010101...01" (zero nesting).
# * If balanced, translate to parens and print.
#
# Advantages of zero-one:
# * I find zero's and one's easier to think about than left and right parens.
# * No need to backslash "\(" and "\)" in regexps.
# * $x computation in &parity is simpler.
#
# Disadvantages:
# * It needs $x and y/// before printing.

use 5.006; use strict; use warnings; $^W = 1;

my $N=shift;

# Take care of the two special cases that the for(;;) doesn't like.
exit 0 if !$N;
print "()\n" and exit 0 if $N == 1;

my $x;

for ($_ = ((0 x $N) . (1 x $N)); # Maximal nesting: "0000...1111"
     ! /^(01)+11$/;              # Haven't gone past zero nesting.
     s/0(1*)1$/1 . (0 x length($1)) . 1/e   # Step along.
    ) {
    ($x=$_) =~ y/01/()/, print $x, "\n"
        if ((y/0/0/ == y/1/1/) && &parity);
} # for

exit 0;

sub parity {
    my $x;
    for (split "") {
        return 0 if ($x += $_ ? -1 : 1) < 0;
    }
    1;
} # &parity

__END__

Buggestions:
----------------------/\---------END----------/\----------------------


peace,          || Byatrayanapura: Better governance thru online taxes:
--{kr.pA}       || http://tinyurl.com/296js
-- 
"If I have not seen farther, it is because giants have stood on my shoulders."
    -- V. Guhan.  [with apologies to Newton, Sir Isaac.]