Tutorial 62026-08-20

Four Questions, One Search

Three-hour Python session · no new algorithm · the same six lines answering four different questions, then recursion, then what the memory slots are actually doing

Mission

Finish line: Nothing new is invented today. You already wrote the search last week. Today you point it at four different questions, then discover that recursion has been that same search all along.

Teacher provides

The map, the colours, the animated views, a live speed test, and the build checks.

Student builds

Six small functions. Five of them are the loop you already know, written again.

Not this week

No weights, no directed edges, no new algorithm. Consolidation only.

Three-Hour Route

00:00-00:12

The one skeleton, from memory

Close the laptop. Write the six lines on paper. Everything today is this, four times.

00:12-00:40

Question 1 and 2

Fill one room, then run the same call again and again to count every room.

00:40-01:05

Question 3 and 4

BFS gives every cell a distance, not just the goal. Then start from three doors at once.

01:05-01:20

TODO 1-5

Five small functions, all the same loop. Run each checkpoint before moving on.

01:20-01:30

Break

Leave the distance map on screen.

01:30-02:05

Recursion

countdown(3) on paper first. Then see that calling a function IS pushing onto a stack.

02:05-02:25

TODO 6, and the proof

Write visit(). Then run [6] and read the line that says the two orders match cell for cell.

02:25-02:50

Why a list is a bad queue

Run [7] on their own laptop. The numbers are measured there and then, not quoted.

02:50-03:00

One upgrade

Pick one and name the single function it touches before writing anything.

Part 1 — The Skeleton You Already Know

One sentence: Keep a to-do list. Take one out. Add the neighbours you have not seen. That is the entire algorithm, and every question below is just a different thing to write down along the way.

python

frontier = [ ...where we start... ]seen     = { ...the same cells... }while len(frontier) > 0:    current = take one out of frontier    for step in neighbors(grid, current):        if step not in seen:            seen[step] = True            frontier.append(step)

Which cells are in this room?

Start from one cell. Collect everything the search reaches.

How many separate rooms?

Run question 1 again from every cell nobody has claimed yet.

How far is every cell from here?

Record a number as you go, instead of just a tick.

How far from the NEAREST door?

Exactly the same code. Just put three cells in the frontier to begin with.

Part 2 — Question 1: One Room

Switch between BFS and DFS with the buttons. The colour spreads in a completely different shape — and both stop with exactly the same 114 cells filled. The frontier decides the ORDER you visit in. It never decides WHICH cells you can reach.

question 1

Which cells are in this room?

1 / 114

Taking the oldest cell waiting.

Part 3 — Question 2: How Many Rooms

Question 1 answers 'everything joined to THIS cell'. To count every room, run it again from any cell nobody has claimed yet. Each colour below is one call to the same function.

question 2

How many separate rooms?

1 / 5

Room 1: this one call to flood() has claimed 1 cells.

Five rooms: one big one of 114 cells, one of 5, and three sealed closets of 2. A closet nobody can walk into is still a room — the search simply never reaches it from outside.

Part 4 — Question 3: How Far Is Everything

Last week BFS stopped when it hit the goal. If you let it run to the end instead, it hands you the distance to EVERY cell. Notice how each ring lights up all at once — that is what makes the numbers correct.

question 3

How far is every cell from the start?

0 / 37

Ring 0: every cell here is exactly 0 steps from the start.

This one really does have to be a queue. Swap pop(0) for pop() and the cells still all get a number, but the numbers are wrong: a stack wanders down a long path first and writes that length in.

Part 5 — Question 4: Nearest Door

Here is the part worth pausing on: this uses the SAME function as question 3. Not a similar one. The same one. The only difference is that the frontier starts with three cells in it instead of one.

question 4

How far is every cell from the nearest door?

0 / 12

Ring 0: every cell here is 0 steps from its nearest door.

distance_map(grid, [start])

farthest cell: 37 steps away

distance_map(grid, doors)

farthest cell: 12 steps away

Part 6 — Recursion Is The Same Stack

One sentence: Recursive DFS does not get rid of the stack. It just stops making you write it down — Python keeps one for every running function, and that is the frontier.

python

# You write the stack down yourselfdef flood(grid, start):    frontier = [start]    seen = {start: True}    while len(frontier) > 0:        current = frontier.pop()        for step in neighbors(grid, current):            if step not in seen:                seen[step] = True                frontier.append(step)# Python writes it down for youdef visit(grid, cell, seen):    seen[cell] = True    for step in neighbors(grid, cell):        if step not in seen:            visit(grid, step, seen)      # <-- this line IS frontier.append

The stack you write	The stack Python keeps
frontier.append(next)	calling visit(next) — Python pushes a frame
frontier.pop()	the function returns — Python pops the frame
len(frontier)	how deep the calls are nested right now
while len(frontier) > 0	the program keeps running until the last call returns
the list grows as big as you like	about 1000 frames, then RecursionError

Watch both columns at once

Step through it. The left column is Python's call stack. The right column is a stack written out by hand. They hold the same cells, in the same order, at every single step.

no frontier list anywhere

Recursion IS the stack

the map

Python's call stack

visit(1,1)

a stack you write yourself

1,22,1

visit(1,1) — Calling a function PUSHES a frame. The stack is now 1 deep.

visited

1/12

frames now

deepest

step through and compare the two columns

Two small details make them match exactly. Push the neighbours BACKWARDS, so the first one comes off the top first. And mark a cell seen when you TAKE IT OUT, not when you put it in — because a recursive call only marks a cell once it actually enters it. Change either detail and the cells stay the same but the order shifts.

