Ted Idzikowski Ted Idzikowski - 27 days ago 23
Python Question

Verifying arithmetic sequence in matrix without using numpy

I'm just wondering how I can write a function that can verify that there's an arithmetic sequence of length at least 4 either horizontally, vertically or diagonally in a matrix such that, if it's True, the function returns a sorted list containing 4 locations (y,x) in the matrix where one that sequence was found. Otherwise, it returns an empty list. See test below for clarification.

In mathematics, an arithmetic progression (AP) or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15 … is an arithmetic progression with common difference of 2.

P.S. For location, the components start with vertical position first and then horizontal with 0 as the initial position for both components just like in indexes.

This is how the function is tested. Below the function is called as1.

>>> as1([[0, 10, 1, 1, 0],
[1, 7, 2, 2, 1],
[4, 4, 3, 5, 2],
[9, 1, 4, 10, 3],
[16, -2, 5, 17, 4],
[25, -5, 6, 26, 5]])

[[0, 1],[1, 1], [2, 1], [3, 1]]

>>> as1([[2, 5, 2, 0, 0],
[5, 0, 4, 4, 4],
[2, 1, 3, 3, 3],
[1, 5, 0, 4, 2],
[4, 2, 1, 5, 5]])

[[0, 1], [1, 2], [2, 3], [3, 4]]

>>> as1([[2, 5, 2, 0, 0, 3],
[5, 0, 4, 4, 0, 0],
[2, 1, 3, 0, 3, 7],
[1, 5, 0, 4, 2, 8],
[4, 0, 1, 5, 5, 2]])

[[1, 4], [2, 3], [3, 2], [4, 1]]

>>> as1([[1, 2],
[3, 4]])

[]

>>> as1([[-48, -63, -80, -99, -120],
[-41, -56, -73, -92, -113],
[-22, -37, -54, -73, -94],
[15, 0, -17, -36, -57],
[76, 61, 44, 25, 4],
[167, 152, 135, 116, 95]])

[]

>>> as1([[-19, -8, 35, 35, -41, 19, 30, -43, 25],
[-12, -47, 14, -6, 31, 16, -40, 0, -38],
[40, 38, 26, -13, 47, -13, 40, 25, -26],
[37, -21, -40, 43, -7, -28, -33, -3, 50],
[10, -37, 37, -11, -40, -14, 5, 42, -43],
[49, -34, 27, 31, 25, -31, 36, -48, -5],
[23, -16, -47, 30, 46, 13, -30, 0, 23]])

[]


My attempt was only successful with lists, not matrices:

def as1(l):
list = []
delta = l[1] - l[0]
for index in range(len(l) - 1):
if (l[index + 1] - l[index] == delta):
list.append(index)

return list


I don't know how to identify an arithmetic sequence of length 4 occurrence for every and each value in a matrix. Also, I don't know how to make a function identify and append the 2D position of a location where the arithmetic sequence occurred.

How would a clever programmer approach such a problem?

Any hints would be welcome.

I'd recommend not using numpy, because I'm having issues installing it in my shell.

Answer

Here's a solution using dynamic programming. It goes through the matrix and for each element updates the length of incoming sequence for 4 possible directions. Once the matrix has been iterated over it finds the maximum sequence and backtracks to generate the result:

def as1(matrix):
    # Each element has 4 slots for incoming directions:
    # 0: x - 1
    # 1: y - 1, x - 1
    # 2: y - 1
    # 3: y - 1, x + 1
    # Each slot is a pair two numbers: difference to parent and sequence length
    cache = [[[[0, 0] for _ in range(4)] for _ in row] for row in matrix]

    def update(y_0, x_0, y_1, x_1, slot):
        if y_1 < len(matrix) and x_1 < len(matrix[y_1]):
            diff = matrix[y_0][x_0] - matrix[y_1][x_1]
            prev_diff, prev_len = cache[y_0][x_0][slot]
            if prev_diff == diff:
                length = prev_len + 1
            else:
                length = 1
            cache[y_1][x_1][slot] = [diff, length]

    # Populate working memory
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            update(i, j, i, j + 1, 0)
            update(i, j, i + 1, j + 1, 1)
            update(i, j, i + 1, j, 2)
            update(i, j, i + 1, j - 1, 3)

    # Find coordinate & slot for maximum sequence
    y, x, slot = max(((i, j, s)
                      for i in range(len(matrix))
                      for j in range(len(matrix[i]))
                      for s in range(4)
                     ),
                     key=lambda x: cache[x[0]][x[1]][x[2]][1])

    # Backtrack to generate the result
    length = cache[y][x][slot][1]
    result = []
    if length >= 3:
        for _ in range(4):
            result.append((y, x))
            if slot == 0:
                x -= 1
            elif slot == 1:
                x -= 1
                y -= 1
            elif slot == 2:
                y -= 1
            else:
                y -= 1
                x += 1

    return list(reversed(result))

res = as1([[0,  10, 1,  1, 0],
        [1,   7, 2,  2, 1],
        [4,   4, 3,  5, 2],
        [9,   1, 4, 10, 3],
        [16, -2, 5, 17, 4],
        [25, -5, 6, 26, 5]])

print(res)

Output:

[(2, 1), (3, 1), (4, 1), (5, 1)]

It has linear running time and will always return the 4 last items of longest sequence. If you only need first sequence of length 4 algorithm could be improved to terminate as soon as such sequence is found.