OutputError: Find the longest path in a matrix with given constraints

Question

My matrix is:

4 8 7 3 
2 5 9 3 
6 3 2 5 
4 4 1 6

Problem (Skiing):

Each number represents the elevation of that area of the mountain.

From each area (i.e. box) in the grid, you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in.

I.e. you can only ski downhill.

You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit.

And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation.

My Solution:

def findSkiPath():
    mySolution = [0] * 3
    mySolution[0] = 0 # Distance
    mySolution[1] = 0 # Drop
    cellIndexRow = 0
    cellIndexCol = 0
    myPath = []
    myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
    countRows = len(myMatrix)
    countCols = len(myMatrix[0])
    for i in range(0, countRows - 1):
        for j in range(0, countCols - 1):
            myValue = myMatrix[i][j]
            myPath.append(myValue)

            #check east
            cellIndexRow = i
            cellIndexCol = j + 1
            checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )

            #check west
            cellIndexRow = i
            cellIndexCol = j - 1
            checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )

            #check north
            cellIndexRow = i - 1
            cellIndexCol = j
            checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )            

            #check south
            cellIndexRow = i + 1
            cellIndexCol = j
            checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath )
    print (mySolution)

def checkAdjacentCells(cellIndexRow, cellIndexCol, myValue, myMatrix , mySolution , myPath ):

    #The base case - If we go beyond the limits of the matrix
    if (cellIndexRow < 0 or cellIndexRow > (len(myMatrix) - 1) or cellIndexCol < 0 or cellIndexCol > (len(myMatrix[0]) - 1)):
        evaluateSolution(mySolution , myPath )
        return

    #check if the next cell has a lower value than the current cell
    tmpValue = myMatrix[cellIndexRow][cellIndexCol]
    if tmpValue < myValue:
        newPath = myPath
        newPath.append(tmpValue)

        r = cellIndexRow
        c = cellIndexCol
        #check east
        cellIndexRow = r
        cellIndexCol = c + 1
        checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )

        #check west
        cellIndexRow = r
        cellIndexCol = c - 1
        checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )

        #check north
        cellIndexRow = r - 1
        cellIndexCol = c
        checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )          

        #check south
        cellIndexRow = r + 1
        cellIndexCol = c
        checkAdjacentCells(cellIndexRow, cellIndexCol, tmpValue, myMatrix , mySolution , newPath )

    evaluateSolution(mySolution , myPath )

def evaluateSolution(mySolution , myPath ):

    myDistance = 1
    mySolutionDistance = int(mySolution[0])
    mySolutionDrop = int(mySolution[1])

    if myDistance < mySolutionDistance:
        return

    myDrop = myPath[0] - myPath[-1]

    if myDistance > mySolutionDistance or myDrop > mySolutionDrop:
        mySolution[0] = myDistance
        mySolution[1] = mySolutionDrop
        mySolution[2] = myPath

if __name__ == "__main__":

    findSkiPath()

Issues:

Current output (distance, drop, path):

[1, 0, [4, 2, 8, 7, 3, 4, 2, 5, 2, 3, 2, 1, 7, 3, 2, 5, 2, 3, 2, 1, 9, 3, 5, 2, 3, 2, 1, 7, 3, 2, 1, 6, 3, 2, 1, 2, 4, 3, 2, 1, 2, 1]]

Expected output:

[5,8,[9,5,3,2,1]]

On this particular map, the longest path down is of length=5, drop=8 (9-1=8), and path: 9-5-3-2-1.

Answer 1

One can approach the in the question described challenge in two different ways:

1. using a recursive algorithm which walks only valid paths checking already while iterating through the matrix elements if the given requirements are fulfilled

2. doing it in two steps:

   2.1. getting an iterator over all possible paths with a simple call to an in the itertools module available function permutations()

   2.2. picking from the generated paths these ones which fulfill the requirements

The code for the second approach is easier to write and to understand, but the huge amount of possible paths already for a 4x4 size of a matrix makes it practically impossible to run it for larger matrix sizes.

The code of the first approach can handle larger sizes of matrices, but has the disadvantage of being harder to grasp how it works to adjust it in case of other constraints.

The question asked here is a 100% 1:1 duplicate of a question asked two years ago here on stackoverflow and titled "Maximum number of elements in the path of a matrix". Anyway here the solution given in an answer to that old question again:

theMatrix = [
                [ 4, 8, 7, 3],
                [ 2, 5, 9, 3],
                [ 6, 3, 2, 5],
                [ 4, 4, 1, 6]
]

