Lesson 6-5 · Three Planners, One Harness
Lesson 6-5 · Three Planners, One Harness
Teacher mode is on. Toggle it off (bottom-right) to preview the student view.
This lesson is for students who built the Manhattan and BFS classes in Lessons 4-3
and 5-5. It adds the third one, Dijkstra, and runs all three as objects through the
Module 5 class harness. The harness never finds out which one it is holding. That
property has a name — polymorphism — and this is the cleanest place in the course
to see it. If you did Lesson 6-3 as a function, this lesson replaces that function with
the class; if you skipped ahead from 6-3, this is where you write it.
Learning Objectives
By the end of this lesson you will be able to:
- Write the
Dijkstraclass by copyingBFSand making the same two changes as Lesson 6-3 - Give it
add_slow_edge(),clear_slow_edges()andweight()as methods, with the slow list inside the object - Run
Manhattan(),BFS()andDijkstra()through one harness and read the results - Explain why the harness can treat three different classes the same way
This lesson's skeleton
This is the class-track skeleton for the DIJKSTRA PLANNER section. Paste it in place
of the section's banner and compute_dijkstra_path() — closest() sits under the
new banner, and dijkstra_distances(), compare(), the Lesson 6-4 part and your
tests stay where they are — and move your Lesson 6-3 body into compute_path(). The WEIGHTED GRAPH section stays as it is too: from today it is
the harness's record of the slow edges, the way HARNESS_BLOCKED is its record of
the blocks.
# ===== DIJKSTRA PLANNER (class version) =====
# One Dijkstra object holds the grid size, ITS OWN blocked
# list and ITS OWN slow list, and plans by cost around both:
# the BFS class with the slow-list methods added and the two
# Lesson 6-3 changes inside compute_path(). Same names as the
# function version, with planner. in front; the 5-6 class
# harness tests all three planners without naming one.
class Dijkstra:
def __init__(self, rows=4, cols=4):
self.rows = rows
self.cols = cols
self.blocked = []
self.slow_edges = [] # NEW: lives inside the planner
def add_blocked(self, intersection):
# as in BFS
pass
def clear_blocked(self):
pass
def add_slow_edge(self, a, b, cost):
# your function, with self.slow_edges for SLOW_EDGES
pass
def clear_slow_edges(self):
pass
def weight(self, a, b):
# your function, reading self.slow_edges
pass
def compute_path(self, start, destination):
# your compute_dijkstra_path(), with
# build_graph(self.rows, self.cols, self.blocked)
# and self.weight(); closest() stays a function
pass
planner = Dijkstra()
The third class
BFS from Lesson 5-5 holds its blocked list in self.blocked and exposes
add_blocked(), clear_blocked() and compute_path(start, destination). Dijkstra
is a copy of it with one more list and the two changes. Same shape as the other two:
compute_path(start, destination), told the start every call, returning a path
that excludes the start. The slow list is the planner's own data, as the blocked list
already was, so nothing outside the object reaches in to change it.
The name under the class is the Lesson 5-5 rule again: one object called planner,
and it is your newest planner. Delete planner = BFS(), and everything in Module 5
that said planner. now plans by cost — on a grid with no slow edges, it gives the
same answers as before, which you can prove by running any Module 5 test.
Where does the slow-edge list live in the class version, and why?
One harness, three objects
The Lesson 5-6 class harness is handed an object and calls its methods:
run_all_tests("Manhattan", Manhattan())
run_all_tests("BFS", BFS())
run_all_tests("Dijkstra", Dijkstra())
Inside, every line is planner.compute_path(start, destination),
block(planner, ...) or clear(planner). Nothing in the harness names a class. The
seventh case needs one more helper of the block() kind — slow(planner, a, b, cost)
tells the planner about a slow edge and records it in SLOW_EDGES, so that
path_cost() adds up the true weights whichever planner is being tested — and
clear() has to forget the slow edges as well as the blocks, on both sides. Paste
these under clear() in the 5-6 part of the file, and make the three edits:
def slow(planner, a, b, cost):
"""Tell planner about the slow edge AND note it in
SLOW_EDGES, so path_cost() can see it."""
pass
clear(planner)also callsplanner.clear_slow_edges()andclear_slow_edges().- In
run_all_tests(), the seventh case:slow(planner, (0, 1), (0, 2), 5)where it saidadd_slow_edge(...),planner.compute_path(...)for the plan, andclear(planner)for both clears. compare()makes a freshBFS()and a freshDijkstra(), and a fresh object knows nothing — so before it plans, each one is told every entry inSLOW_EDGESwithp.add_slow_edge(a, b, cost). Two lines, andBFSignores them.
That slow() call, and clear()'s, mean Manhattan and BFS need an
add_slow_edge() and a clear_slow_edges() too, even though they ignore them,
exactly as Manhattan.add_blocked() did nothing in Module 5:
class BFS:
# ...
def add_slow_edge(self, a, b, cost):
pass # BFS does not plan by cost; it accepts the call and ignores it
def clear_slow_edges(self):
pass
run_all_tests("Dijkstra", compute_dijkstra_path)
path = planner(position, destination)
add_slow_edge((0, 1), (0, 2), 5)
run_all_tests("Dijkstra", Dijkstra())
path = planner.compute_path(start, destination)
slow(planner, (0, 1), (0, 2), 5)
Three classes, one set of method names, one harness that works on any of them. That is polymorphism: code written against a shape — the names a planner answers to — rather than against one particular class. You have been using it since Lesson 5-6, where the harness was handed a function. Objects make the shape explicit: it is the list of methods.
Why must BFS have an add_slow_edge() method that does nothing?
Activity · Build it, test it, read the results
- Fill in the
Dijkstramethods: the two blocked methods as inBFS, the three slow ones from your WEIGHTED GRAPH functions withself.slow_edgesin place ofSLOW_EDGES, andcompute_path()from your Lesson 6-3 body with the twoself.changes in its comment. Deleteplanner = BFS(). - Give
ManhattanandBFSthe two methods that do nothing. - Write
slow()and make the three harness edits. Then the tests, the usual way:test_three_planners()hands inManhattan(),BFS()andDijkstra();test_cost_grid()saysslow(planner, ...)and drawsplanner.blocked;dijkstra_distances()readsplanner.blockedandplanner.weight(). Set the run line totest_three_planners().
Expected, on the slow grid:
=== Manhattan === blocked cases FAIL, cost FAIL 4 of 7
=== BFS === blocked cases PASS, cost FAIL 6 of 7
=== Dijkstra === everything PASS 7 of 7
Each planner fails exactly the tests that describe what it cannot do, and the harness that showed you that is the one you wrote in Lesson 5-6, with one case added.
- Last, the swap on the floor. In
test_drive_slow_grid(),PLANNER_NAMEnow chooses an object —planner = Dijkstra()orplanner = BFS()— which is told the slow segment withslow(planner, ...)and asked for the path withplanner.compute_path(). With theNavigatorclass, the drive isnavigator.drive_path(path). Run both planners as in Lesson 6-4: same test program, and the only line that changes is the class name.
Wrap-up
- What does
Dijkstraadd toBFS? (A slow list with three methods, and the two changes.) - Why can one harness test three classes? (They answer to the same method names.)
- What is that called? (Polymorphism.)