Lesson 5-6 · Testing and Swapping
Lesson 5-6 · Testing and Swapping
Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.
Your planner passes five tests. Now test it properly, with a testing idea that outlasts this course. Then point the same tests at Module 4's Manhattan planner and watch it fail, for exactly the reason this module exists.
Learning Objectives
By the end of this lesson you will be able to:
- Explain why an exact-match test is wrong for BFS and right for Manhattan
- Name the five properties every correct path has, and write each as one
if - Explain why the walled-off case needs its own test
- Hand a function to another function, and explain what
planner(position, destination)does inside the harness - Run one harness against Manhattan and BFS and explain every FAIL line
- Write a main program that works with either planner by changing one name
Two right answers, one test
Compare your Lesson 5-5 Test 1 path with a classmate's. If they match, here's another correct one:
[(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)] # yours, maybe
[(0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)] # also six steps, also right
Now here's the test from Module 4's Lesson 4-3, still in your file as run_test():
if actual == expected:
print(test_name, "- PASS")
One of those two correct paths gets marked FAIL. Exact match was fine for Manhattan,
which has exactly one answer. BFS doesn't, so it needs a different kind of test, with a
different name. run_test() stays in the MANHATTAN PLANNER section, doing its job.
Test what must be true
Forget the exact list. What must be true of any correct path from (0, 0) to
(3, 3)?
- The first step is next to the start.
- The last step is the destination.
- Every step is next to the one before it.
- No step is a blocked intersection.
- With nothing blocked, the number of steps is the Manhattan distance.
Each is a one-line check. Together they are stricter than an exact match, which only tells you a path is the one you expected, and they allow every correct answer. That's a property test: check what must be true, not what you happened to expect.
Why are the five property checks stronger than comparing with one expected path?
This lesson's skeleton
Paste this at the end of the BFS PLANNER section. You write the two helpers and the
checker. run_all_tests() (the suite) and navigate() are given: they are the "same
program" in "same program, swap the planner."
# --- Lesson 5-6: the property harness ---
# Tests any planner by what must be true of its path, not by
# one expected list, because BFS has many right answers.
# run_all_tests() is handed a planner FUNCTION and runs the
# six cases through it: one program tests Manhattan and BFS.
# Module 4's run_test() stays; exact match is right there.
def manhattan_distance(a, b):
"""Steps between a and b with nothing in the way."""
pass
def is_neighbor(a, b):
"""True when a and b are one step apart."""
pass
def check_path(path, start, destination):
"""Return a list of everything wrong with path as a route
from start to destination; [] means it is good."""
# problems = []
# an empty path is fine only if already there; return
# 1. first step next to the start?
# 2. last step the destination?
# 3. every step next to the one before it?
# 4. no step in BLOCKED?
# return problems
pass
def run_path_test(test_name, planner, start, destination, expected_steps):
"""Ask planner for a path, check the five properties, print
PASS or FAIL with the path; return True on a pass."""
# path = planner(start, destination)
# problems from check_path(), plus 5. the step count
# no problems: print " PASS ", test_name, "", path
# otherwise: print " FAIL " the same way, then each
# problem on its own line, " - " in front
pass
def run_no_path_test(test_name, planner, start, destination):
"""For a walled-off destination the only right answer is
[]; print PASS or FAIL and return True on a pass."""
pass
def run_all_tests(name, planner):
"""The six cases, through whichever planner is handed in:
four on the open grid, the wall, and walled off."""
print("==========", name, "==========")
passed = 0
clear_blocked()
if run_path_test("open (0, 0) to (3, 3)", planner, (0, 0), (3, 3), 6):
passed = passed + 1
if run_path_test("open (0, 0) to (0, 3)", planner, (0, 0), (0, 3), 3):
passed = passed + 1
if run_path_test("open (2, 1) to (0, 3)", planner, (2, 1), (0, 3), 4):
passed = passed + 1
if run_path_test("open (1, 1) to (1, 1)", planner, (1, 1), (1, 1), 0):
passed = passed + 1
add_blocked((1, 0))
add_blocked((1, 1))
if run_path_test("wall at (1,0),(1,1): (0,0) to (3,0)", planner, (0, 0), (3, 0), 7):
passed = passed + 1
add_blocked((1, 2))
add_blocked((1, 3))
if run_no_path_test("walled off: (0,0) to (3,0)", planner, (0, 0), (3, 0)):
passed = passed + 1
clear_blocked()
print(name + ":", passed, "of 6 passed")
def navigate(planner, position, destination):
"""Plan with planner and print the path; return
destination, where the robot would be after driving it."""
path = planner(position, destination)
print(" Path from", position, "to", destination, ":", path, " Steps:", len(path))
return destination
Activity · Build the harness
Step 1 · Two helpers
manhattan_distance() is the Lesson 5-1 count: the x difference plus the y
difference, each made positive with abs(). is_neighbor() asks whether that
distance is exactly 1. Write both.
Step 2 · check_path() returns a list of problems
One if per property, each appending a sentence to problems when it fails; an
empty list means the path is good. The outline's first line is the special case: an
empty path is correct when position == destination and a problem otherwise. Either
way there are no steps to check, so return at once.
Make the sentences specific. A bare FAIL gets ignored; "drives through blocked intersection (1, 0)" tells you what to fix. That's why it returns problems, not
True/False. Build each with + and str(): property 1's is "first step " + str(path[0]) + " is not next to the start " + str(start), and the others likewise
name the step and say what's wrong. Property 3 loops from the second step to the last,
comparing each with the one before; property 4 loops over every step.
run_path_test() checks the fifth property, the step count, against the count its
caller gives it.
One case check_path can't judge: an empty path for a walled-off destination is
correct, but looks just like "forgot to look." So walled-off gets its own small
test, run_no_path_test(), where the only right answer is [].
A planner returns [(0,1), (0,3)] for (0,0) to (0,3). Which property fails, and what does the FAIL line say?
Step 3 · Hand the harness its planner
The one new Python idea in the lesson: handing a function to a function. Look at
run_path_test()'s planner parameter and the two lines you're about to write:
def run_path_test(test_name, planner, start, destination, expected_steps):
path = planner(start, destination)
...
run_all_tests("Manhattan", compute_manhattan_path)
run_all_tests("BFS", compute_bfs_path)
compute_bfs_path, with no parentheses, is the function itself, handed over like a
number or a list. run_all_tests passes it on to run_path_test, where
planner(position, destination) calls it. Both planners have the same shape, so the
harness never needs to know which one it has.
Try it at the prompt first: f = compute_bfs_path, then f((0, 0), (3, 3)).
Now write run_path_test() and run_no_path_test() from their outlines. Each
returns True on a pass so run_all_tests() can count. PASS and FAIL lines look
like this:
PASS open (0, 0) to (0, 3) [(0, 1), (0, 2), (0, 3)]
FAIL wall at (1,0),(1,1): (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- drives through blocked intersection (1, 0)
- expected 7 steps, got 3
Inside run_path_test, what does `path = planner(start, destination)` do when the harness was called with run_all_tests("BFS", compute_bfs_path)?
Activity · Run it against both
Write test_harness(), the two run_all_tests() lines above, and set the run line
to it. BFS should pass 6 of 6. Then read Manhattan's lines carefully:
========== Manhattan ==========
computing path from: (0, 0) to: (3, 3)
PASS open (0, 0) to (3, 3) [(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
computing path from: (0, 0) to: (0, 3)
PASS open (0, 0) to (0, 3) [(0, 1), (0, 2), (0, 3)]
computing path from: (2, 1) to: (0, 3)
PASS open (2, 1) to (0, 3) [(1, 1), (0, 1), (0, 2), (0, 3)]
computing path from: (1, 1) to: (1, 1)
PASS open (1, 1) to (1, 1) []
computing path from: (0, 0) to: (3, 0)
FAIL wall at (1,0),(1,1): (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- drives through blocked intersection (1, 0)
- expected 7 steps, got 3
computing path from: (0, 0) to: (3, 0)
FAIL walled off: (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- there is no way through, so the path should be empty
Manhattan: 4 of 6 passed
Manhattan isn't broken. It does exactly what Module 4 built it to do, across then up or down, and it has no idea what a wall is. The harness just showed why this module exists.
Then the same swap in a main program. navigate(), the skeleton's last function,
plans with the planner it's handed, prints the path, and returns the destination:
where the robot would be after driving it. Write test_swap(): block (2, 0), then
run two trips, (0, 0) to (3, 3) and back, with each planner. Only the planner's
name changes:
position = navigate(compute_manhattan_path, (0, 0), (3, 3)) # through the wall
position = navigate(compute_bfs_path, (0, 0), (3, 3)) # around it
Finally, break a property on purpose: make compute_bfs_path return path[1:]
(drop the first step), then path + [destination]. Which property catches each?
Real-world connections
Property-based testing
Professional test tools generate thousands of random inputs and check properties, exactly as this harness checks paths — because for most real programs there is no single expected answer.
Plug-in parts
Handing a function (or object) to code that doesn't know which one it got is how programs are built from swappable parts: sort orders, file formats, planners.
Test before you drive
Everything the harness checks here is checked without a robot. Real robot teams test the planner on a laptop for the same reason: it's faster, and it separates "the algorithm is wrong" from "the robot drove wrong."
Wrap-up
- Why not compare with one expected path? (BFS has many correct answers; the properties allow all of them and check validity.)
- What are the five properties? (Starts next to the start; ends at the destination; every step a neighbor; no blocked step; Manhattan-distance length on an open grid.)
- Why does walled-off get its own test? (
check_pathcan't tell it from a broken planner's[].) - What's passed in
run_all_tests("BFS", compute_bfs_path)? (The function itself.) - Why does Module 4's
run_test()keep its name and its job? (Exact match is right for a planner with one answer.)