0

This recursive function returns the highest score of walking from the top left corner to the bottom right, only moving down or to the right.

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

def walk_the_path(matrix, x=0, y=0, score=0, path=[]):
    height, length = len(matrix)-1, len(matrix[0])-1
    score += matrix[x][y]
    if x != height and y != length:
        return max(walk_the_path(matrix, x+1, y, score),
                   walk_the_path(matrix, x, y+1, score))
    elif x == height and y != length:
        return walk_the_path(matrix, x, y+1, score)
    elif x != height and y == length:
        return walk_the_path(matrix, x+1, y, score)
    return score

It works fine and returns 29 for the test matrix, which is the score of the following path: down, down, right, right.

I tried to adjust the function to also, return the path in the form of [(0,0), (1,0), (2,0), (2,1), (2,2)]. As the function returns a tuple of score and path, I first tried to maximize based on the first term only, using walk_the_path(matrix, x+1, y, score, path)[0], but got TypeError: 'int' object is not subscriptable. So i tried running maximizing the output without slicing, as such:

def walk_the_path(matrix, x=0, y=0, score=0, path=[]):
    height, length = len(matrix)-1, len(matrix[0])-1
    score += matrix[x][y]
    path.append((x, y))
    if x != height and y != length:
        return max(walk_the_path(matrix, x+1, y, score, path),
                   walk_the_path(matrix, x, y+1, score, path))
    elif x == height and y != length:
        return walk_the_path(matrix, x, y+1, score, path)
    elif x != height and y == length:
        return walk_the_path(matrix, x+1, y, score, path)
    return (score, path)

This returns the correct answer, but it seems like it appends the list at the top level in all recursions. This is the output.

(29, [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 1), (2, 1), (2, 2), (1, 2), (2, 2), (0, 1), (1, 1), (2, 1), (2, 2), (1, 2), (2, 2), (0, 2), (1, 2), (2, 2)])

Why is that?

And I would also be interested in knowing why I can't slice the function output in max()? And perhaps. how it would be best to write without recursions.

Thanks!

Mubli
  • 1
  • 4
    Looks like you ran into [Least Astonishment](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) with your `path` argument. – Cory Kramer Jan 02 '20 at 12:32
  • wrt/ the "'int' object is not subscriptable" thing: in at least one case, your function returns an int (the call to `max`) instead of a `(score, path)` tuple. You have to be consistent in what your function returns. – bruno desthuilliers Jan 02 '20 at 12:43

0 Answers0