Ted Idzikowski Ted Idzikowski - 24 days ago 9
Python Question

Checking for arithmetic sequencing inside matrix without using numpy

I'm just wondering how I can write a function that can determine if there's an arithmetic sequence of any length (this time four) in any direction in a matrix such that, if it's True, the function returns a list containing 4 coordinates (y,x) in the matrix of the occurrence of the list. Otherwise, it returns nothing. 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([[1, 10, 18, 29, 2],
[2, 7, 5, 6, 34],
[21, 4, 3, 5, 2],
[9, 1, 6, 10, 3],
[16, -9, 9, 17, 4],
[32, -6, 0, 26, 5]])

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


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.

Update: Here's a version that will terminate as soon as sequence of length of 4 is found:

SLOTS = [
    [0, -1],
    [-1, -1],
    [-1, 0],
    [-1, 1]
]

def as2(matrix):
    state = [[[[0, 0] for _ in range(4)] for _ in range(len(matrix[0]))] for _ in range(2)]

    def update(y, x, d_y, d_x, slot):
        if (y + d_y) >= 0 and 0 <= (x + d_x) < len(matrix[0]):
            prev_diff, prev_len = state[1+d_y][x+d_x][slot]
            diff = matrix[y+d_y][x+d_x] - matrix[y][x]
            length = prev_len + 1 if diff == prev_diff else 1
            state[1][x][slot] = [diff, length]

    for y in range(len(matrix)):
        for x in range(len(matrix[0])):
            for slot, (d_y, d_x) in enumerate(SLOTS):
                update(y, x, d_y, d_x, slot)
                if state[1][x][slot][1] == 3:
                    return [(y + d_y * i, x + d_x * i) for i in range(3, -1, -1)]

        state = state[::-1]
    return []

When applied to the same input as first version the output is following:

[(0, 1), (1, 1), (2, 1), (3, 1)]