3
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ChatterOne Mar 21 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.