20 December 2023

Challenge 248

Distances And Sums

• Task 1: Shortest Distance
• Task 2: Submatrix Sum

Task 1: Shortest Distance

Submitted by: Mohammad S Anwar

---

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 occurrence of
the given character in the given string.

The distance between two indices i and j is abs(i - j).

Example 1

Input: $str = "loveleetcode", $char = "e"
Output: (3,2,1,0,1,0,0,1,2,2,1,0)

The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5,
but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

Example 2

Input: $str = "aaab", $char = "b"
Output: (3,2,1,0)

---

Solution

First we create two PDL::Char ndarrays:

• $c holds the single character
• $s holds the string

Then we find all positions $p in $s where $c occurs. The difference between a 1xN ndarray holding $s’s indices and the positions ndarray $p produces a 2-d ndarray of the distances at each position to all of $c’s occurrences. Taking the minimum over the absolute values for every index produces the requested minimum distances.

use PDL;
use PDL::Char;

sub shortest_distance {
    my $c = PDL::Char->new(shift);
    my $s = PDL::Char->new(shift);
    my $p = which($s == $c)->long;
    return if $p->isempty;

	minover abs sequence(1, $s->dim(0)) - $p;
}

See the full solution.

Task 2: Submatrix Sum

Submitted by: Jörg Sommrey

---

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]

Example 1

Input: $a = [
              [1,  2,  3,  4],
              [5,  6,  7,  8],
              [9, 10, 11, 12]
            ]

Output: $b = [
               [14, 18, 22],
               [30, 34, 38]
             ]

Example 2

Input: $a = [
              [1, 0, 0, 0],
              [0, 1, 0, 0],
              [0, 0, 1, 0],
              [0, 0, 0, 1]
            ]

Output: $b = [
               [2, 1, 0],
               [1, 2, 1],
               [0, 1, 2]
             ]

---

Solution

Another PDL solution.

We create a NxM matrix $m as 2-d ndarray. For all elements of $m except the last row and column, we create 2x2 submatrices, bring the 2x2 dimensions to the front, clump them into a single dimension of size 4 and take the sums over these.

use PDL;
use PDL::NiceSlice;

sub submatrix_sum {
	my $m = pdl @_;

    $m->range(ndcoords($m(1:,1:)), 2)->reorder(2, 3, 0, 1)
        ->clump(2)->sumover;
}

See the full solution.

---

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.