Implement a Python function called ap4 that takes a 2D list

Implement a Python function called ap4 that takes a 2D list m of numbers as input (parameter) representing a matrix and tests if m has at least four consecutive numbers that form an arithmetic progression either horizontally, vertically or diagonally (in either of the two diagonal directions \\ or /). If yes, the function returns a 2D list containing 4 locations in the matrix where one such sequence is found. This return 2D list has to be sorted by using python’s sorted function (so that your function can be automatically tested). If no sequence is found, the function returns empty 1D list. You may assume that m represents a matrix, meaning m will not have rows with different number of elements.

Examples of function calls:

>>> ap4([[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]]

>>> ap4([[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]]

>>> ap4([[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]]

>>> ap4([[1, 2],

   [3, 4]])

[]

>>> ap4([[-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]])

[]

>>> ap4([[-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]])

[]

Solution

program

   import sys
def arithmetic(arr):
n = len(arr)
if (n<=2):
return n
llap = 2
L = [[0]*n for i in xrange(n)]
for i in xrange(n):
L[i][n-1] = 2
for j in xrange(n-2,0,-1):
i = j-1
k = j+1
while (i >=0 and k <= n-1):
if (arr[i] + arr[k] < 2*arr[j]):
k = k + 1
elif (arr[i] + arr[k] > 2*arr[j]):
L[i][j] = 2
i -= 1
else:
L[i][j] = L[j][k] + 1   
llap = max(llap, L[i][j])
i = i - 1
k = j + 1
while (i >=0):
L[i][j] = 2
i -= 1
return llap
arr = [1,4,5,7,8,10]
print arithmetic(arr)