Skip to main content
Module 5 · Pathfinding Around Obstacles

Lesson 5-5 · Implementing compute_bfs_path() — Knowledge ChecksAnswer key

Correct answers are marked and the explanation follows each question.

  1. In bfs_distances(), what does `if neighbor not in distance:` mean in pencil terms?

    1. A."Only if this intersection has no number yet"✓
    2. B."Only if this intersection is not blocked"
    3. C."Only if this intersection is the destination"
    4. D."Only if we have not visited the current intersection"

    An intersection gets an entry in distance the first time the wave reaches it, so not-in-distance means not-yet-numbered. Blocked intersections never come up at all — they aren't in the graph.

  2. A classmate's walk adds current to the path BEFORE stepping. Their straight-line test, (0,0) to (0,3), prints Steps: 3, but the path is [(0, 0), (0, 1), (0, 2)]. What's wrong?

    1. A.The start is in the path and the destination is missing✓
    2. B.Nothing: 3 steps is right
    3. C.The path goes the wrong way
    4. D.A blocked intersection got into the path

    Adding before stepping writes down where you were, not where you went: the start goes in, and the loop ends on the destination without writing it. The step count is right, which is why a test should check the list, not just its length.

  3. You change pop(0) to pop() in bfs_distances() and Test 4, the wall test, prints Steps: 9 instead of 7. What changed?

    1. A.Newest-first writes numbers that are not shortest distances, and the walk downhill follows them on a longer route✓
    2. B.The graph lost some neighbors
    3. C.The walk downhill went the wrong way
    4. D.Nothing — 9 is also a shortest path

    Oldest-first (a queue) moves the wave front out one step at a time, so each number is the fewest steps. Newest-first (a stack) numbers along whatever route it happens to dive down, and the walk is only as good as the numbers.

  4. Why is Manhattan given an add_blocked() method that does nothing?

    1. A.So every planner has the same shape and the harness never has to know which one it holds✓
    2. B.Because Manhattan can route around obstacles if told about them
    3. C.Python requires every class to have the same methods
    4. D.It is a bug

    The swap only works if every planner answers the same two calls. Manhattan ignores add_blocked, and the harness shows the consequence: it drives through the wall.