Implement a Python function called ap4 that takes a 2D list m of numbers as inpu

Question

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

[]

Explanation / Answer

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)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.