There is one real difference, and it is not about correctness. Python allows about 1000 nested calls and then raises RecursionError. A 30x30 open room needs 900 and just survives; a 40x40 room needs 1600 and crashes. The stack you write yourself has no such ceiling — it happily goes 19,901 deep on a 200x200 room.

Practice

Warm-Up 16 min

Watch the stack grow and shrink

Nine printed lines. Work them out first, then read the sample and say why it is symmetric.

python

def countdown(n):    print("enter", n)    if n == 0:        print("bottom")    else:        countdown(n - 1)    print("leave", n)countdown(3)

Sample output

enter 3
enter 2
enter 1
enter 0
bottom
leave 0
leave 1
leave 2
leave 3

This is exactly what the finished program prints. Match it line for line.

Hint 1

Nothing after the call runs until the call has finished.

Hint 2

The leaves come out backwards. That is a stack, and you did not write one.

Warm-Up 26 min

Add up a list without a loop

Every recursion needs a case that stops. Here it is an empty tail.

python

def total(numbers, index=0):    # TODO    passprint(total([4, 7, 2]))print(total([]))

Sample output

13
0

This is exactly what the finished program prints. Match it line for line.

Hint 1

Write the stopping case first, or the calls never end.

Hint 2

4 + total([7,2]) becomes 4 + 7 + total([2]) becomes 4 + 7 + 2 + 0.

Warm-Up 37 min

Recursive DFS on four nodes

There is no frontier list here. Mark the node, record it, then step into each unseen neighbour.

python

links = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}seen = {}order = []def visit(node):    # TODO    passvisit("A")print(order)

Sample output

['A', 'B', 'D', 'C']

This is exactly what the finished program prints. Match it line for line.

Hint 1

Mark the node seen the moment you enter it, before looking at neighbours.

Hint 2

A goes into B, B goes into D, D has nowhere to go, so we come back up and take C.

Warm-Up 47 min

The same answer, with a stack you wrote

This is Warm-Up 3 with the stack made visible. Compare the two outputs and say what is going on.

python

links = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}stack = ["A"]seen = {}order = []while len(stack) > 0:    current = stack.pop()    if current in seen:        continue    seen[current] = True    order.append(current)    kids = links[current]    for i in range(len(kids) - 1, -1, -1):        if kids[i] not in seen:            stack.append(kids[i])print(order)

Sample output

['A', 'B', 'D', 'C']

This is exactly what the finished program prints. Match it line for line.

Hint 1

Two details make it match: push neighbours backwards, and mark seen on the way out.

Hint 2

Change either detail and the order shifts, even though the cells stay the same.

Part 7 — Why A Queue Needs A deque

One sentence: A Python list is one unbroken run of slots. Touching the end is free. Touching the front makes everything else shuffle along.

what the slots actually do

A list is a great stack and a poor queue

waiting = ['A', 'B', 'C', 'D', 'E']

one continuous block of slots

1/10A list is one unbroken block

Python asks the operating system for one continuous run of slots, side by side in memory. Slot 0 first, then slot 1, and so on. Nothing is allowed to leave a hole in the middle.

Measured, emptying from the front

items	list.pop(0)	deque.popleft()	slower by
10,000	3.9 ms	0.2 ms	19x
40,000	88.8 ms	0.9 ms	104x
160,000	1653 ms	3.9 ms	423x

Four times the items, sixteen times the work. Taking from the back is identical for both, so this only ever bites a queue.

But does it matter in YOUR search?

A grid mazefrontier stays short (one ring, ~400)list is fine — 1.1x

One node joined to 40,000 othersfrontier grows to 40,000list is 31x slower

The cost of pop(0) depends on how long the frontier is right now, not on the size of the whole graph. A grid keeps it short, so a list survives. Reach for a deque anyway — it is one import and you never have to think about it again.

python

stack = []                      # a list is already a perfect stackstack.append(cell)              # writes one slot at the endstack.pop()                     # reads one slot at the endfrom collections import deque   # a queue needs one importqueue = deque()queue.append(cell)              # one slot at the backqueue.popleft()                 # moves a marker, shifts nothing

Be honest about when it bites. The cost of pop(0) depends on how long the frontier is AT THAT MOMENT, not on the size of the whole graph. On a grid the frontier is one thin ring, so a list is only about 1.1x slower and you would never notice. On a graph where one node touches forty thousand others, the frontier balloons and the list is 31x slower. Use a deque anyway: it is one import, and then the question never comes up again.

Practice

Warm-Up 55 min

Both ends of a list

Four printed lines. Then answer: which of the two pops had to move other items?

python

waiting = ["A", "B", "C", "D"]print(waiting.pop())print(waiting)print(waiting.pop(0))print(waiting)

Sample output

D
['A', 'B', 'C']
A
['B', 'C']

This is exactly what the finished program prints. Match it line for line.

Hint 1

Both give the right answer. Only one of them is cheap.

Hint 2

pop(0) on a list of 100 items has to move 99 of them.

Warm-Up 66 min

Turn a slow queue into a fast one

This BFS is correct but uses a list as a queue. Rewrite it with a deque. The output must not change.

python

links = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}queue = ["A"]seen = {"A": True}order = []while len(queue) > 0:    current = queue.pop(0)        # TODO: make this O(1)    order.append(current)    for nxt in links[current]:        if nxt not in seen:            seen[nxt] = True            queue.append(nxt)print(order)

Sample output

['A', 'B', 'C', 'D']

This is exactly what the finished program prints. Match it line for line.

Hint 1

append() is spelled the same on a deque. Only pop(0) becomes popleft().

