RogerBW's Blog

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

Task 1: Max Diff

You are given an array of integers having four or more elements.

Write a script to find two pairs of numbers from this list (four numbers total) so that the difference between their products is as large as possible.

In the end return the max difference.

With Two pairs (a, b) and (c, d), the product difference is (a * b) - (c * d).

The "cool" way to do this would be a partial permutation, but that's hard work, and nested loops work too. Perl:

use List::Util qw(max);

sub maxdiff($a) {
  my $md = 0;

Start the loops for a and b (indices w and x). Cut out half the possibilities by only considering w < x.

  foreach my $w (0 .. scalar @{$a} - 2) {
    foreach my $x ($w + 1 .. scalar @{$a} - 1) {

The loops for c and d are indices y and z. These are set such that w < y and y < z. (On reflection I'm not 100% sure this is exhaustive, but it passes all the test cases, and most languages don't have an efficient partial permutation routine.)

      foreach my $y ($w + 1 .. scalar @{$a} - 2) {
        if ($y != $x) {
          foreach my $z ($y + 1 .. scalar @{$a} - 1) {
            if ($z != $x) {

Generate the value and store the highest found so far.

              my $v = abs($a->[$w] * $a->[$x] - $a->[$y] * $a->[$z]);
              $md = max($md, $v);
            }
          }
        }
      }
    }
  }
  $md;
}

Task 2: Peak Point

You are given an array of altitude gain.

Write a script to find the peak point gained.

In other words, the highest value of sum (x0 to xN) for any N. I think a purely functional approach would create a list of these values then take the maximum at the end, but going one at a time saves the storage. JavaScript:

function peakpoint(a) {
    let h = 0;
    let o = 0;
    for (let p of a) {
        h += p;
        o = Math.max(o, h);
    }
    return o;
}

Full code on github.