def longest_path(matrix):
    def inner_longest_path(x, y):
        best, best_path = 0, []
        # for all possible neighbor cells...
        for dx, dy in ((+1, 0), (-1, 0), (0, +1), (0, -1)):
            # if cell is valid and strictly smaller...
            if (0 <= x + dx < len(matrix) and 0 <= y + dy < len(matrix[x]) 
                    and matrix[x+dx][y+dy] < matrix[x][y]):
                n, path = inner_longest_path(x+dx, y+dy)  ### RECURSION
                # check if the path starting at that cell is better
                if n > best:
                    best, best_path = n, path
        return best + 1, [matrix[x][y]] + best_path

    return max(inner_longest_path(x, y) for x, row in enumerate(matrix) 
                                         for y, _ in enumerate(row))

print( longest_path(theMatrix) )

The code above prints:

(5, [9, 5, 3, 2, 1])

Now let's take a look also at the code of the non-recursive approach provided here be me myself:

# myMatrix = [[4, 5, 8, 7],[1, 1, 5, 9], [0, 7, 5, 5], [7, 4, 2, 9]]
#  4 5 8 7
#  1 1 5 9 
#  0 7 5 5
#  7 4 2 9
myMatrix = [[4, 5, 8],[1, 1, 5], [0, 7, 5]]
#  4 5 8
#  1 1 5
#  0 7 5
# myMatrix = [[4, 5],[1, 1]]
#  4 5
#  1 1

def getAllValidSkiingPathsFrom(myMatrix): 
# def getDictRepresentationOf(myMatrix):
    dctOfMatrix = {}
    for row in range(len(myMatrix)):
        for column in range(len(myMatrix[0])):
            currPoint = (column, row)
            dctOfMatrix[currPoint] = myMatrix[row][column]

    lstIndicesOfAllMatrixPoints = list(dctOfMatrix.keys())
    setAllPossiblePaths = set()

    from itertools import permutations
    for pathCandidate in permutations(lstIndicesOfAllMatrixPoints): 
        lstPossiblePath = []
        prevIndexTuple = pathCandidate[0]
        lstPossiblePath.append(prevIndexTuple)
        for currIndexTuple in pathCandidate[1:]:
            if abs(currIndexTuple[0]-prevIndexTuple[0]) + abs(currIndexTuple[1]-prevIndexTuple[1]) > 1:
                break # current path indices not allowed in path (no diagonals or jumps)
            else:
                if dctOfMatrix[currIndexTuple] >= dctOfMatrix[prevIndexTuple]: 
                    break # only "down" is allowed for "skiing" 
                else:
                    lstPossiblePath.append(currIndexTuple)
                    prevIndexTuple = currIndexTuple
        if len(lstPossiblePath) > 1 and tuple(lstPossiblePath) not in setAllPossiblePaths: 
            setAllPossiblePaths.add(tuple(lstPossiblePath))

    return setAllPossiblePaths, dctOfMatrix
#:def getAllValidSkiingPathsFrom

setAllPossiblePaths, dctOfMatrix = getAllValidSkiingPathsFrom(myMatrix)

for path in setAllPossiblePaths:
    for point in path:
        print(dctOfMatrix[point], end=',')

Here the results for the 2x2 and 3x3 versions of myMatrix:

#  4 5
#  1 1
4,1,
5,1,
5,4,
5,4,1,

#   4 5 8
#   1 1 5
#   0 7 5
5,1,
8,5,1,
7,1,
4,1,
5,1,
5,4,
8,5,1,
1,0,
5,4,1,0,
8,5,4,1,
8,5,4,1,0,
8,5,4,
8,5,
7,0,
7,5,
8,5,
4,1,0,
5,4,1,

I hope the code is self-explanatory, but if not here the rough idea:

1. build a dictionary representing the matrix where the keys are tuples of (column,row)"coordinates" and the values the values in the matrix.

2. build a list of all possible full paths within the matrix (permutations)

3. filter the list of all possible full paths to extract only the valid ones according to what is required (apply criteria).

I didn't have run the computational very expensive calculation of the result for the 4x4 matrix as it takes for sure more than several minutes on my box.

For the sake of completeness I would like to mention that there is also another question HERE on stackoverflow which is a variation of THIS question (it has a bit other rules for valid paths and requests an algorithm able to work on irregular matrices).

Answer 2

The main problem with this is that you don't do any sort of backtracking. You are traversing the matrix appropriately, but you don't do anything to maintain the concept of a particular path. Instead, for each square you visit, you simply append all legal moves to a single list.

Instead, consider keeping the current path as a local variable. For each legal move from the given square, you make a separate recursive call to find more moves. Each of those will add a legal move to the end of the local path.

As you return from each call, compare the best found path with the one you've been saving (the best so far); keep the better of those two, and go to the next legal move. When you've considered each of the four directions, then return the best-known path to the calling instance.

There are plenty of examples of backtracking on line and on this site; search out some that you find understandable. You might look under coin combination recursion (finding a set of coins that add to a certain amount) -- they're not the same algorithm, but the backtracking ideas above are shown more clearly.

Does that get you moving toward a solution?