matrix maximum diagonal pattern match

Solution 1:

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.

Solution 2:

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