Re: [SPOILER] Solution to QOTW #23 in Haskell

This is a direct port of my Haskell solution to Perl. I'm not claiming 
it's the most efficient way to do it, but it does work and might help 
people understand my approach. Directly translating functional 
programming concepts into an imperative language of course isn't usually 
the best of ideas if you want things to run fast.

Anyway, timings (1GHz G4 Powerbook, OS X 10.3.5, Perl 5.8.1-RC3) show:

parens 12:
real    0m26.726s
user    0m6.970s
sys     0m1.010s

parens 10:
real    0m2.464s
user    0m0.700s
sys     0m0.070s

Which are remarkably similar to my Haskell implementation.

Also, I recompiled the Haskell implementation with -O2 to enable GHC's 
optimisation system, and it knocks about two seconds off the time of 
parens 12 on my Powerbook, and less than a second off parens 10 (that's 
within the noise).

#!/usr/bin/perl

use strict;
use warnings;

my $num = shift || die "Usage: $0 <num>\n";

sub buildvalid {
  my $open = shift;
  my $to_go = shift;
  my $so_far = shift;
  
  if($to_go == 0) {
    return ($so_far);
  }
  elsif($open == 0) {
    return buildvalid(1, $to_go - 1, $so_far . '(');
  }
  elsif($open >= $to_go) {
    return buildvalid($open - 1, $to_go - 1, $so_far . ')');
  }
  else {
    return (buildvalid($open - 1, $to_go - 1, $so_far . ')'), buildvalid($open + 1, $to_go - 1, $so_far . '('));
  }
}

print "$_\n" foreach buildvalid(0, $num * 2, '');