[SPOILER] my solution to Perl Quiz of the Week #23

Jereme Corrado <jereme-eOgykUXTlIE4oC6ZuLIW0ln8z39Dn/[email protected]> Sat, 4 Sep 2004 20:27:39 -0400

Newsgroups	gmane.comp.lang.perl.qotw.discuss
Message-ID	<[email protected]>

Here is my solution, it's very straight forward.  I used a recursive
algorithm as it just seamed more natural, though I do pay a penalty in
speed.

Once this was running, the part I found most interesting was looking
at the patterns in the output and how they changed as I adjusted my
code.  I decided to make matching pairs the same color so I could pick
them out more readily.  This also added a little challenge as far as
matching open and close parens correctly, (which isn't too hard but my
first thought fell flat).  This is also the first time I have played
with color output in console, which probably isn't very portable.

Also, I read allot of people's evaluations of the memory usage of
their code.  I am interested to see this as well, how do folks go
about checking this out?  My method was kind of clunky, I just put in
"sleep 10000000" as my last statement and looked at the output of
`top'.  Comments and better methods always welcome.

parens.pl (application/x-perl, 1.1 KB)

#!/usr/bin/perl -w

# Print permutations of pretty pairs of parenthesis.

use strict;
use Term::ANSIColor ':constants';

my $PAIRS = $ARGV[0];
die "we need a number of pairs to print\n" 
    unless $PAIRS && $PAIRS =~ /[[:digit:]]/;

my @colors = (RED, YELLOW, GREEN, BLUE, MAGENTA);
my $num_colors = scalar @colors;
my $col_index = 0;

build([1]);

sub build{
    my $string = shift;

    if (my $branches = get_branches($string)){
	for (@$branches){
	    build([@$string, $_]);
	}
    }else{
	print_string($string);
	print RESET;
    }
}

sub get_branches{
    my $string = shift;

    my $possible_branches;
    my ($o, $c) = (0, 0);
    for (@$string){ $_ ? $o++ : $c++ }
    if ($o < $PAIRS){ push @$possible_branches, 1 }
    if ($c < $o){ push @$possible_branches, 0 }
    return $possible_branches;
}

sub print_string{
    my $string = shift;

    my $index = 0;
    my @acum;
    for (@$string){
	if ($_){
	    my $i = $index % $num_colors;
	    print $colors[$i] . '(';
	    $index++;
	    push @acum, $i;
	}else{
	    print $colors[pop(@acum)] . ')';
	}
    }
    print "\n";
}