PWC 262 Grep it once, grep it twice

#perl #perlweeklychallenge #pwc

Perl Weekly Challenge 262, Max Positive Negative

You are given an array of integers, @ints.
Write a script to return the maximum number
of either positive or negative integers in
the given array.

Example

Input: @ints = (-3, 1, 2, -1, 3, -2, 4)
Output: 4

Count of positive integers: 4
Count of negative integers: 3
Maximum of count of positive and negative integers: 4

The simplest thing that works

As the song says, grep you once, grep you twice, don't count zeroes at any price.

sub maxPosNeg(@ints) 
{
    my $pos = grep { $_ > 0 } @ints;
    my $neg = grep { $_ < 0 } @ints; 
    return ( $pos > $neg ? $pos : $neg );
}

And yet ... two passes over the array. Ick. Seems so unnecessary. The iterators. Won't someone think of the iterators? If we can save the life of even one iterator, wouldn't it be worth it?

The simplest thing that feels efficient

The agile ghosts that live in the dark space behind my desk perk up. "Are you contemplating pre-mature optimization? Because it seems like you're making pre-mature optimization noises."

I glare at them. Of course we can do this in one pass. The efficiency is, uh, obvious by inspection. Yeah, no need to even benchmark. "Ugh. You do you," say the ghosts.

sub maxPosNeg(@ints)
{
    my ($pos, $neg) = (0, 0);
    foreach ( @ints )
    {
        if    ( $_ > 0 ) { $pos++ }
        elsif ( $_ < 0 ) { $neg++ }
    }
    return ( $pos > $neg ) ? $pos : $neg;
}

Somewhat less simple

The agile ghosts are getting agitated. "You're still going to mess with it, aren't you? What is wrong with you? Knock it off."

"Shut up," I explain.

Those two variables $pos and $neg are chafing me. What if we could put the counts into an array and take the maximum of an array? All the positive numbers map to one element of the array; all the negative numbers to another. For starters, let's have a function that maps numbers into one of three buckets: -1 for negatives, 0 for zeroes, and 1 for positives.

sub sign($n) { return ( $n < 0 ? -1 : ( $n > 0 ? 1 : 0 ) ) }

Now we have three distinct values that could be indexes into an array. Suppose we have an array of three elements; call it @range. The indices of the array are 0, 1, and 2. The indices are also -3, -2, and -1. So $range[1] (positives) is the middle element, and $range[-1] (negatives) is the last element.

sub maxPosNeg(@ints)
{
    use List::Util qw/max/;
    my @range = ( 0, 0, 0 );
    $range[ sign($_) ]++ foreach @ints;
    return max( @range[1,2] );
}

Is this clear? No. Is this more efficient? Probably also no.

Oh sure, I could have had sign($n) map into 0, 1 and 2, but then I wouldn't have the little frisson that comes from indexing the array from both ends at the same time.

Totally gratuitous generalization

I feel the power of obfuscation descend on me like a dark fog. I must have more.

What if I generalize?

The agile ghosts start chanting, "You aren't going to need it. YAGNI, YAGNI, YAGNI ..." But need has nothing to do with it now. I want it. I want it so bad. The agile ghosts shake their heads sadly and slink back behind the desk. "Perl is a helluva drug," I hear them mutter.

What if we had different conditions? What if we wanted to know the maximum of even or odd numbers? Or multiples of 3, 5, and 7? Or what if the numbers were US postal codes and we wanted to know the maximum among west coast states?

I should parameterize the buckets. And I should use objects.

So what do we need? We're categorizing things into buckets. Each bucket has a condition for inclusion, and a count. Then we need a collection of buckets, from which we can find the maximum.

Time to change the music and start humming Buckets of Rain. This could get weird.

Little red wagon, little red bike. I ain't no monkey but I know what I like

First step: a Bucket class. It has two attributes (fields). The condition is a reference to a subroutine, which takes a number as input and returns true or false.

The Bucket class needs two methods: one to evaluate whether a number should be in the bucket, and another to return the count of things in the bucket.

class Bucket {
    field $condition :param = sub($n) { true };
    field $_count = 0;

    method contains($n) { $_count++ if $condition->($n); }
    method count() { return $_count }
}

That's minimal. For convenience and readability ("Oh now you're thinking of readability?" I hear sarcastically from behind the desk), let's give the bucket a name. In the spirit of continuing to do too much, let's also have default names that are constructed from an incrementing ID.

class Bucket {
    my $id = 0;
    ADJUST { ++$id }

    field $name :param = "Bucket$id";
 . . .

Perl notes here:

notice that $id is my $id, not a field. It's a class variable that is common to all instances of Bucket.
The ADJUST code is executed every time the constructor is used. So, $id counts instances and should make $name unique to every new Bucket that needs a default name.
The :param tag means that the field could be provided via the constructor (we also used it for $condition above).
On the right side of the variables is an initializer to provide a default value.

That means that a call of the constructor would look like

my $plus = Bucket->new(name => "positive",
                       condition => sub($n) { $n > 0 } );

Next, we need a collection of Bucket objects. We will cleverly name it BucketCollection. (Audible eye roll from behind the desk.) It holds references to bucket objects, and it needs three methods:

add($bucket) to put new Buckets into the collection.
place($n) to categorize a number into its bucket
biggestNum() to retrieve the largest number.

class BucketCollection {
    field @coll;

    method add($bucket) { push @coll, $bucket; return $self; }

    method place($n) { $_->contains($n) for @coll; return $self }
    method biggestNum() { return List::Util::max map { $_->count } @coll }
}

Notes here:

I'm using an array as the implementation of the collection. I could have used a hash, with maybe the bucket names as keys, but suddenly I've rediscovered the urge to Do The Simplest Thing That Works.
Both add and place return a reference to the BucketCollection object. That means I can chain calls, a useful idiom.
biggestNum uses map to transform each bucket to its count number.

With these classes available, the solution is reasonably concise:

sub maxPosNeg(@ints)
{
    my $buckets = BucketCollection->new()
        ->add( Bucket->new(name => "positive", condition => sub($n) { $n > 0 } ) )
        ->add( Bucket->new(name => "negative", condition => sub($n) { $n < 0 } ) );

    $buckets->place($_) foreach @ints;
    return $buckets->biggestNum();
}