Ted Idzikowski - 6 months ago 54

Python Question

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.