Memoized search on a grid

When there is no fill order to find, let the recursion discover it.

Why it works

Stop finding an order and let recursion find it

Memoized recursion needs no fill order. It computes what it needs when it needs it, and the memo prevents recomputation. That is the whole reason to prefer it here.

The state is the cell. Its answer is the best achievable starting from it, and the transition takes the best over the neighbors that the rule allows moving to.

Which neighbors those are is worth seeing before writing anything. Below, one grid is listed cell by cell with the moves the rule permits out of each.

1grid = [[9, 9, 4],2        [6, 6, 8],3        [2, 1, 1]]4 5rows, cols = len(grid), len(grid[0])6for r in range(rows):7    for c in range(cols):8        onward = []9        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):10            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:11                onward.append(grid[nr][nc])12        print(f"from {grid[r][c]} at ({r}, {c}) you may move to {sorted(onward)}")

Nothing points back at anything below it, so the dependencies can never form a cycle.

Predict the output· 5 min

Predict the output: does the answer depend on how you arrived?

The same cell is reached along two different routes. Type the three lines it prints.

Python

1grid = [[1, 2],2        [3, 4]]3 4# Two ways to arrive at the 4, and what remains reachable afterwards.5print("via 1 then 2:", [4])6print("via 1 then 3:", [4])7print("moves available from the 4 either way:", [])

Printed output

Problem· 30 min

Longest Increasing Path In A Matrix

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1grid = [[9, 9, 4],2 [6, 6, 8],3 [2, 1, 1]]4 5rows, cols = len(grid), len(grid[0])6for r in range(rows):7 for c in range(cols):8 onward = []9 for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):10 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > grid[r][c]:11 onward.append(grid[nr][nc])12 print(f"from {grid[r][c]} at ({r}, {c}) you may move to {sorted(onward)}")

1grid = [[1, 2],2 [3, 4]]3 4# Two ways to arrive at the 4, and what remains reachable afterwards.5print("via 1 then 2:", [4])6print("via 1 then 3:", [4])7print("moves available from the 4 either way:", [])