[SPOILER] Solution for QOTW 23

My first attempt is slightly different from some others.

Rather than generate valid paren strings, this generates *all* paren
strings of a given size, then just discards invalid ones.  The bit
checks run okay, but it's still exponential due to the numeric
generation.


#!/usr/bin/perl
use warnings;
use strict;

my $size = shift;
ATTEMPT: foreach my $attempt (0 .. 2**(2 * $size - 1))
{
   my $sum;
   my $string;
   foreach my $bit ( 0 .. (2 * $size) - 1)
   {
      if (($attempt >> $bit) & 1)
      { $sum++; $string .= "(";}
      else
      { $sum--; $string .= ")";}
      next ATTEMPT if ($sum < 0);
   }
   print "$string\n" if ($sum == 0);
}


My second attempt was standard recursion.  I represented a paren string
as a path along a grid from (n,n) to the origin, where all steps could
only be -x, or -y, and you can't cross the x=y diagonal.

The main problem is that components in the field are constantly
recomputed.  Memoization works only until the machine runs out of memory
(or swaps badly).  I was able to get much further on my machine by
disabling memoization.

#!/usr/bin/perl
use warnings;
use strict;
#use Memoize;
#memoize('paren_string');

# How long?
my $size = shift;

foreach (paren_string($size,$size))
  {  print "$_\n"; }

sub paren_string
  {
    my ($x, $y) = @_;
    die "Called as $x,$y" if ($x < $y);
    if ($x > $y and $y > 0)
      {
        my @tmp;
        push @tmp,	
          map { "($_" } paren_string($x, $y-1);
        push @tmp,     map { ")$_" } paren_string($x-1, $y);
        return @tmp;
      }
    elsif ($y > 0) # $x == $y
      {  return map { "($_" } paren_string($x, $y-1); }
    elsif ($x > 0)  # $y == 0
      {  return map { ")$_" } paren_string($x-1, $y); }
    else # $x == $y == 0
      {  return ""; }
  }

-- 
Darren Dunham                                           [email protected]
Senior Technical Consultant         TAOS            http://www.taos.com/
Got some Dr Pepper?                           San Francisco, CA bay area
         < This line left intentionally blank to confuse you. >