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.