Re: [Spoiler] QotW 23

Rod Adams <[email protected]> writes:

> sub Insert {
>   # Given any previously properly balanced string of parens, including the
>   # empty string, you can insert a '()' at any position you feel like, and
>   # it will remain a properly balanced string.
>   # Unfortunately, I couldn't come up with a way of doing this to avoid
>   # creating the same pattern more than once, so I had to add a %seen hash.
>
>   my ($length) = @_;
>   my %seen = ();
>   _insert('',$length);
>
>   sub _insert {
>     my ($string, $left) = @_;
>     for (my $x = 0 ; $x <= length($string) ; ++$x) {
>       my $newstring = $string;
>       substr($newstring,$x,0,'()');
>       next if $seen{$newstring}++;
>       if ($left == 1) {
>     print "$newstring\n" if EnablePrint;
>       } else {
>     _insert($newstring, $left - 1);
>       }
>     }
>   }
> }

And Bruce J Keeler wrote up essentially the same algorithm in a post
which I haven't gotten through the digest yet.

Anyway, I thought I'd let you know that I've discovered a very simple
way to avoid the necessity of a "seen" hash.  When I remove this from
the program, Bruce Keeler's variation on insert is actually faster
than his second solution (in perl - the C version blows everything
else away in terms of speed) and is even faster than MJD's regexp
monstrosity, which I'm still figuring out.

So here's how to remove the %seen hash; comments continued below:

#!/usr/bin/perl -w

use strict;

my $length = 2 * (shift || 0);

die "Usage: parens <n>\n" unless $length > 0;

my @pipeline = ("()");

while(@pipeline) {
    my $item = shift @pipeline;

    my $limit = index $item, ')';
    for(my $i = 0; $i <= $limit; $i++) {
        my $newitem = $item;
        substr($newitem, $i, 0) = "()";
        if (length $newitem == $length) {
            print "$newitem\n";
        } else {
            push @pipeline, $newitem;
        }
    }
}

__END__

This has the disadvantage of not nicely handling the case when n=0,
but Bruce's program was already die'ing in that case anyway.  I
figured out this by running Bruce's program and then using
Data::Dumper to print out %seen.  Here's what I got - the pattern
should be obvious:

$VAR1 = {
          '(())()()' => 3,
          '()()' => 2,
          '(())' => 1,
          '(()())()' => 3,
          '(())()' => 2,
          '(()()())' => 3,
          '(((())))' => 1,
          '()(()())' => 3,
          '(()())' => 2,
          '()(())()' => 3,
          '(()(()))' => 2,
          '((()))()' => 2,
          '()(())' => 2,
          '()((()))' => 2,
          '()()()' => 3,
          '()()()()' => 4,
          '()' => 1,
          '((())())' => 2,
          '()()(())' => 3,
          '((()()))' => 2,
          '(())(())' => 2,
          '((()))' => 1
        };