PWC 262 Grep it once, grep it twice
Tags: perl, perlweeklychallenge, pwc
Published: 2024-03-30 14:20:06

## [Perl Weekly Challenge 262, Max Positive Negative](https://theweeklychallenge.org/blog/perl-weekly-challenge-262/#TASK1)
```text
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](https://www.youtube.com/watch?v=EPmTGFg06zA), `grep` you once, `grep` you twice, don't count zeroes at any price.
```perl
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.
```perl
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.
```perl
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. 
```perl
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](https://www.youtube.com/watch?v=jGsOmKZXDvo). 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.
```perl
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.

```perl
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
```perl
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.

```perl
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:
```perl
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();
}
```
----
The agile ghosts have had enough of me. I hear them talking about pizza and edibles. I declare this horse officially beaten. Full code is on [GitHub](https://github.com/boblied/perlweeklychallenge-club/tree/w262/challenge-262/bob-lied/perl).