[Israel.pm] What does this code do?

Shlomi Fish shlomif at iglu.org.il
Wed Apr 28 13:25:12 PDT 2004

On Wednesday 28 April 2004 14:28, David Baird wrote:
> I waited a week. 

A one day week - how interesting.

> Here is my answer: 
> The program tests that for arrays of N elements, that all members are 0,
> 1, and 2, and that all three are present in the array. 

Right. A bit more clearly: for all cominations of N ordered items out of a set 
of three, (possibly "0", "1" and "2"), how many combinations there are for 
which all three items are present?

> My alternative 
> code uses a hash instead of another array to test that all values exist.
> I also placed the test for the correct number of elements at the top of
> the subroutine, which I think makes for more clean code. I also go rid
> of the extra assignment and some fluff code like scalar(). My code runs
> no faster or slower the the original code. I am still thinking of how to
> avoid the recursion. 

Well, you cannot really avoid a recursion in this case. Recursion is an 
algorithmic technique which is not necessary such that uses procedures 
calling to themselves. What you can do is implement the recursion without a 
procedural recursion, all in one function. For some recursions it can be done 
by incrementing and decrementing a pointer or index that points to an element 
of a stack.

> I may try an iterating subroutine. Give me some 
> time, if no one beats me to it.
> #!/usr/bin/perl -w
> use strict;
> my $N = shift;
> my $num_true_cases = 0;
> helper();
> print $num_true_cases, "\n";
> sub helper
> {
>     if (@_ != $N) {
>         helper(@_, $_) for (0..2);
>         return;
>     }
>     my %bits;
>     $bits{$_} = 1 for @_;

This line (and the equivalent one from the original) can be written as:

@bits{@_} = @_;

Or perhaps:

@bits{@_} = ((1) x @_);

It did not occur to me to use a hash slice at the time.


	Shlomi Fish

Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Quidquid latine dictum sit, altum viditur.
        [Whatever is said in Latin sounds profound.]

More information about the Perl mailing list