[Spoiler] Perl Quiz of the Week #23

I just got back from my weekend away, and haven't read anything yet.
So here's my solution.

The basic idea is to recurse filling 2N slots with N open parentheses.
So I have a function `recurse' that has the number of open parentheses
remaining, the number of slots to fill, and the string so far.  The
basic recursion is that I choose either an open or close parentheses
and recurse.

I first wrote this where I kept a list of indices of the open parens.
However, building the string was really expensive.  When I switched to
the string, it really sped things up.

I tried to optimize by having a function `catalan(N)' that returns a
list of strings, and have it cache the results.  Then, recurse can
have a special case when 2 * $open = $slots.

However, this was horribly inefficient -- most likely because of all
the memory it uses.  Right now, my memory usage is O(n), while my
"optimized" version ended up being O(4**n).

So here is my version.  More comments inline.

    use strict;
    
    # sub main
    {
      die "usage: parens <n>\n" unless scalar(@ARGV) == 1;
      my ($N) = @ARGV;
    
      # Start with N available open parens, 2N open slots, and an empty
      # string.
      recurse($N, 2 * $N, "");
    }
    
    sub recurse
    {
      my ($opens, $slots, $string) = @_;
    
      # Choose whether to add an open paren or close paren at the back,
      # and recurse into each choice.  There are two reasons why we would
      # end the recursion:
    
      # (1) There are no more open parens left to choose.  In this case,
      #     we must be at the beginning, so we just set the remaining
      #     slots to be close parens, and print it.
    
      # (2) There are fewer slots than open/close pairs (2 * $opens), so we
      #     cannot fit the rest in.  We don't print anything in this case.
    
      if ($opens == 0)
      {
        # reason (1)
        print $string, ")"x$slots, "\n";
      }
      elsif (2 * $opens <= $slots)
      {
        # Add open paren
        recurse($opens - 1, $slots - 1, "$string(");
    
        # Add close paren
        recurse($opens, $slots - 1, "$string)");
      }
      # else reason (2)
    }

# Colin Rafferty