RogerBW's Blog

The Weekly Challenge 248: Shortest Submatrix 24 December 2023

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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1