RogerBW's Blog

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

Task 1: Reorder Notes

You are given an array [composer, notes, permutation], reconstruct the melody by using each permutation value as the destination position of the corresponding note. Use no explicit for, foreach, or while loops. Output each result as COMPOSER => reordered notes.

ASSUMPTION: Input is valid; the notes array and permutation array have identical lengths, and the permutation contains each position from 1 to N exactly once.

This was pretty much the same in each language I used. Kotlin:

fun reordernotes(composer: String, notes: List<String>, order: List<Int>): HashMap<String, List<String>> {

Create an empty output array.

    var out = ArrayList((1 .. order.size).map{""})

Fill it piecewise.

    order.forEachIndexed { i, n ->
                               out[n - 1] = notes[i];
    }

Return the hashmap.

    return hashMapOf(composer to out)
}

There seems to be a bug or syntax oddity in Crystal such that its built-in tests can't compare with a literal hash. Hey ho.

Task 2: ZigZag Subarray

You are given an array of integers.

Write a script to find the length of the longest contiguous subarray where the numbers alternate between strictly increasing and strictly decreasing (a ZigZag pattern).

A sequence of numbers $A = [a0, a1, …, ak]$ with length $k >= 1 is considered a ZigZag sequence if every adjacent pair alternates direction:

a_0 < a_1 > a_2 < a_3 > ...

OR

a_0 > a_1 < a_2 > a_3 < ...

NOTE: A single element (length 1) or any two distinct elements (length 2) are automatically valid ZigZag sequences. Equal adjacent numbers (e.g., 5, 5) break the pattern.

This ended up being involved, but not complicated. In Perl:

sub zigzagsubarray($a) {

Set an initial maximum value of 1 if the array is not empty.

  my $mx = min(1, scalar @{$a});

Iterate from each possible starting point.

  foreach my $i (0 .. $#{$a}) {

Set up last value and direction.

    my $o = 0;
    my $lastdir = 0;

Iterate from that starting point as far as possible.

    foreach my $j ($i .. $#{$a}) {

Work out this direction. (And if we have two unequal values, make sure mx is at least 2.)

      my $thisdir = 0;
      if ($j > $i) {
        if ($a->[$j] > $o) {
          $thisdir = 1;
          $mx = max($mx, 2);
        } elsif ($a->[$j] < $o) {
          $thisdir = -1;
          $mx = max($mx, 2);
        }
      }

If this wasn't the first entry, and the latest two values were equal; or if this was later than the second entry, and the two directions weren't either (-1, 1) or (1, -1); this value at j invalidates the sequence, so stop looking.

      if (($j > $i && $thisdir == 0) || ($j > $i + 1 && $thisdir * $lastdir != -1)) {
        last;
      }

Otherwise, set the previous value and direction, and log the current sequence length.

      $o = $a->[$j];
      $lastdir = $thisdir;
      $mx = max($mx, $j - $i + 1);
    }
  }

Return the largest length seen.

  $mx;
}

Of course Scala doesn't let you break out of a loop which makes everything more fiddly.

Full code in all tagged languages is on codeberg.