0

I'm currently writing a short code as follows that returns the co-ordinates and size of the longest path in a grid with the following constraints:

  1. Only move up,down,left,right
  2. Only move to a cell that has a maximum difference of 1
  3. Cannot pass through a cell twice
  4. Must start in the top row

My code is as follows:

import numpy as np
grid = np.random.randint(3, size=(5, 5))

def get_longest_path(grid):

    # setup
    cols, rows = grid.shape # length, width

    # pathfinder function
    def pathfinder(i,j):        
        best, best_path = 0, []
        udlr = {(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)}  # up down left right directions
        for x, y in udlr:
            if 0 <= x < cols and 0 <= y < rows and abs(grid[x][y] - grid[i][j]) <= 1: # check it's in bounds   
                #grid[x][y] > grid[i][j]
                n, path = pathfinder(x,y)
                if n > best:
                    best, best_path = n, path
        return best + 1, [(i,j)] + best_path
        
    
    #return longest path
    return max(pathfinder(0,j) for j in range(rows))

get_longest_path(grid)

As far as I can tell, it works fine if I use the constraint grid[x][y] > grid[i][j] in place of abs(grid[x][y] - grid[i][j]) <= 1. However, if I run this as it is, the Jupyter kernel dies straight away.

Perhaps it starts an infinite loop, but I can't see why this would be the case.

Any advice would be appreciated, thank you.

Chris Taylor
  • 1
  • 2

1 Answers1

0

Try defining pathfinder() outside and above the get_longest_path() function.

Tyler2P
  • 2,324
  • 26
  • 22
  • 31
smcrowley
  • 451
  • 3
  • 10
  • Hi, thanks for the suggestion. I gave this a go, and now I get an actual RecursionError on the ```n, path = pathfinder(grid,x,y)``` line. Any ideas? Thanks. – Chris Taylor Dec 16 '21 at 17:53
  • If your error has to do with the maximum recursion, then two good links explaining why this happens and how to hard get around it are these: https://stackoverflow.com/a/3323013/11616708 https://www.geeksforgeeks.org/python-handling-recursion-limit/ – smcrowley Dec 18 '21 at 00:54
  • but honestly, it might also be worth trying to work logically around how deep it has to go by adding checks comparing how many steps have been taken in the current path vs the known best, and if its > the known best, you can break out of that path and continue checking others – smcrowley Dec 18 '21 at 00:56