python - Checking for arithmetic sequencing inside matrix without using numpy -

i'm wondering how can write function can determine if there's arithmetic sequence of length (this time four) in direction in matrix such that, if it's true, function returns list containing 4 coordinates (y,x) in matrix of occurrence of list. otherwise, returns nothing. see test below clarification.

in mathematics, arithmetic progression (ap) or arithmetic sequence sequence of numbers such difference between consecutive terms constant. instance, sequence 5, 7, 9, 11, 13, 15 … arithmetic progression common difference of 2.

p.s. location, components start vertical position first , horizontal 0 initial position both components in indexes.

this how function tested. below function 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 successful lists, not matrices:

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

i don't know how identify arithmetic sequence of length 4 occurrence every , each value in matrix. also, don't know how make function identify , append 2d position of location arithmetic sequence occurred.

how clever programmer approach such problem?

any hints welcome.

i'd recommend not using numpy, because i'm having issues installing in shell.

here's solution using dynamic programming. goes through matrix , each element updates length of incoming sequence 4 possible directions. once matrix has been iterated on finds maximum sequence , backtracks generate result:

def as1(matrix):     # each element has 4 slots incoming directions:     # 0: x - 1     # 1: y - 1, x - 1     # 2: y - 1     # 3: y - 1, x + 1     # each slot pair 2 numbers: difference parent , sequence length     cache = [[[[0, 0] _ in range(4)] _ in row] row in matrix]      def update(y_0, x_0, y_1, x_1, slot):         if y_1 < len(matrix) , 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     in range(len(matrix)):         j in range(len(matrix[i])):             update(i, j, i, j + 1, 0)             update(i, j, + 1, j + 1, 1)             update(i, j, + 1, j, 2)             update(i, j, + 1, j - 1, 3)      # find coordinate & slot maximum sequence     y, x, slot = max(((i, j, s)                       in range(len(matrix))                       j in range(len(matrix[i]))                       s in range(4)                      ),                      key=lambda x: cache[x[0]][x[1]][x[2]][1])      # backtrack generate result     length = cache[y][x][slot][1]     result = []     if length >= 3:         _ 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 , return 4 last items of longest sequence. if need first sequence of length 4 algorithm improved terminate such sequence found.

update: here's version terminate sequence of length of 4 found:

slots = [     [0, -1],     [-1, -1],     [-1, 0],     [-1, 1] ]  def as2(matrix):     state = [[[[0, 0] _ in range(4)] _ in range(len(matrix[0]))] _ in range(2)]      def update(y, x, d_y, d_x, slot):         if (y + d_y) >= 0 , 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]      y in range(len(matrix)):         x in range(len(matrix[0])):             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) in range(3, -1, -1)]          state = state[::-1]     return [] 

when applied same input first version output following:

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