I’m not even going to try to come up with something clever to tie this to music; just thinking about the first task makes my brain swim. So I’m tackling the second task first.
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]
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]
]
Approach
The approach here is fairly straightforward: accept the input matrix, determine the size M and N, then run through the calculations to determine the elements for the sums of the 2×2 submatricies. Jorg Sommrey was even kind enough to give us the formula.
Raku
sub submatrixSum(@a) {
# subtract 1 because we're 0-indexed
my $M = @a.elems - 1; # rows
my $N = @a[0].elems - 1; # columns
# we are ASSUMING the matrix is consistent with
# each row having the same number of columns
my @b;
for 0 .. $M - 1 -> $i {
for 0 .. $N - 1 -> $k {
@b[$i;$k] = @a[$i; $k] + @a[$i; $k+1]
+ @a[$i+1;$k] + @a[$i+1;$k+1];
}
}
return @b;
}
View the entire Raku script for this task on GitHub.
Perl
sub submatrixSum(@a) {
my $M = $#a; # rows
my $N = $#{$a[0]}; # columns
# we are ASSUMING the matrix is consistent with
# each row having the same number of columns
my @b;
foreach my $i ( 0 .. $M - 1 ) {
push @b, [];
foreach my $k ( 0 .. $N - 1 ) {
$b[$i]->[$k] = $a[$i]->[$k] + $a[$i]->[$k+1]
+ $a[$i+1]->[$k] + $a[$i+1]->[$k+1];
}
}
return @b;
}
View the entire Perl script for this task on GitHub.
Python
def submatrixSum(a):
# subtract 1 because we're 0-indexed
M = len(a) - 1 # rows
N = len(a[0]) - 1 # columns
# we are ASSUMING the matrix is consistent with
# each row having the same number of columns
b = []
for i in range(M): # range is 0 .. M-1
row = []
for k in range(N):
row.append( a[i ][k] + a[i ][k+1] +
a[i+1][k] + a[i+1][k+1] )
b.append(row)
return b
View the entire Python script for this task on GitHub.
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 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)
Approach
The approach we should take is pretty much outlined in the description of the example: first generate a list of what indices the target character occurs at, then calculate the closest occurrence based on abs(x - y) where x and y are the positions of the current character and an occurrence of the target character.
Raku
sub shortestDistance($str, $char) {
# split the string into an array of characters
my @strchar = $str.split('', :skip-empty);
# find the positions of the target $char
my @pos = (0 .. @strchar.end).grep: { @strchar[$_] eq $char };
my @output;
for 0 .. @strchar.end -> $i {
# find the distances
my @distance = @pos.map: { abs($i - $_) };
# find the minimum distance
@output.push( @distance.min );
}
return @output;
}
View the entire Raku script for this task on GitHub.
Perl
sub shortestDistance($str, $char) {
# split the string into an array of characters
my @strchar = split(//, $str);
# find the positions of the target $char
my @pos = grep { $strchar[$_] eq $char } 0 .. $#strchar;
my @output;
foreach my $i ( 0 .. $#strchar ) {
# find the distances
my @distance = map { abs($i - $_) } @pos;
# find the minimum distance
push @output, min(@distance);
}
return @output;
}
View the entire Perl script for this task on GitHub.
Python
def shortestDistance(s, c):
# split the string into an array of characters
strchar = list(s)
# find the positions of the target char
pos = [ x for x in range(len(s)) if strchar[x] == c ]
output = []
for i in range(len(s)):
# find the distances
distance = [ abs(i - p) for p in pos ]
# find the minimum distance
output.append( min(distance) )
return output
View the entire Python script for this task on GitHub.
Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-248/packy-anderson
