RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved searching a string and adding matrix elements. (Note that this ends today.)

Task 1: Shortest Distance

You are given a string and a character in the given string.

Write a script to return an array of integers of size same as length of the given string such that: distance[i] is the distance from index i to the closest occurence of the given character in the given string. The distance between two indices i and j is abs(i - j).

So each instance of the target character maps to zero, its neighbours to 1, etc. There were several possible approaches to this, but I ended up building a list of the target character indices and then doing a BFS to find their neighbours.

Rust, which is my usual language for the first solution of these problems, has a handy match_indices which lets me find all the matches at once. Most of the others have a "start your match at a particular point" function. For PostScript, I tried building a working string copy and cropping it down, but it felt cleaner to take a functional approach: take the input string as an array, enumerate it so that I have index values, filter for matching characters, then map the list into the queue format.

In Scala, I'm on Scala 2.11 (Debian/stable), which only has a Queue type rather than a general-purpose double-ended queue. Still, it works.

sub shortestdistance($a, $c) {
    my @q;
    my $i = 0;

Find all instances of the target character and queue them with a zero value.

    while (True) {
        with ($a.index($c, $i)) {
            @q.push(($_, 0));
            $i = $_ + 1;
        } else {
            last;
        }
    }

In most languages that was a loop as in this Perl, where I start the next string search one character after the previous one. (Raku returns a fail state of Nil if the character isn't found, rather than -1, but documentation on how to catch that cleanly is sparse.)

  while ($i >= 0) {
    my $p = index($a, $c, $i);
    if ($p > -1) {
      push @q, [$p, 0];
      $i = $p + 1;
    } else {
      $i = -1;
    }
  }

In Rust it was:

    for (i, _c) in a.match_indices(c) {
        q.push_back((i, 0));
    }

while in PostScript (which only has "does this substring appear at the start of the string" and "does this substring appear at all" functions) I went functional:

We're going to define a variable:

/q

Build a list of characters and indices:

a enumerate.array

Choose only those where the character matches the target:

{ 1 get c eq } filter

Use the index to build the queue entry:

{ 0 get [ exch 0 ] } map

and put that list into the variable:

def

Back to Raku. Fill the output list with an invalid valuue.

    my $invalid = $a.chars + 1;
    my @out = $invalid xx $a.chars();

Now do the BFS. If I find an entry that hasn't been initialised already…

    while (@q.elems > 0) {
        my ($i, $v) = @q.shift;
        if (@out[$i] == $invalid) {

Fill it with the calculated value (and because this is BFS the lowest value will be the first time I've seen this cell).

            @out[$i] = $v;

Now queue neighbouring cells with a value one higher than this. One of these will always be a cell we've already seen, and sometimes both.

            if ($i > 0) {
                @q.push(($i - 1, $v + 1));
            }
            if ($i < $a.chars - 1) {
                @q.push(($i + 1, $v + 1));
            }
        }
    }
    return @out;
}

Another approach, which I didn't think of until writing this up: for each matching character, build a list [..., -2, -1, 0, 1, 2, ...] centred on that position. Then align them all and take the minimum value. But I was in a BFS sort of mood, so this is the one you get.

Task 2: Submatrix Sum

You are given a NxM matrix A of integers.

Write a script to construct a (N-1)x(M-1) matrix B having elements that are the sum over the 2x2 submatrices of A, b[i,k] = a[i,k] + a[i,k+1] + a[i+1,k] + a[i+1,k+1]

This is basically just nested loops, and looks the same in most languages. JavaScript:

function submatrixsum(a) {
    let out = [];
    for (let y = 0; y < a.length - 1; y++) {
        let row = [];
        for (let x = 0; x < a[y].length - 1; x++) {
            let s = 0;
            for (let ya = y; ya <= y + 1; ya++) {
                for (let xa = x; xa <= x + 1; xa++) {
                    s += a[ya][xa];
                }
            }
            row.push(s);
        }
        out.push(row);
    }
    return out;
}

Full code on github.