matrix maximum diagonal pattern match-CodePudding

I came across a problem while doing technical interviews for matrix pattern matching. I was able to solve the problem using brute force but wonder if there is a more efficient solution as I only got about half credit for efficiency. Thank you in advanced for your input.

Given a matrix containing the numbers 0, 1, 2 and the pattern [1, 2, 0, 2, 0, 2, 0] find the max length of the matching pattern starting from any point in the matrix but can only travel diagonally.

here is an example of where we would expect the function to return 12.

here is where we would expect the function to return 7.

and empty matrix should return 0.

Here is my code, like I said previously it does work and passed all the tests but I got docked points.

def max_diagonal_match(matrix) -> int:
    max_len = 0
    pattern_match = [1, 2, 0, 2, 0, 2, 0]
    for i in range(0, len(matrix)):
        for j in range(0, len(matrix[i])):
            max_len = max(
                max_len,
                find_i_minus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_minus_j_plus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_minus(matrix, i, j, pattern_match, 7),
                find_i_plus_j_plus(matrix, i, j, pattern_match, 7)
            )
    return max_len


# i-, j-
def find_i_minus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i -= 1
        j -= 1
    return count


# i-, j 
def find_i_minus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i >= 0 and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i -= 1
        j  = 1
    return count


# i , j-
def find_i_plus_j_minus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j >= 0:
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i  = 1
        j -= 1
    return count


# j , i 
def find_i_plus_j_plus(matrix, i, j, pattern, mod):
    count = 0
    while i < len(matrix) and j < len(matrix[i]):
        if matrix[i][j] != pattern[count % mod]:
            return count
        count  = 1
        i  = 1
        j  = 1
    return count

Many thanks for taking the time to read and any input is much appreciated.

CodePudding user response：

Building on the accept answer to this question. It's based on a few key ideas:

You can use np.diagonal over a range to slice every possible diagonal out of the array. You can flip the array around to make sure you get all angles.

You can tile the pattern to make sure it's at least as long or longer than the largest diagonal.

You can zip the diagonal and the pattern and the extra values in the pattern will be dropped automatically due to the way zip works.

Then you can use takewhile on the zipped (diag,pattern) to check how many consecutive matches there are len(set(x))==1.

If you do this for all the possible combinations and take the max, you should have your answer.

import numpy as np
from math import ceil
from itertools import takewhile

def max_sequence(arr):
    solns = []
    i = arr.shape[0]
    for x in range(-i, i 1):
        values = arr.diagonal(x)
        N = len(values)
        possibles = np.where(values == pattern[0])[0]
        for p in possibles:
            check = values[p:p N]
            m = len(list(takewhile(lambda x:len(set(x))==1, zip(pattern,check))))
            solns.append(m)
    return max(solns)

def find_longest(arr):
    if len(arr)>0:
        return max([max_sequence(x) for x in [arr, np.fliplr(arr), np.flipud(arr), arr[::-1]]])
    else:
        return 0

arr = np.array([
    [1,0,2,1,1,1,1,0,0,0,0,0,0],
    [1,2,2,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,1,1,1,0,0,0,0,0,0],
    [1,0,0,2,0,1,1,0,0,0,0,0,0],
    [1,0,0,1,1,2,1,0,0,0,0,0,0],
    [1,0,0,1,1,1,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,2,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,2,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,0],
])

arr1 = np.array([
    [1,0,2,1,1,1,1],
    [1,2,2,1,1,1,1],
    [1,0,0,1,1,1,1],
    [1,0,0,2,1,1,1],
    [1,0,0,2,0,1,1],
    [1,0,0,1,1,2,1],
    [1,0,0,1,1,1,0]
])

arr2 = np.array([])

pattern = [1, 2, 0, 2, 0, 2, 0]
# Make sure pattern repeats longer than the max diagonal
pattern = np.tile(pattern,ceil(arr.shape[1] / len(pattern)))

for a in [arr, arr1, arr2]:
    print(find_longest(a))

Output

12
7
0

CodePudding user response：

We can break the problem down into finding the longest match possible along each diagonal of the matrix. The efficiency of the algorithm then boils down to how quickly can we find the longest match along any given diagonal.

For a diagonal of length N and a pattern of length M, your solution is O(N^2): you try each of N starting points along the diagonal and extend the match as far as you can (which is O(N) comparisons)

Faster solutions to this problem do exist. It is possible to match each diagonal with complexity:

O(NM) by using dynamic programming, which is faster if M << N
O(NlogN) by lexicographically sorting suffixes of the diagonal (or related techniques: suffix trees, Burrows-Wheeler transform, FM-index, etc)
technically, O(N) is possible with suffix arrays, but the algorithms are too complicated to implement for a coding interview (e.g. Ukkonen's algorithm)

There are also algorithms that, while O(N^2) in the worst case, are likely to be much faster than this in practice, e.g. seed-and-extend algorithms are fast when there are few long matches.

I'm sure that the techniques mentioned above are not an exhaustive list.