Hint 2

Leave a stack alone. A list is already the right tool for pop().

In The Terminal

A real frame from the finished program: question 4, every cell labelled with its distance to the nearest door. In a real terminal each cell is a solid 24-bit colour and the rings light up one after another.

terminal

+----------------------------------------------------------------------------+|         QUESTION 4 - HOW FAR IS EVERY CELL FROM THE NEAREST DOOR?          ||                        3 sources, all starting at 0                        |+----------------------------------------------------------------------------+|                                                                            ||                  ########################################                  ||                  ## D 1 2 3 4 5 6 7## 8 7 6 5 4 3 2 1 D##                  ||                  ## 1 2######## 7 8## 9 8 7######## 2 1##                  ||                  ## 2 3## . .## 8 9##10 9 8## . .## 3 2##                  ||                  ## 3 4######## 910##1110 9######## 4 3##                  ||                  ## 4 5 6 7 8 91011##121110 9 8 7 6 5 4##                  ||                  ## 5 6############################## 5##                  ||                  ## 6 7 8 9 9 8 91011121110 9 8 9 8 7 6##                  ||                  ## 7######## 7############## 7###### 7##                  ||                  ## 8## . .## 6## . . . . .## 6##10 9 8##                  ||                  ## 9######## 5############## 5###### 9##                  ||                  ## 9 8 7 6 5 4 3 2 1 D 1 2 3 4 5 6 7 8##                  ||                  ########################################                  ||                                                                            |+----------------------------------------------------------------------------+| farthest cell (9, 9) at distance 12                                        || reached 114/125 floor cells     unreachable 11                             |+----------------------------------------------------------------------------+

Start it

bash

python3 room_survey.py# The build check runs first. The map only opens after TODO 1-6 pass.#  [1]  Question 1  -  fill one room, with a QUEUE#  [2]  Question 1  -  fill the same room, with a STACK#  [3]  Question 2  -  colour every separate room#  [4]  Question 3  -  distance from the start#  [5]  Question 4  -  distance to the nearest door#  [6]  Recursive DFS  -  the same walk, with no frontier list#  [7]  Why a list is a fine stack but a bad queue  (timed live, on your machine)#  [8]  The numbers#  [q]  Quit

Option [7] is not a table copied from somewhere. It times list.pop(0) against deque.popleft() on your own machine, right then, and prints what it found.

01Choose [1], then [2]. The colour spreads differently, but the same cells end up filled: 114.

02Choose [3]. Count the colours: five rooms. Three of them are sealed closets nobody can walk into.

03Choose [4]. Every ring appears at once, because every cell in a ring is the same distance away.

04Choose [5]. Three zeros this time. Watch the three waves meet in the middle.

05Choose [6]. Read the line that compares recursion with the hand-written stack. It must say YES.

06Choose [7] on your own laptop. The timings are measured right there, not copied from a book.

07Break it: in distance_map, change pop(0) to pop(). A build check will catch you.

08Break it again: in visit(), mark seen AFTER the loop instead of before. Watch it never finish.

TODO Contract

Six functions. Five of them are the same loop with a different thing recorded along the way. Finish one at a time and run its checkpoint.

TODO 1Phase 1 - Reading the map

neighbors

Purpose

The same helper as last week. Everything else is built on it.

Input

grid: list[str], cell: a pair (row, col)

Output / Return

The floor cells up, down, left and right, in DIRECTIONS order.

State change

Nothing.

Checkpoint

python

print(neighbors(FLOOR_MAP, (1, 1)))    # [(2, 1), (1, 2)]print(neighbors(FLOOR_MAP, (1, 2)))    # [(1, 1), (1, 3)]

TODO 2Phase 2 - The four questions

flood

Purpose

Question 1: which cells are joined to this one?

Input

grid; start, a pair; mode, "bfs" or "dfs"

Output / Return

Every reachable cell, in the order you took them out.

State change

Nothing. "bfs" pops the front, "dfs" pops the back.

Checkpoint

python

bfs_cells = flood(FLOOR_MAP, START, "bfs")dfs_cells = flood(FLOOR_MAP, START, "dfs")print(len(bfs_cells), len(dfs_cells))          # 114 114print(sorted(bfs_cells) == sorted(dfs_cells))  # True

TODO 3Phase 2 - The four questions

count_rooms

Purpose

Question 2: how many separate rooms does the map have?

Input

grid

Output / Return

A list of rooms, each one the list flood() returned.

State change

Nothing. Skip a cell an earlier room already claimed.

Checkpoint

python

rooms = count_rooms(FLOOR_MAP)print(len(rooms))                                 # 5print(sorted((len(r) for r in rooms), reverse=True))# [114, 5, 2, 2, 2]

TODO 4Phase 2 - The four questions

distance_map

Purpose

Questions 3 and 4 at once. One source or many, same code.

Input

grid; sources, a LIST of starting cells

Output / Return

A dict, cell -> how many steps away it is.

State change

Nothing. This must be a queue. A stack gives wrong distances.

Checkpoint

python

one = distance_map(FLOOR_MAP, [START])many = distance_map(FLOOR_MAP, DOORS)print(one[START], len(one))                   # 0 114print(one[farthest_cell(one)])                # 37print(many[farthest_cell(many)])              # 12

TODO 5Phase 2 - The four questions

farthest_cell

Purpose

Find the most awkward corner of the building.

Input

distance, the dict distance_map() returned

Output / Return

The cell with the largest distance; on a tie the smallest pair.

State change

Nothing.

Checkpoint

python

