Finding the max product of a 2D array

Question

Given a 2D array of unsigned integers and a maximum length n, find a path in that matrix that is not longer than n and which maximizes the product of the elements in the path. The output should consist of both the path and the product.

A path consists of neighbouring integers that are either all in the same row, or in the same column, or down a diagonal in the down-right direction. The code for this problem is below:

def maxPathProduct(self, matrix, maxLen):
 """
 Take a 2D Array of ints
 and return the largest Product of list of ints of length maxLen
 and the product of the list integers
 """ 
 maxProduct = -1
 maxList = [] 
 if len(matrix) == 0:
 return maxProduct, maxList
 numRows = len(matrix)
 numCols = len(matrix[0])
 for direction in range(1, 4):
 if direction == 1:
 numLines = numCols
 elif direction == 2:
 numLines = numRows
 elif direction == 3:
 numLines = numRows + numCols -1
 for line in range (0,numLines):
 pathProduct = 1
 pathLen = 0
 if direction == 1:
 headRow = 0
 headCol = line
 elif direction ==2:
 headCol = 0
 headRow = line
 elif direction == 3:
 headRow = 0 if line >= numRows else line
 headCol = line-numRows if line >= numRows else 0
 tailRow = headRow
 tailCol = headCol
 pathList = []
 while headRow < numRows and headCol < numCols:
 pathList.append(matrix[headRow][headCol])
 pathProduct *= matrix[headRow][headCol]
 pathLen+=1
 if pathLen > maxLen:
 pathProduct /= matrix[tailRow][tailCol]
 pathList = pathList[1:]
 if direction== 1:
 tailRow += 1
 elif direction == 2:
 tailCol += 1
 elif direction == 3:
 tailCol += 1
 tailRow += 1
 if pathProduct > maxProduct:
 maxProduct = pathProduct
 maxList = pathList
 if direction== 1:
 headRow += 1
 elif direction == 2:
 headCol += 1
 elif direction == 3:
 headCol += 1
 headRow += 1
 return maxProduct, maxList
matrix = [
 [1, 2, 3, 4, 5],
 [1, 1, 2, 3, 5],
 [3, 4, 5, 5, 5],
 [3, 4, 5, 9, 5],
 [1, 1, 5, 5, 25],
]

The issue here is that the solution constitutes changing the values of the "head" and "tail" variables based on the current direction being considered in the 2D requiring the use of multiple if/else statements. This makes the code a look longer and possibly harder to follow. I'm basing this off of these errors listed by pylint:

[pylint] C0103:Invalid function name "maxPathProduct"
[pylint] R0914:Too many local variables (17/15)
[pylint] C0103:Invalid argument name "maxLen"
[pylint] C0103:Invalid argument name "maxLen"

I'm not sure if these errors actually warrant any changes but if they do, is there anyway to possibly refactor the if/else statements or any unwieldy part of the code while maintaining the functionality of the solution?

Answer 1

First of all, if this function is not in a class you must remove the self parameter, there's no need of that. Then you should insert a check if the parameters are correct, that is the rows number and the columns number must be at least equals to maxLength:

if len(matrix) < maxLen and len(matrix[0]) < maxLen:
 return -1 # return error code

In this cases, when you have to move across a matrix, I suggest you to use a sort of direction tuples, which are tuples of the form (1,0), (0,1), (1,1), (-1,0) etc..; so for each element of the matrix you add to the indexes of that element one of this tuples multiplied for a number. Maybe it's more complicate to speak about it than show it:

def maxPathProduct(matrix, maxLen):
 if len(matrix) < maxLen and len(matrix[0]) < maxLen:
 return -1
 maxProduct = -1
 maxList = []
 directions = [(1, 0), (0, 1), (1, 1)] 
 for i in range(len(matrix)):
 for j in range(len(matrix[0])):
 for dir in directions:
 tempProduct = 1
 tempList = []
 inc = 0
 indexOutOfBound = False
 while len(tempList) < maxLen and not indexOutOfBound:
 row = i + dir[0] * inc
 col = j + dir[1] * inc
 if row < len(matrix) and col < len(matrix[0]):
 tempProduct *= matrix[row][col]
 tempList.append(matrix[row][col])
 inc += 1
 else:
 indexOutOfBound = True
 if tempProduct > maxProduct:
 maxProduct = tempProduct
 maxList = tempList
 return maxProduct, maxList

In this case you have only to move from left-to-right ((0,1)), up-to-down ((1,0)) and diagonally-up-to-down ((1,1)). With those direction tuples you can avoid that terrible long list of if-elif-else. I've tried this solution a bit, I'm not completely sure that it works, but I hope that you understand the trick.

• ChatterOne: As a slight optimization: they're unsigned integers, that means the tuple giving the max product is the same as the one give the max sum. But sum is usually faster than multiplication and takes longer to get to an overflow, so you could check the sum instead of the product.