Ted Idzikowski - 4 months ago 26

Python Question

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)]
```