Number of unique paths for robot pathfinding

[kevinlin1]

Thanks for offering this service, Pamela!

The recursion visualizer is great for tree recursion (aka multiple recursion). I'm introducing dynamic programming by using a motivating example of robot pathfinding in a 2-D grid, and I like to compare the dynamic programming approach to a tree recursive program that students have seen before. The recursion visualizer is a nice way to refresh the idea and showcase the calls to the same subproblems.

def paths(w, h):
    if w == 0 or h == 0:
        return 1
    else:
        return paths(w - 1, h) + paths(w, h - 1)

A call to paths(2, 2) shows the way that the algorithm finds 6 total paths to get from position (0, 0) to position (2, 2) in a 3x3 grid. I can then compare this to the dynamic program:

def paths(w, h):
    grid = [x[:] for x in [[0] * (w + 1)] * (h + 1)]
    for x in range(w + 1):
        grid[x][0] = 1
    for y in range(h + 1):
        grid[0][y] = 1
    for x in range(1, w + 1):
        for y in range(1, h + 1):
            grid[x][y] = grid[x - 1][y] + grid[x][y - 1]
    return grid[w][h]

[pamelafox]

Thanks for sharing, Kevin! Given the lack of recursive calls for that second one (it's quite a contrast to the first), do you step through that with PythonTutor?

I like to also visualize robot-grid stuff using a turtle graphics animation, though I can't find the ones I made for UC berkeley, and that might not be as appropriate for this function.

[kevinlin1]

Yeah, for the dynamic programming activity, I walk through it by marking slides to show how the process unfolds in a 2-d grid. It's helpful to have the recursion visualization nearby too so that we can compare the redundant call to paths(1, 1) that's computed twice in the recursive program.

[pamelafox]

Love the slide. Amazing how much more interested I am in a problem when there's an adorable robot graphic. 🤖 And yeah paths(1, 1) is interesting.