Re: Perl Quiz of the Week #23

"Zsban Ambrus" <[email protected]> Mon, 6 Sep 2004 17:51:32 +0200

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

On Wed, Sep 01, 2004 at 12:50:14PM -0400, Mark Jason Dominus wrote:
> Write a program, 'parens', which gets a command line argument, n',
> which is an integer.  The program should print all the
> properly-balanced strings of parentheses of length 2n.  

I send another solution in addition to my first one.

ambrus

ants (text/plain, 1.1 KB)

#!ruby -w
=begin

parens - prints all possible strings of balanced parenthesis

This my other solution for regular perl qotw #23, see
"http://perl.plover.com/qotw/r/023".

This is by no means an original solution, I have seen some similar ones
on the discussion list.  This solution is supposed to be faster than
my first one because it does not copy and concatenate strings, it only
modifies the characters in one single string. 

It would be possible to make this even more efficent by eliminating the
recursion, but I've found that too confusing.

[email protected]

=end

def main;
	1==$*.size or fail "Usage: parens an_integer";
	level = $*[0].to_i;
	level<0 and fail "I need a non-negative integer";
	parens level;
end;

def parens(num);
	str = "/" * (2 * num) + "\n";
	rec(str, num, 0, 0);
end;

def rec(str, num, pos, ht);
	if 2 * num <= pos;
		print str;
	else
		if ht < 2 * num - pos;
			str[pos] = ?(;
			rec(str, num, pos + 1, ht + 1);
		end;
		if ht > 0;
			str[pos] = ?);
			rec(str, num, pos + 1, ht - 1);
		end;
	end;
end;

main;

__END__