A string, a character and a matrix...

walked into a bar and was the ingredients for this weeks task.

Weekly Challenge 248

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Shortest Distance

Task

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[sic] of the given character in the given string.

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

My solution

I start by getting all the positions of the character in the string, and raising an error if the character does not exist.

positions = [i for i, s in enumerate(word) if s == char]
if len(positions) == 0:
    raise ValueError(f"'{char}' does not appear in string")

The next step is to set the current_pos value to the first occurrence of the character, and the next_pos value to the next value from the positions array. If there is only one occurrence of the character next_pos is the same as current_pos.

current_pos = positions.pop(0)
next_pos = positions.pop(0) if len(positions) > 0 else current_pos

I then create a loop from 0 to one less than the length of the string. At this point, we don't actually care about what the string contains.

For each iteration, I see if we are closer to the next_pos than the current_pos. If this is the case, I set current_pos to next_pos and get the next value in the positions list. I add the difference between the iterator and current_pos to the solutions array.

solution = []
for i in range(len(word)):
    if abs(i - next_pos) < abs(i-current_pos):
        current_pos = next_pos
        next_pos = positions.pop(0) if len(positions) > 0 else current_pos

    solution.append(abs(i-current_pos))

And finally, print the solutions list in the format in the example.

print('(' + ','.join(map(str, solution)) + ')')

Examples

$ ./ch-1.py loveleetcode e
(3,2,1,0,1,0,0,1,2,2,1,0)

$ ./ch-1.py aaab b
(3,2,1,0)

Task 2: Submatrix Sum

Task

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].

My solution

For this, I take the input as a JSON-formatted string, which will be a list of list of integers. The first thing I do is check that each row has the same number of columns.

rows = len(matrix)
cols = len(matrix[0])

for r in range(1, rows):
    if len(matrix[r]) != cols:
       raise ValueError(f'Row {r} has different number of columns')

Then it is simply a matter of going through the matrix, calculating the new values to print.

print('[')
for r in range(rows-1):
    row = []
    for c in range(cols-1):
        row.append(matrix[r][c] + matrix[r][c+1] +
                   matrix[r+1][c] + matrix[r+1][c+1])
    print('  ' + str(row) + ',')

print(']')

Examples

$ ./ch-2.py "[ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ]"
[
  [14, 18, 22],
  [30, 34, 38],
]

$ ./ch-2.py "[ [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1] ]"
[
  [2, 1, 0],
  [1, 2, 1],
  [0, 1, 2],
]