print(farthest_cell({(0, 0): 0, (5, 5): 4, (2, 2): 4}))   # (2, 2)one = distance_map(FLOOR_MAP, [START])print(farthest_cell(one), one[farthest_cell(one)])        # (1, 10) 37

TODO 6Phase 3 - Recursion

visit (recursive DFS)

Purpose

The same walk as flood(..., "dfs"), with no frontier list at all.

Input

grid; cell, the pair you are standing on; seen and order, shared records

Output / Return

No return value.

State change

Mark cell seen, append it to order, then visit each unseen neighbour.

Checkpoint

python

cells = flood_recursive(FLOOR_MAP, START)print(len(cells))                                            # 114print(sorted(cells) == sorted(flood(FLOOR_MAP, START)))      # Trueprint(cells == flood_like_recursion(FLOOR_MAP, START))       # True

Student Work Area

Only edit this part: All six TODOs live here. Read the comment at the top before anything else — it is the whole lesson in nine lines.

student_work.py

python

# ================================================================# ONE SKELETON, FOUR QUESTIONS## Last week you wrote this loop once, to find a path.# This week you write it again, and it answers three more questions# without changing shape at all:##     frontier = [ ...where we start... ]#     seen     = { ...the same cells... }#     while len(frontier) > 0:#         current = take one out of frontier#         look at every neighbour that is NOT in seen#         put it in seen, and add it to frontier# ================================================================def neighbors(grid, cell):    # TODO 1    # Input: grid, a list of strings; cell, a pair (row, col)    # Return: a list of the floor cells directly up, down, left and right    #         Keep DIRECTIONS order. '#' is a wall. Nothing outside the grid.    # Change: nothing    return []def flood(grid, start, mode="bfs"):    # TODO 2  -  QUESTION 1: which cells are in the same room as start?    # Input: grid; start, a pair; mode, "bfs" or "dfs"    # Return: a list of every reachable cell, in the order you took them out    # Change: nothing    #    # "bfs" takes frontier.pop(0), "dfs" takes frontier.pop().    # Both answers contain the SAME cells - only the order differs.    return []def count_rooms(grid):    # TODO 3  -  QUESTION 2: how many separate rooms does the map have?    # Input: grid    # Return: a list of rooms; each room is the list flood() gave back    # Change: nothing    #    # Walk over all_floor(grid). Skip a cell if an earlier room already    # contains it. Otherwise flood from it - that is one whole new room.    return []def distance_map(grid, sources):    # TODO 4  -  QUESTION 3 AND 4: how far is every cell from the sources?    # Input: grid; sources, a LIST of starting cells    # Return: a dict, cell -> how many steps away it is    # Change: nothing    #    # This must be BFS. A stack would give wrong distances.    # One source answers "how far from here".    # Several sources answer "how far from the NEAREST one" - same code.    return {}def farthest_cell(distance):    # TODO 5    # Input: distance, the dict distance_map() gave back    # Return: the cell with the largest distance.    #         If several tie, return the smallest pair, so the answer is stable.    # Change: nothing    return Nonedef flood_recursive(grid, start):    # Provided. It only sets up the two records and starts the first call.    seen = {}    order = []    visit(grid, start, seen, order)    return orderdef visit(grid, cell, seen, order):    # TODO 6  -  the SAME depth-first search, with no frontier list at all    # Input: grid; cell, the pair we are standing on; seen and order, shared records    # Return: nothing    # Change: mark cell as seen, append it to order,    #         then visit every neighbour that is not in seen yet    #    # There is no frontier here. Python keeps the stack for you:    # calling visit() pushes a frame, returning from it pops the frame.    pass

Project Template

Copy this whole file once so the map can run. During class, work in the Student Work Area above and search by TODO number.

room_survey.py

python

