RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved array sums and differences. (Note that this ends today.)

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.

This can be rearranged into "take the sum of each row, then return the highest", and it's pretty much a one-liner (except in Lua). Typst:

#let highestrow(a) = {
  calc.max(..a.map(x => x.sum()))
}

The other languages all look very similar.

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.

Of course I could do all the cross-subtractions and return the largest absolute value.

Or I could take the lowest and highest values of each input array, because the largest difference will be between either (highest 1 - lowest 2) or (lowest 2 - highest 1).

Perl:

sub maxdistance($a, $b) {
  my ($l1, $h1) = minmax(@{$a});
  my ($l2, $h2) = minmax(@{$b});
  return max($h1 - $l2, $h2 - $l1);
}

(I use minmax from List::MoreUtils, which reduces the number of comparisons needed to find both minimum and maximum by splitting each pair of values, one to a minimum bucket and the other to a maximum bucket; then it does a straightforward min and max on each of those buckets.)

Again, the others look similar, but I'm quite happy with the PostScript:

/maxdistance {

Replace each list with its minimum and maximum values (as above). This is the only operation that isn't a standard language primitive, and of course it's in my PostScript utility library.

    minmax exch
    minmax

Break out the arrays into individual values on the stack.

    aload pop
    3 -1 roll
    aload pop

At this point the stack is l1 h1 l2 h2, or perhaps the other way round; the order of the inputs doesn't matter.

Now twiddle the stack entries so that I get h1 and l2 (or vice versa) next to each other.

    4 1 roll

Now we have h2 l1 h1 l2… and subtract.

    sub

Tuck that away, and subtract the other pair of values.

    3 1 roll
    sub

Return the higher.

    max
} bind def

Full code on github.