01 — the shape
Who imports whom
The architecture is legible from the import statements alone. Only one module imports anything else from the lab.
solver.py.Read in reverse, the graph gives the layering. python/maze.py describes a world. python/pqueue.py and python/pstack.py describe two disciplines for holding a collection of items. Neither is aware of the other, and neither is aware of what a search is. python/solver.py is the only file that refers to all of them, and the only one that had to change when the stack was moved into a module of its own.
02 — layer one
The graph knows nothing about search
maze.py answers exactly one question: given a cell, which cells are one step away?
def neighbors(self, pos):
"""Yield the walkable cells orthogonally adjacent to `pos`."""
r, c = pos
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
npos = (r + dr, c + dc)
if self.is_free(npos):
yield npos
Three places the agnosticism is visible
- No frontier state in the constructor.
__init__storesgrid,height,width,start,end— and nothing else. No queue, no stack, no visited set, no parent map. All of that is the search's bookkeeping and none of it lives here. neighborsreports adjacency, not order. It returns every walkable neighbour and leaves the caller to sequence them. It is a generator, so a caller that stops early incurs no further cost.is_freeis a pure predicate. It returns the same answer for a cell regardless of how that cell was reached, or whether a search is under way at all. The bounds check precedes the index, so a negative coordinate is rejected rather than wrapping silently to the far side of the grid.
That is the entire boundary. The maze is a graph, and a graph prescribes no traversal order.
03 — layer two
The algorithm, written once
search in solver.py never mentions a queue or a stack. It refers only to ops.
frontier = ops.put(ops.empty, mz.start) parent = {mz.start: None} versions = [frontier] while not ops.is_empty(frontier): pos, frontier = ops.take(frontier) if pos == mz.end: # walk `parent` backwards to build the path ... for npos in mz.neighbors(pos): if npos not in parent: parent[npos] = pos frontier = ops.put(frontier, npos) versions.append(frontier)
empty, put, take, is_empty. Nothing further about the container is assumed: neither its representation, nor its cost, nor its ordering.Note what take returns: a value and a new frontier. Nothing is mutated in place. That signature is not a stylistic preference; it is what allows the solver to retain versions, a list of every frontier the search has held, without copying. Why that matters is the subject of §04 of the session page.
The parent dictionary serves two purposes at once — visited set and path reconstruction: a cell is enqueued only if it has no parent recorded, and the path is recovered by following parents backwards from the exit.
04 — layer three
Two containers, same interface
Both are cons-lists — None is empty, (head, tail) is a node. Both are persistent: every operation returns a new structure, and no earlier version is ever destroyed. Only one of the two is difficult to implement.
pqueue.py — FIFO
Two cons-lists, (front, back). Take from the head of front, push onto the head of back. Four TODOs remain to be completed.
q = (front, back) # contents = front ++ reverse(back) # invariant: front empty ⟹ back empty enqueue(q, x) # O(1) dequeue(q) # amortized O(1)
Here persistence must be earned. When front is exhausted, _make reverses the whole of back — an O(n) step. The banker's argument establishes that each element pays for its own reversal exactly once, so n operations still cost O(n) in total.
pstack.py — LIFO
A single cons-list. Take from the head, push onto the head. No TODOs; supplied in full.
s = (head, tail) # contents = the list itself # invariant: none needed push(s, x) # O(1), shares all of s pop(s) # O(1), allocates nothing
Here persistence is free. push conses a single node in front of the old stack and shares all of it; pop returns a tail that already exists. There is no rebalancing step anywhere, so there is nothing to amortise.
pqueue._make, and pstack.py is there to show what its absence looks like.05 — the wiring
A frontier is five functions
There is no base class, no ABC, no Protocol. A frontier is a namespace holding five names, and the two modules supply them.
| ops.name | queue_frontier → BFS | stack_frontier → DFS |
|---|---|---|
| empty | P.EMPTY | S.EMPTY |
| put | P.enqueue | S.push |
| take | P.dequeue | S.pop |
| is_empty | P.is_empty | S.is_empty |
| to_list | P.to_list | S.to_list |
# FIFO frontier: the persistent queue of pqueue.py (Part A). queue_frontier = SimpleNamespace( name="BFS (queue frontier)", empty=P.EMPTY, put=P.enqueue, take=P.dequeue, is_empty=P.is_empty, to_list=P.to_list, ) # LIFO frontier: the persistent stack from the lecture (pstack.py, provided). stack_frontier = SimpleNamespace( name="DFS (stack frontier)", empty=S.EMPTY, put=S.push, take=S.pop, is_empty=S.is_empty, to_list=S.to_list, )
# No flag means --bfs: the default frontier is the one under construction. ops = stack_frontier if "dfs" in flags else queue_frontier
The single point of difference. put followed by take returns the oldest element on the queue and the newest on the stack. That one difference is what makes the same loop either expand in rings from the start — breadth-first, with a guaranteed shortest path — or descend a single corridor until it dead-ends — depth-first, returning the first path found.
The maze never learns which occurred. search never asks.
Both searches run side by side, one step at a time, in §03 of the session page.
06 — run it
From the python/ directory
--bfs is the default, and until the four TODOs in pqueue.py are completed it reports this plainly rather than failing: solver.py catches the NotImplementedError and directs the reader back to the file in question. Full lab instructions are in README.md.