DEV Community

Bob Lied
Bob Lied

Posted on

PWC 338 Maximal maximization of maximums

#perl #perlweeklychallenge #pwc

As I'm writing this, I'm watching a crew install a fence and once again thanking my high school guidance counselor, Mr. Bencini, for yelling at me to get my ass in gear and quit procrastinating on those college applications if you don't want to spend your life digging post holes and living in a van down by the river.

This week's challenges must have come from Cybertruck drivers in Texas, because they are overcompensating for something with an obsession about being the biggest.

Our musical accompaniment: Take it to the Limit by the Eagles, 1975 (coincidentally about the time that Mr. Bencini was yelling at me).

Task 1: Highest Row 

You are given a m x n matrix. Write a script to 
find the highest row sum in the given matrix.
Example: Input: @matrix = ([4,  4, 4, 4],
                           [10, 0, 0, 0],
                           [2,  2, 2, 9])
Output: 16
    Row 1: 4  + 4 + 4 + 4 => 16
    Row 2: 10 + 0 + 0 + 0 => 10
    Row 3: 2  + 2 + 2 + 9 => 15
Enter fullscreen mode Exit fullscreen mode

If every row can be reduced to its sum, then it's a one-liner. We'll lean on list utilities.

use List::Util qw/sum0 max/;
sub highestRow(@matrix)
{
    return max map { sum0 $_->@* } @matrix
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • map {...} @matrix -- Each element in @matrix is a reference to an array. Do something to every row.
  • sum0 $_->@* -- De-reference a row ($_) to get its list of numbers. Use sum0 instead of sum to handle the possibility of an empty matrix.

Task 2: Max Distance 

# You are given two integer arrays, @arr1 and @arr2.  Write a script to
# find the maximum difference between any pair of values from both arrays.
# Example 1 Input: @arr1 = (4, 5, 7)
#                  @arr2 = (9, 1, 3, 4)
#           Output: 6
#   With element $arr1[0] = 4   | 4 - 9 | = 5
#                               | 4 - 1 | = 3
#                               | 4 - 3 | = 1
#                               | 4 - 4 | = 0
#           max distance = 5
#   With element $arr1[1] = 5   | 5 - 9 | = 4
#                               | 5 - 1 | = 4
#                               | 5 - 3 | = 2
#                               | 5 - 4 | = 1
#           max distance = 4
#   With element $arr1[2] = 7   | 7 - 9 | = 2
#                               | 7 - 1 | = 6
#                               | 7 - 3 | = 4
#                               | 7 - 4 | = 4
#           max distance = 6
#   max (5, 4, 6) = 6
Enter fullscreen mode Exit fullscreen mode

This example is trying to scare us by implying that we have to do some atrocious examination of every possible pair, an O(n2) algorithm. But let's cut through the fog: if we reduce each array to a range from its minimum to its maximum, it can be visualized like sliding @arr2 past @arr1, with five different possibilities for how they overlap.

                min1                   max1
                +-------------------------+
 +--------+  +--------+  +--------+  +--------+  +--------+
 min2  max2  min2  max2  min2  max2  min2  max2  min2  max2
Enter fullscreen mode Exit fullscreen mode

The maximum distance will be from the extreme of one line to the extreme of the other. At the left side of the figure, that's the distance from min2 to max1; at the right side, it's from min1 to max2.

sub maxDist($arr1, $arr2)
{
    use List::MoreUtils qw/minmax/;
    use List::Util qw/max/;

    my ($min1, $max1) = minmax($arr1->@*);
    my ($min2, $max2) = minmax($arr2->@*);

    return max( $max1-$min2, $max2-$min1 );
}
Enter fullscreen mode Exit fullscreen mode

Notes:

  • List::MoreUtils::minmax -- this convenient function finds the minimum and maximum in an array with only one pass, exploiting Perl's ability to return more than one thing at a time.

Well, that was almost too easy. Let's apply Parkinson's Law ("Work expands to fill the time available"). We should do some error checking for the case that one of the arrays is empty. Because I can't think of a sensible result for that case, I'll throw an exception.

    die "ERROR empty array" if ( not ( @$arr1 and @$arr2) );
Enter fullscreen mode Exit fullscreen mode
  • @$arr1 and @arr2 -- the value of an array in a scalar context is its size; compact and useful, and easy to trip up beginners.
  • I'm using not and and for readability, rather than ! and &&. It's a simple conditional expression, so there's no problem with the low precedence of not and and.

That's nice, but now we have a function that could possibly throw an exception. We should check for that. Classic Perl had the eval syntax, but there have been variations on a try/catch feature for decades. Perl finally acquired a native try/catch syntax as an experimental feature in release 5.34, and it became a stable language feature in 5.40, so let's embrace the future.

For command-line usage, I'm going to pass the script a pair of comma-separated lists.

perl ch-2.pl  1,2,3,4  3,6,9
Enter fullscreen mode Exit fullscreen mode

The Perl code to handle the arguments and call maxDist will look like:

my @ARR1 = split(",", shift // "");
my @ARR2 = split(",", shift // "");
try          { say maxDist(\@ARR1, \@ARR2); }
catch ( $e ) { say STDERR "Problem: $e" }
Enter fullscreen mode Exit fullscreen mode

Notes:

  • shift -- the implicit argument for shift is @ARGV, so this takes the next available command-line argument.
  • shift // "" -- If there isn't an argument, avoid a warning message by defaulting to an empty string.
  • say STDERR "..." -- Not trying very hard to inform or recover, but at least use conventional streams.

The final piece is to add a unit test for catching an exception. Using the Test2::V0 testing module, check for throwing an appropriate exception like this:

    like( dies { maxDist([], []) }, qr/empty/i, "Empty arrays");
Enter fullscreen mode Exit fullscreen mode
  • like(...) -- test that the result of some code matches a regular expression
  • dies {...} -- evaluate some code that is expected to throw an exception (note braces instead of parentheses).

Top comments (0)