RogerBW's Blog

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

Task 1: Arrange Binary

You are given a list of binary digits (0 and 1) and a positive integer, $n.

Write a script to return true if you can re-arrange the list by replacing at least $n digits with 1 in the given list so that no two consecutive digits are 1 otherwise return false.

The simplest approach seemed to be to try it and see: look through the list, and if I can validly insert a 1, do so. Kotlin:

fun arrangebinary(a: List<Int>, n: Int): Boolean {

Copy the list and initialise the counter.

    var b = ArrayList(a)
    var t = n

Look through the list. for (i in 0 .. b.size - 1) {

If this place's value is a zero, and

        if (b[i] == 0 &&

We're at the start, or the previous place's value was a zero, and

            (i == 0 || b[i - 1] == 0) &&

We're at the end, or the next place's value is a zero

            (i == b.size - 1 || b[i + 1] == 0)) {

Then insert a 1 and decrement the counter.

            b[i] = 1
            t -= 1
        }
    }

Reteurn true of we reached zero.

    return t <= 0
}

Task 2: Maximum Average

You are given an array of integers, @ints and an integer, $n which is less than or equal to total elements in the given array.

Write a script to find the contiguous subarray whose length is the given integer, $n, and has the maximum average. It should return the average.

Mostly this is a job for sliding windows, and most languages have that available (thouh the Perl one in List::MoreUtils can be a bit rough).

use List::Util qw(sum max);
use List::MoreUtils qw(slideatatime);

sub maximumaverage($a, $n) {
  my $mx = 0;
  my $dd = slideatatime 1, $n, @{$a};
  while (my @s = $dd->()) {
    if (scalar @s == $n) {
      $mx = max($mx, sum(@s));
    }
  }
  $mx / $n;
}

But JavaScript, for example, doesn't have a built-in sliding window, so instead I take a running sum.

function maximumaverage(a, n) {
    let t = 0;
    for (let i = 0; i < n; i += 1) {
        t += a[i];
    }

Then add the new value and subtract the old one, keeping the maximum.

    let mx = t;
    for (let i = n; i < a.length; i += 1) {
        t += a[i];
        t -= a[i - n];
        mx = Math.max(mx, t);
    }
    return mx / n
}

In both cases, the icky floating point bit happens right at the end.

Full code on github.