import reimport sysfrom time import sleepESC = chr(27) + "["RESET = f"{ESC}0m"USE_COLOR = sys.stdout.isatty()ANIMATE = sys.stdout.isatty()ANSI_RE = re.compile(re.escape(ESC) + r"[0-9;]*m")# '#' is a wall. Everything else is floor you can stand on.FLOOR_MAP = [    "####################",    "#........#.........#",    "#..####..#...####..#",    "#..#..#..#...#..#..#",    "#..####..#...####..#",    "#........#.........#",    "#..###############.#",    "#..................#",    "#.####.#######.###.#",    "#.#..#.#.....#.#...#",    "#.####.#######.###.#",    "#..................#",    "####################",]# up, down, left, rightDIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]START = (1, 1)DOORS = [(1, 1), (1, 18), (11, 10)]def rgb_bg(text, red, green, blue, fr=230, fg=235, fb=245):    if not USE_COLOR:        return str(text)    return (        f"{ESC}48;2;{red};{green};{blue}m{ESC}38;2;{fr};{fg};{fb}m{text}{RESET}"    )def rgb(text, red, green, blue, bold=False):    if not USE_COLOR:        return str(text)    weight = "1;" if bold else ""    return f"{ESC}{weight}38;2;{red};{green};{blue}m{text}{RESET}"def dim(text):    if not USE_COLOR:        return str(text)    return f"{ESC}2m{text}{RESET}"def gradient_text(text, start=(120, 235, 255), end=(200, 120, 255)):    if not USE_COLOR or len(text) <= 1:        return str(text)    out = ""    steps = len(text) - 1    for index, character in enumerate(text):        ratio = index / steps        out += rgb(            character,            round(start[0] + (end[0] - start[0]) * ratio),            round(start[1] + (end[1] - start[1]) * ratio),            round(start[2] + (end[2] - start[2]) * ratio),        )    return outdef visible_len(text):    return len(ANSI_RE.sub("", str(text)))def pad_visible(text, width):    return str(text) + " " * max(0, width - visible_len(text))def center_visible(text, width):    spaces = max(0, width - visible_len(text))    left = spaces // 2    return " " * left + str(text) + " " * (spaces - left)def clear_screen():    if sys.stdout.isatty():        print(f"{ESC}2J{ESC}H", end="")def hide_cursor():    if sys.stdout.isatty():        print(f"{ESC}?25l", end="")def show_cursor():    if sys.stdout.isatty():        print(f"{ESC}?25h", end="")WALL_BG = (46, 50, 68)FLOOR_BG = (20, 22, 32)# One colour per room, used by the "count the rooms" view.ROOM_COLOURS = [    (72, 190, 255),    (255, 170, 70),    (120, 230, 150),    (240, 110, 190),    (200, 150, 255),    (255, 230, 110),]def heat_colour(value, biggest):    """Blue for near, magenta for far."""    ratio = 0.0 if biggest <= 0 else min(1.0, value / biggest)    red = round(40 + 200 * ratio)    green = round(150 - 90 * ratio)    blue = round(230 - 40 * ratio)    return (red, green, blue)def all_floor(grid):    cells = []    for row in range(len(grid)):        for col in range(len(grid[row])):            if grid[row][col] != "#":                cells.append((row, col))    return cellsTOTAL_FLOOR = len(all_floor(FLOOR_MAP))def blank_paint():    return {}def draw_map(grid, paint, labels=None):    """paint: cell -> (r, g, b). labels: cell -> two characters."""    if labels is None:        labels = {}    lines = []    for row in range(len(grid)):        line = ""        for col in range(len(grid[row])):            cell = (row, col)            if grid[row][col] == "#":                line += rgb_bg("  " if USE_COLOR else "##", *WALL_BG)                continue            text = labels.get(cell, "  ")            if len(text) == 1:                text = text + " "            if cell in paint:                red, green, blue = paint[cell]                line += rgb_bg(text[:2], red, green, blue, 15, 18, 26)            elif text.strip() == "":                line += rgb_bg(" .", *FLOOR_BG, 70, 76, 98)            else:                line += rgb_bg(text[:2], *FLOOR_BG, 150, 160, 190)        lines.append(line)    return lines# ================================================================# ONE SKELETON, FOUR QUESTIONS## Last week you wrote this loop once, to find a path.# This week you write it again, and it answers three more questions# without changing shape at all:##     frontier = [ ...where we start... ]#     seen     = { ...the same cells... }#     while len(frontier) > 0:#         current = take one out of frontier#         look at every neighbour that is NOT in seen#         put it in seen, and add it to frontier# ================================================================def neighbors(grid, cell):    # TODO 1    # Input: grid, a list of strings; cell, a pair (row, col)    # Return: a list of the floor cells directly up, down, left and right    #         Keep DIRECTIONS order. '#' is a wall. Nothing outside the grid.    # Change: nothing    return []def flood(grid, start, mode="bfs"):    # TODO 2  -  QUESTION 1: which cells are in the same room as start?    # Input: grid; start, a pair; mode, "bfs" or "dfs"    # Return: a list of every reachable cell, in the order you took them out    # Change: nothing    #    # "bfs" takes frontier.pop(0), "dfs" takes frontier.pop().    # Both answers contain the SAME cells - only the order differs.    return []def count_rooms(grid):    # TODO 3  -  QUESTION 2: how many separate rooms does the map have?    # Input: grid    # Return: a list of rooms; each room is the list flood() gave back    # Change: nothing    #    # Walk over all_floor(grid). Skip a cell if an earlier room already    # contains it. Otherwise flood from it - that is one whole new room.    return []def distance_map(grid, sources):    # TODO 4  -  QUESTION 3 AND 4: how far is every cell from the sources?    # Input: grid; sources, a LIST of starting cells    # Return: a dict, cell -> how many steps away it is    # Change: nothing    #    # This must be BFS. A stack would give wrong distances.    # One source answers "how far from here".    # Several sources answer "how far from the NEAREST one" - same code.    return {}def farthest_cell(distance):    # TODO 5    # Input: distance, the dict distance_map() gave back    # Return: the cell with the largest distance.    #         If several tie, return the smallest pair, so the answer is stable.    # Change: nothing    return Nonedef flood_recursive(grid, start):    # Provided. It only sets up the two records and starts the first call.    seen = {}    order = []    visit(grid, start, seen, order)    return orderdef visit(grid, cell, seen, order):    # TODO 6  -  the SAME depth-first search, with no frontier list at all    # Input: grid; cell, the pair we are standing on; seen and order, shared records    # Return: nothing    # Change: mark cell as seen, append it to order,    #         then visit every neighbour that is not in seen yet    #    # There is no frontier here. Python keeps the stack for you:    # calling visit() pushes a frame, returning from it pops the frame.    passWIDTH = 78INSIDE = WIDTH - 4MAP_WIDTH = len(FLOOR_MAP[0]) * 2def rule():    return "+" + "-" * (WIDTH - 2) + "+"def row(text):    return "| " + pad_visible(text, INSIDE) + " |"def centered(text):    return "| " + center_visible(text, INSIDE) + " |"def panel(title, subtitle, map_lines, footer):    lines = [rule(), centered(gradient_text(title))]    if subtitle:        lines.append(centered(dim(subtitle)))    lines.append(rule())    lines.append(row(""))    for line in map_lines:        lines.append(centered(line))    lines.append(row(""))    lines.append(rule())    for line in footer:        lines.append(row(line))    lines.append(rule())    print("\n".join(lines))def show(title, subtitle, paint, labels, footer, delay=0.0):    clear_screen()    panel(title, subtitle, draw_map(FLOOR_MAP, paint, labels), footer)    if ANIMATE and delay > 0:        sleep(delay)# ---------------------------------------------------------------- 1def view_flood(mode):    order = flood(FLOOR_MAP, START, mode)    colour = (72, 190, 255) if mode == "bfs" else (255, 170, 70)    name = "QUEUE (BFS)" if mode == "bfs" else "STACK (DFS)"    hide_cursor()    try:        paint = {}        for index, cell in enumerate(order):            paint[cell] = colour            show(                "QUESTION 1 - WHICH CELLS ARE IN THIS ROOM?",                f"flood from {START} using a {name}",                dict(paint),                {cell: "()"},                [                    f"filled {index + 1}/{len(order)} cells"                    f"     room size {len(order)}"                    f"     map has {TOTAL_FLOOR} floor cells",                    dim("Both bfs and dfs end with exactly the same cells filled."),                ],                0.02,            )    finally:        show_cursor()    return order# ---------------------------------------------------------------- 2def view_rooms():    rooms = count_rooms(FLOOR_MAP)    hide_cursor()    try:        paint = {}        for index, room in enumerate(rooms):            colour = ROOM_COLOURS[index % len(ROOM_COLOURS)]            for cell in room:                paint[cell] = colour                show(                    "QUESTION 2 - HOW MANY SEPARATE ROOMS?",                    "run the same flood again from every cell nobody has claimed",                    dict(paint),                    {},                    [                        f"room {index + 1} of {len(rooms)}"                        f"     this room has {len(room)} cells",                        dim("Each colour is one call to flood()."),                    ],                    0.012,                )    finally:        show_cursor()    sizes = sorted((len(room) for room in rooms), reverse=True)    show(        "QUESTION 2 - HOW MANY SEPARATE ROOMS?",        "one colour per room",        {cell: ROOM_COLOURS[i % len(ROOM_COLOURS)] for i, r in enumerate(rooms) for cell in r},        {},        [            rgb(f"{len(rooms)} rooms", 120, 235, 255, bold=True)            + f"     sizes {sizes}",            dim("A sealed closet is still a room. It just has nobody to talk to."),        ],    )    return rooms# ---------------------------------------------------------------- 3 and 4def view_distance(sources, title, subtitle):    distance = distance_map(FLOOR_MAP, sources)    biggest = max(distance.values())    # Reveal the map one ring at a time, which is what BFS actually does.    hide_cursor()    try:        for ring in range(biggest + 1):            paint, labels = {}, {}            for cell in distance:                if distance[cell] <= ring:                    paint[cell] = heat_colour(distance[cell], biggest)                    labels[cell] = str(distance[cell]).rjust(2)            for source in sources:                labels[source] = " S"            show(                title,                subtitle,                paint,                labels,                [                    f"ring {ring}/{biggest}"                    f"     cells reached {len(paint)}/{TOTAL_FLOOR}",                    dim("Every cell in one ring is the same number of steps away."),                ],                0.09,            )    finally:        show_cursor()    far = farthest_cell(distance)    paint = {cell: heat_colour(distance[cell], biggest) for cell in distance}    labels = {cell: str(distance[cell]).rjust(2) for cell in distance}    for source in sources:        labels[source] = " S"    labels[far] = " X"    show(        title,        subtitle,        paint,        labels,        [            rgb(f"farthest cell {far} at distance {distance[far]}", 255, 210, 90, bold=True),            f"reached {len(distance)}/{TOTAL_FLOOR} floor cells"            f"     unreachable {TOTAL_FLOOR - len(distance)}",            dim("X marks the farthest cell. S marks every source."),        ],    )    return distance# ---------------------------------------------------------------- 5def view_numbers():    rooms = count_rooms(FLOOR_MAP)    one = distance_map(FLOOR_MAP, [START])    many = distance_map(FLOOR_MAP, DOORS)    bfs_order = flood(FLOOR_MAP, START, "bfs")    dfs_order = flood(FLOOR_MAP, START, "dfs")    clear_screen()    lines = [        rule(),        centered(gradient_text("THE NUMBERS")),        rule(),        row(""),        row(f"{'floor cells on the map':<38}{TOTAL_FLOOR:>8}"),        row(f"{'separate rooms':<38}{len(rooms):>8}"),        row(f"{'biggest room':<38}{max(len(r) for r in rooms):>8}"),        row(""),        row(f"{'flood() with bfs, cells filled':<38}{len(bfs_order):>8}"),        row(f"{'flood() with dfs, cells filled':<38}{len(dfs_order):>8}"),        row(dim("   same count - the ORDER differs, the ANSWER does not")),        row(""),        row(f"{'farthest cell from the start':<38}{one[farthest_cell(one)]:>8}"),        row(f"{'farthest cell from any door':<38}{many[farthest_cell(many)]:>8}"),        row(dim("   more doors means nowhere is very far away")),        row(""),        rule(),        row("Same loop, four questions. Only the starting frontier and the"),        row("thing you record along the way ever change."),        rule(),    ]    print("\n".join(lines))def flood_like_recursion(grid, start):    """The explicit-stack version that matches recursion EXACTLY.    Two details make it match, and both are worth saying out loud:      1. neighbours go on the stack BACKWARDS, so the first one comes off first      2. a cell is marked seen when it is TAKEN OUT, not when it is put in,         because a recursive call only marks a cell once it actually enters it    """    frontier = [start]    seen = {}    order = []    while len(frontier) > 0:        current = frontier.pop()        if current in seen:            continue        seen[current] = True        order.append(current)        steps = neighbors(grid, current)        for index in range(len(steps) - 1, -1, -1):            if steps[index] not in seen:                frontier.append(steps[index])    return orderdef call_depths(grid, start):    """How deep the recursion is when each cell is first reached."""    seen = {start: True}    depth = {start: 1}    frontier = [start]    order = [start]    while frontier:        current = frontier.pop()        steps = neighbors(grid, current)        for index in range(len(steps) - 1, -1, -1):            step = steps[index]            if step not in seen:                seen[step] = True                depth[step] = depth[current] + 1                frontier.append(step)                order.append(step)    return depth# ---------------------------------------------------------------- 6def view_recursion():    order = flood_recursive(FLOOR_MAP, START)    depth = call_depths(FLOOR_MAP, START)    deepest = max(depth.values())    hide_cursor()    try:        paint = {}        for index, cell in enumerate(order):            level = depth.get(cell, 1)            ratio = level / deepest            paint[cell] = (                round(90 + 150 * ratio),                round(210 - 120 * ratio),                round(255 - 60 * ratio),            )            show(                "RECURSIVE DFS - PYTHON HOLDS THE STACK FOR YOU",                "no frontier list anywhere in this code",                dict(paint),                {cell: "()"},                [                    f"visited {index + 1}/{len(order)}"                    f"     call depth here {level}"                    f"     deepest so far {max(depth[c] for c in order[:index + 1])}",                    dim("Colour shows how many visit() frames are stacked up right now."),                ],                0.02,            )    finally:        show_cursor()    same = flood_like_recursion(FLOOR_MAP, START)    show(        "RECURSIVE DFS - PYTHON HOLDS THE STACK FOR YOU",        "deepest call: " + str(deepest),        {c: (round(90 + 150 * depth[c] / deepest),             round(210 - 120 * depth[c] / deepest),             round(255 - 60 * depth[c] / deepest)) for c in depth},        {},        [            rgb(f"deepest nest of visit() calls: {deepest}", 255, 210, 90, bold=True),            "recursive order == hand-written stack, cell for cell: "            + ("YES" if order == same else "NO"),            dim("Python's default recursion limit is 1000. This map needs "                + str(deepest) + "."),        ],    )# ---------------------------------------------------------------- 7def view_cost():    from collections import deque    from time import perf_counter    clear_screen()    lines = [        rule(),        centered(gradient_text("WHY A LIST IS A FINE STACK BUT A BAD QUEUE")),        rule(),        row(""),        row("Taking from the BACK - both are instant"),        row(f"  {'items':>8} {'list.pop()':>14} {'deque.pop()':>14}"),    ]    for size in (10000, 40000, 160000):        data = list(range(size))        start = perf_counter()        while data:            data.pop()        list_time = perf_counter() - start        ring = deque(range(size))        start = perf_counter()        while ring:            ring.pop()        deque_time = perf_counter() - start        lines.append(row(f"  {size:>8} {list_time * 1000:>12.1f}ms {deque_time * 1000:>12.1f}ms"))    lines.extend([        row(""),        row("Taking from the FRONT - the list has to shuffle everything left"),        row(f"  {'items':>8} {'list.pop(0)':>14} {'deque.popleft()':>16} {'slower by':>11}"),    ])    for size in (10000, 40000, 160000):        data = list(range(size))        start = perf_counter()        while data:            data.pop(0)        list_time = perf_counter() - start        ring = deque(range(size))        start = perf_counter()        while ring:            ring.popleft()        deque_time = perf_counter() - start        lines.append(            row(f"  {size:>8} {list_time * 1000:>12.1f}ms {deque_time * 1000:>14.1f}ms"                f" {rgb(f'{list_time / deque_time:.0f}x', 255, 120, 120, bold=True):>11}")        )    lines.extend([        row(""),        rule(),        row("Double the items and list.pop(0) gets about FOUR times slower."),        row("Double the items and deque.popleft() gets about TWO times slower."),        row(""),        row(dim("pop() and append() only touch the end, so a list is a perfect stack.")),        row(dim("pop(0) moves every remaining item one slot left. Use a deque for queues.")),        rule(),    ])    print("\n".join(lines))# ---------------------------------------------------------------- checksTINY = [    "#####",    "#..##",    "#..##",    "##.##",    "#####",]SPLIT = [    "#######",    "#.#.#.#",    "#.#.#.#",    "#######",]def run_build_checks():    assert neighbors(TINY, (1, 1)) == [(2, 1), (1, 2)], (        "TODO 1 failed: only down and right are open, in DIRECTIONS order."    )    assert neighbors(TINY, (3, 2)) == [(2, 2)], (        "TODO 1 failed: walls and the grid edge must both be rejected."    )    room = flood(TINY, (1, 1))    assert sorted(room) == [(1, 1), (1, 2), (2, 1), (2, 2), (3, 2)], (        "TODO 2 failed: flood must reach every floor cell joined to the start."    )    assert room[0] == (1, 1), "TODO 2 failed: the start is taken out first."    assert len(room) == len(set(room)), "TODO 2 failed: no cell may appear twice."    assert sorted(flood(TINY, (1, 1), "dfs")) == sorted(room), (        "TODO 2 failed: bfs and dfs must fill the SAME cells."    )    rooms = count_rooms(SPLIT)    assert len(rooms) == 3, (        "TODO 3 failed: the small test map has three separate columns."    )    assert sorted(len(r) for r in rooms) == [2, 2, 2], (        "TODO 3 failed: every room in the small test map holds two cells."    )    assert sum(len(r) for r in rooms) == len(all_floor(SPLIT)), (        "TODO 3 failed: every floor cell belongs to exactly one room."    )    assert len(count_rooms(TINY)) == 1, (        "TODO 3 failed: the tiny map is one single room."    )    one = distance_map(TINY, [(1, 1)])    assert one[(1, 1)] == 0, "TODO 4 failed: a source is 0 steps from itself."    assert one[(1, 2)] == 1 and one[(2, 1)] == 1, "TODO 4 failed: check the first ring."    assert one[(2, 2)] == 2 and one[(3, 2)] == 3, (        "TODO 4 failed: count the rings again on the small test map."    )    both = distance_map(TINY, [(1, 1), (3, 2)])    assert both[(3, 2)] == 0 and both[(2, 2)] == 1, (        "TODO 4 failed: with several sources, every source starts at 0."    )    assert len(distance_map(SPLIT, [(1, 1)])) == 2, (        "TODO 4 failed: a search cannot leak into a room it is not joined to."    )    real = distance_map(FLOOR_MAP, [START])    for cell in real:        if cell == START:            assert real[cell] == 0, "TODO 4 failed: the source must be 0."            continue        closest = min(real[n] for n in neighbors(FLOOR_MAP, cell) if n in real)        assert real[cell] == closest + 1, (            "TODO 4 failed: distances are not rings. A stack gives wrong distances."        )    rec = flood_recursive(TINY, (1, 1))    assert sorted(rec) == sorted(room), (        "TODO 6 failed: recursion must reach exactly the same cells."    )    assert rec[0] == (1, 1), "TODO 6 failed: the first cell visited is the start."    assert len(rec) == len(set(rec)), "TODO 6 failed: no cell may be visited twice."    assert rec == flood_like_recursion(TINY, (1, 1)), (        "TODO 6 failed: recursion must match the hand-written stack exactly."    )    assert farthest_cell({(0, 0): 0, (5, 5): 4, (2, 2): 4}) == (2, 2), (        "TODO 5 failed: on a tie, return the smallest pair."    )    assert farthest_cell(one) == (3, 2), (        "TODO 5 failed: check which cell really has the biggest distance."    )MENU = [    "[1]  Question 1  -  fill one room, with a QUEUE",    "[2]  Question 1  -  fill the same room, with a STACK",    "[3]  Question 2  -  colour every separate room",    "[4]  Question 3  -  distance from the start",    "[5]  Question 4  -  distance to the nearest door",    "[6]  Recursive DFS  -  the same walk, with no frontier list",    "[7]  Why a list is a fine stack but a bad queue  (timed here, live)",    "[8]  The numbers",    "[q]  Quit",]def show_menu():    clear_screen()    labels = {START: " S"}    for door in DOORS:        labels[door] = " D"    panel(        "FOUR QUESTIONS, ONE SEARCH",        "the same six lines, asked four different things",        draw_map(FLOOR_MAP, {}, labels),        MENU,    )def wait_for_enter():    try:        input("\nPress Enter to return to the menu: ")    except EOFError:        passdef main():    try:        run_build_checks()    except (AssertionError, AttributeError, TypeError, KeyError, IndexError, ValueError) as error:        detail = str(error) if str(error) else "A required result was incorrect."        print(rule())        print(centered("BUILD CHECK FAILED"))        print(rule())        print(row("Finish TODO 1-5 before the map will open."))        print(row(""))        print(row(detail))        print(row(""))        print(row("Fix one TODO, then run the file again."))        print(rule())        return    actions = {        "1": lambda: view_flood("bfs"),        "2": lambda: view_flood("dfs"),        "3": view_rooms,        "4": lambda: view_distance(            [START],            "QUESTION 3 - HOW FAR IS EVERY CELL FROM THE START?",            f"one source: {START}",        ),        "5": lambda: view_distance(            DOORS,            "QUESTION 4 - HOW FAR IS EVERY CELL FROM THE NEAREST DOOR?",            f"{len(DOORS)} sources, all starting at 0",        ),        "6": view_recursion,        "7": view_cost,        "8": view_numbers,    }    while True:        show_menu()        try:            choice = input("Choose: ").strip().lower()        except EOFError:            return        if choice in ("q", "quit", "exit"):            show_cursor()            return        if choice in actions:            actions[choice]()            wait_for_enter()if __name__ == "__main__":    main()

Build rule: The map only opens after all six build checks pass. One of them checks that your distances really do form rings — a stack instead of a queue fails it immediately.

Optional Upgrades

Choose exactly one. Before writing any code, name the single function it touches.

Biggest room

Return the largest list count_rooms gave you. No new search needed.

Is the map fully connected?

One flood from any cell. If it reaches every floor cell, the answer is yes.

Add a door

Put one more cell in DOORS and watch the farthest distance drop.

Widen the map until recursion breaks

Make one big open room. Somewhere past 1000 cells in a line, [6] raises RecursionError while [2] keeps working.

Teacher Checkpoints

After TODO 2: ask why bfs and dfs give the same 114 cells. The frontier decides ORDER, never REACH.

After TODO 3: ask what would happen without the 'already claimed' check. Every cell would start its own room.

After TODO 4: ask why several sources need no extra code. They are just a frontier that starts longer.

After TODO 6: cover the screen and ask where the stack is. The answer is: Python is holding it.

At the end: ask which of pop(), pop(0) and popleft() has to move other items, and why.