Lesson 5-5 · Implementing compute_bfs_path()
Lesson 5-5 · Implementing compute_bfs_path()
Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.
This is the heart of Module 5: the algorithm you reviewed at the end of Lesson 5-2 becomes
about twenty lines of Python, each one a step you've done with a pencil. It comes in two
functions, one for each part of the review: bfs_distances() numbers the grid from the
destination, and compute_bfs_path() walks downhill from the start. Build and test them in
that order; every test prints, and the robot stays on the desk.
Learning Objectives
By the end of this lesson you will be able to:
- Match each line of
bfs_distances()andcompute_bfs_path()to a step of the paper method - Explain why
to_visit.pop(0)(oldest first) matters, and whatpop()would do instead - Explain why
if neighbor not in distanceis the whole "numbered once" rule - Write the walk downhill so the path leaves the start out, and return
[]when the start can't be reached
This lesson's skeleton
In the BFS PLANNER section, replace the placeholder compute_bfs_path() with these
outlines: the algorithm from Lesson 5-2's review, one numbered step per comment.
print_grid(), at the bottom, is given.
def bfs_distances(destination):
"""Steps from every reachable intersection to
destination, as a dictionary: the wave of numbers."""
# Program only, not a step of the algorithm: build the
# graph from BLOCKED; return {} if destination is not in it.
#
# Number the grid from the destination (Lesson 5-2):
# 1. Write 0 on the destination.
# 2. Put the destination on the to-visit list.
# 3. While the to-visit list is not empty:
# 4. Take the oldest one off the front. Call it current.
# 5. For each open neighbor of current:
# 6. If that neighbor has no number yet:
# 7. Give it one more than current's number.
# 8. Add it to the end of the to-visit list.
# 9. Return the numbers.
pass
def compute_bfs_path(start, destination):
"""Shortest path from start to destination around
BLOCKED, as the list of intersections to drive to."""
# Program only: build the graph from BLOCKED.
#
# Walk downhill from the start (Lesson 5-2):
# 1. Number the grid: call bfs_distances(destination).
# 2. If the start has no number, there is no path.
# 3. Start with an empty path, standing on the start.
# 4. Until you are standing on the destination:
# 5. Find the open neighbor whose number is one less
# 6. and step onto it.
# 7. Add where you are standing to the path.
# 8. That path is the answer.
pass
def print_grid(rows, cols, blocked, numbers):
"""Draw the grid the way it lies in front of you: the top
line is the far row, y = 0 is the bottom line. Each
intersection shows its entry in numbers, X if it is
blocked, . if it has no entry."""
for i in range(rows):
y = rows - 1 - i
line = " " + str(y) + " | "
for x in range(cols):
if (x, y) in blocked:
cell = "X"
elif (x, y) in numbers:
cell = numbers[(x, y)]
else:
cell = "."
line = line + "{:>3}".format(cell)
print(line)
print(" " + "-" * (3 * cols + 1))
footer = " "
for x in range(cols):
footer = footer + "{:>3}".format(x)
print(footer)
print_grid() is given: it's formatting, not pathfinding, and Module 6 uses it
unchanged. It prints the far row first, so the picture lies the way the grid does in
front of you. "{:>3}".format(cell) is "this value, right-aligned in three spaces."
Every line is a pencil step
Under each numbered comment you write the Python that does what the step says, usually
one line. Use the names from Lesson 5-3: distance for the numbers, a dictionary, and
to_visit for the list. Step 1 of bfs_distances() makes distance with one entry: the
destination, numbered 0.
An intersection gets an entry in distance only when the wave reaches it, so "is a key in
distance" means "has a number." That's why if neighbor not in distance is the whole
numbered-once rule.
The list is a queue: append() adds to the end and pop(0) takes from the front
(index 0), so the wave front moves out one step at a time.
In bfs_distances(), what does `if neighbor not in distance:` mean in pencil terms?
Activity · Build it in two stages
Build the two functions in order, running a test after each. Check every printed grid, path and step count against your traces from Lessons 5-1 and 5-2.
Step 1 · The numbers
Write bfs_distances(). Then write test_distances(): clear the blocked list, block
(1, 0) and (1, 1), and call
print_grid(ROWS, COLS, BLOCKED, bfs_distances((3, 0)))
Set the run line to it. It should print the wall grid you numbered in Lesson 5-1:
3 | 6 5 4 3
2 | 5 4 3 2
1 | 6 X 2 1
0 | 7 X 1 0
-------------
0 1 2 3
If a number is wrong, the bug is in this function, and you haven't written the walk yet, so there's only one place to look.
Step 2 · The walk downhill
Write compute_bfs_path(). If the start has no number, the wave never reached it, so
there's no path; that one check covers a blocked start, a blocked destination and a wall
between them.
Steps 4 to 7 are a loop inside a loop. The outer while keeps walking until you're on the
destination. The inner for looks through the neighbors for one with a number one less;
when it finds one, it steps onto it and uses break to stop looking. Check that the
neighbor has a number before you compare it: neighbor in distance and .... And notice
when the start is left out: you add an intersection to the path only after stepping onto
it, so the start never goes in, and "already there" comes free: when start == destination,
the loop never runs and the path is [].
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?
Run the five paper tests
Five cases, all grids you traced by hand. Write test_bfs_open() for three open-grid
cases: (0, 0) to (3, 3), (0, 0) to (0, 3), and (2, 2) to (2, 2); start it with
clear_blocked() so the test means the same whatever ran before it. Then write
test_bfs_walls() for the two with walls: add_blocked() the two wall intersections and
plan (0, 0) to (3, 0); then block the rest of the column at x = 1 and plan again. Print
each path and len(path) next to the step count you expect, and the blocked list before
each wall test. Step counts must match; the exact path may differ from yours and still be
right.
=== Test 1: no obstacles, (0,0) to (3,3) ===
Path: [(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
Steps: 6 (expect 6)
=== Test 2: straight line, (0,0) to (0,3) ===
Path: [(0, 1), (0, 2), (0, 3)]
Steps: 3 (expect 3)
=== Test 3: already there, (2,2) to (2,2) ===
Path: []
Steps: 0 (expect 0)
=== Test 4: wall across the grid, (0,0) to (3,0) ===
Blocked: [(1, 0), (1, 1)]
Path: [(0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0)]
Steps: 7 (expect 7 -- around the wall)
=== Test 5: destination walled off ===
Blocked: [(1, 0), (1, 1), (1, 2), (1, 3)]
Path: []
Steps: 0 (expect 0 -- no way through)
Tests 3 and 5 both return []: one because the start is already the destination, the
other because the start never got a number. Next lesson's harness tells them apart.
Activity · Break it on purpose
Once all five pass, break bfs_distances() two ways. Put each back before the next.
- Change
pop(0)topop(). Run Test 4 and count the steps: more.pop()takes the newest intersection, so the wave no longer moves out one step at a time and the numbers stop being shortest distances. The walk downhill trusts the numbers, so it follows them on a longer route. Runtest_distances()too and compare the grid with yours. - Delete
if neighbor not in distance:(keep the two lines under it, one indent level out). Run Test 1. Every neighbor goes back on the list every time, so the list never empties and the program hangs. Press Ctrl-C. That one line is the numbered-once rule.
You change pop(0) to pop() in bfs_distances() and Test 4, the wall test, prints Steps: 9 instead of 7. What changed?
Wrap-up
- Which line is "take the oldest one"? (
to_visit.pop(0).) What wouldpop()do? (Newest first — depth-first, not shortest.) - Which line is "numbered once"? (
if neighbor not in distance.) - Why does the walk add an intersection only after stepping onto it? (So the start is never in the path — Rule 2.)
- Two cases return
[]. What are they? (Already there; the start never got a number.)