Tutorial 72026-08-27

The Third Take Rule

Three-hour Python session · roads that cost different amounts · why BFS answers the wrong question · Dijkstra, which is your own loop with one line changed

Mission

Finish line: A map where road, mud and hill charge 1, 5 and 9. Your search finds the route that costs 19 instead of the route that costs 77 — and the only new thing you write is a function that scans a list for the smallest number.

Already yours

The frontier, the seen record, neighbors, rebuild_path. All of it comes straight from weeks 5 and 6.

New this week

Squares have prices, the frontier carries a cost, and you take the cheapest instead of the oldest.

Still not this week

No heapq, no negative prices, no A*. We name them and walk past.

Three-Hour Route

00:00-00:12

A road with a price on it

Draw the home/park/shop map. One road costs 4, two roads cost 3. Let that sit.

00:12-00:30

Warm-Up 1 and 2

Add up a route by hand, then write take_cheapest. It is a scan for the smallest.

00:30-00:45

77 against 19

Play both animations back to back. Same map, same loop, one line apart.

00:45-01:15

TODO 1-4

step_cost, neighbors, take_cheapest, then the loop. Run every checkpoint.

01:15-01:25

Break

Leave 77 and 19 on the board.

01:25-01:45

Warm-Up 3, then TODO 5-6

The same square pushed twice. Settle that, rebuild the route, run [2].

01:45-02:15

Three more questions

TODO 7-9 with Warm-Up 7 and 8: price everywhere, spend a budget, go via a stop.

02:15-02:40

Warm-Up 6, then TODO 10

heapq keeps the smallest ready. Swap one line and run [8] on their own machine.

02:40-03:00

One-way streets, then one upgrade

Warm-Up 5, then pick one extension and name the function it touches.

Part 1 — Roads Have Prices

One sentence: For two weeks every step cost the same, so 'fewest steps' and 'cheapest' were the same question. Put a price on the roads and they come apart.

python

# Last week an edge was just a line. Now it carries a price.roads = {    "home": [("shop", 4), ("park", 1)],    "park": [("home", 1), ("shop", 2)],    "shop": [("home", 4), ("park", 2)],}# home -> shop  is one road, and it costs 4# home -> park -> shop  is two roads, and it costs 1 + 2 = 3## FEWER ROADS is not the same question as CHEAPER.

road costs 1

mud costs 5

hill costs 9

You pay for a square when you step ONTO it. So the square you start on is free, and a route of 19 steps can be cheaper than a route of 13.

Part 2 — BFS Answers The Wrong Question

This is exactly the BFS you wrote in week 5, running on the new map. Watch it. It is not broken — it finds the fewest squares, precisely as it always did. Then look at the bill.

frontier.pop(0)

Fewest steps — BFS

taken out

cost to here

total cost

—

costs waiting in the frontier

takes whichever waited longest

(empty)

.road · 1~mud · 5^hill · 9#wall

13 steps, and it pays 77 because it marched over four hill squares. Every number on the map is what BFS thinks that square cost to reach — and BFS never once used those numbers to decide where to go next.

Part 3 — The Third Take Rule

One sentence: Do not change the loop. Change which entry you take out of it.

week	the line	the list behaves like	what you get
5	frontier.pop(0)	a queue	BFS — fewest steps
5	frontier.pop()	a stack	DFS — some route
7	frontier.pop(cheapest)	a priority queue	Dijkstra — cheapest route

python

def take_next(frontier, mode):    if mode == "oldest":        return frontier.pop(0)      # a queue  -> BFS      -> fewest steps    if mode == "newest":        return frontier.pop()       # a stack  -> DFS      -> some route    return take_cheapest(frontier)  # a priority queue -> Dijkstra -> cheapestdef take_cheapest(frontier):    best_index = 0    for index in range(len(frontier)):        if frontier[index][0] < frontier[best_index][0]:            best_index = index    return frontier.pop(best_index)   # still just pop()

All three are pop(). The first takes position 0, the second takes the last position, and the third takes a position you worked out by scanning. A list that always hands back its smallest item has a name: a priority queue.

Part 4 — Dijkstra

Same map, same loop, one line different. Watch the colour spread by price instead of by distance: it races down the cheap road and only crawls onto the hill at the very end, when nothing cheaper is left.

take_cheapest(frontier)

Cheapest — Dijkstra

taken out

cost to here

total cost

—

costs waiting in the frontier

takes the smallest

(empty)

.road · 1~mud · 5^hill · 9#wall

19 steps and it pays 19. Six more steps than BFS, for 58 less. And notice the guarantee hiding in the animation: because you always take the cheapest thing waiting, the first time a square comes out of the frontier you already know its cheapest price. Nothing later can beat it.

Part 5 — Side By Side

The picture to remember. Neither is wrong. They are answering two different questions.

same map, same loop, one line different

Fewest steps vs cheapest

BFS · fewest steps

steps 13

Dijkstra · cheapest

steps 19

The map has 92 squares you can stand on. BFS reaches the goal in 13 steps and pays 77. Dijkstra walks 19 steps and pays 19. Fewest squares and cheapest route are only the same question when every square charges the same price.

Part 6 — Decide On The Way Out

One sentence: A square can sit in the frontier several times at several prices. You never repair the dear copies — you ignore them as they come out, which is exactly the rule you used for recursion last week.

python

# A square can be pushed into the frontier more than once,# once for every road that reaches it, each with a different price.frontier = [(10, "X"), (4, "X"), (6, "Y")]# We do NOT go back and fix the dear copy. We simply decide# when we TAKE IT OUT - the same rule you used for recursion:    if current in best:        continue          # an older, dearer copy. Ignore it.    best[current] = cost  # the first copy out is always the cheapest one# result: {'X': 4, 'Y': 6}    the (10, "X") copy never mattered

Why is this safe? Because you always take the cheapest. So when a square finally comes out, no cheaper copy of it can still be waiting — if one were, it would have come out first. Warm-Up 3 walks through this one by hand.

Part 7 — Price Every Square

One sentence: search() stops the moment it reaches the goal. Delete that one test and the very same loop prices the whole map instead.

python

# search() stops the moment it reaches the goal.# Take that test out and it keeps going until the frontier is empty -# and then EVERY square has a price on it.def cost_map(grid, sources):    frontier = []    for source in sources:        frontier.append((0, source, None))     # several starts, all free    best = {}    while len(frontier) > 0:        cost, current, parent = take_cheapest(frontier)        if current in best:            continue        best[current] = cost        # no "if current == goal: return" here        for step in neighbors(grid, current):            if step not in best:                frontier.append((cost + step_cost(grid, step), step, current))    return best

squares now carry a price

the dearest square, deep in the hill ridge

put several squares in at 0 and you get nearest-of-many

You met this shape in week 6 with distance_map, where every step counted 1. It is the same idea again — only now a step can count 1, 5 or 9.

Part 8 — What Can You Afford?

Once every square has a price, this question needs no searching at all — just a filter. Watch the budget climb: the cheap road opens up almost immediately, and the hill stays dark until the very end.

cost_map, then filter

What can you afford?

budget 0

1/92 (1%)

With nothing to spend you can only stand where you already are.

.road · 1~mud · 5^hill · 9#wall

budget	squares you can reach	share of the map
5	10 / 92	11%
10	31 / 92	34%
15	52 / 92	57%
20	76 / 92	83%
30	89 / 92	97%
40	92 / 92	100%

Part 9 — Go Via Somewhere

You have to collect a parcel on the way. There is nothing new to write: run the search you already have twice, and glue the two routes together.

python

def route_via(grid, start, via, goal):    # Nothing new. Just the search you already wrote, twice.    first_from, first_best, _ = search(grid, start, via, "cheapest")    second_from, second_best, _ = search(grid, via, goal, "cheapest")    first = rebuild_path(first_from, via)    second = rebuild_path(second_from, goal)    # second[0] is the via square again, so skip it when gluing.    return first + second[1:], first_best[via] + second_best[goal]

must pass through	terrain	total cost	extra
nowhere, go straight	—	19	—
(4, 8)	.	19	+0
(7, 8)	.	25	+6
(7, 2)	.	25	+6
(1, 7)	^	65	+46

One of them is free. (4, 8) already sits on the cheapest route, so being told to pass through it costs nothing extra. The hill square costs 46 more — that is the price of a detour nobody would choose.

Part 10 — One-Way Streets

Back in week 5 we said every road works both ways, and promised to come back to it. Here is the whole difference.

python

# Undirected: every road works both ways (weeks 5 and 6)graph[one].append(other)graph[other].append(one)# Directed: a one-way street. Only one of the two lines.graph[start].append(end)# Nothing else in the search changes at all. neighbors() still just# asks "where can I go from here", and now the answer is one-way.

That is genuinely all of it. BFS, DFS and Dijkstra do not know or care whether the roads are one-way — they only ever ask neighbors() where they can go from here.

Part 11 — Let heapq Do The Scanning

One sentence: A heap is a list that quietly keeps its smallest item ready at position 0. You never scan it and you never sort it — you just ask for the smallest and it hands it over.

python

from heapq import heappush, heappopheap = []heappush(heap, (7, "a"))heappush(heap, (3, "b"))heappush(heap, (5, "c"))print(heappop(heap))      # (3, 'b')  the smallest, with no scanningheappush(heap, (1, "d"))print(heappop(heap))      # (1, 'd')  it jumped the queue, because it is smaller# A heap is a list that quietly keeps its smallest item ready at# position 0. You never scan it, and you never sort it.## In the search, ONE line changes:#     cost, current, parent = take_cheapest(frontier)   # your scan#     cost, current, parent = heappop(heap)             # heapq

Is it worth it?

Last week you learnt that pop(0) costs more the longer the list is. take_cheapest has the same problem: every take has to look at everything still waiting.

items waiting	your scan	heapq	slower by
2,000	26.2 ms	0.3 ms	77x
4,000	112.4 ms	0.8 ms	146x
8,000	463.1 ms	1.8 ms	262x

Double the items and the scan gets about four times slower — the same quadratic shape as pop(0) last week. Your scan is correct and completely fine on a 92-square map. heapq is what you reach for when the frontier gets big.

One honest detail. heapq gives the same cheapest price and the same route, but it may finish a different NUMBER of squares — 70 instead of 73 here. When two squares tie on price, the two versions break the tie differently. Same answer, different order, exactly like recursive and hand-written DFS last week.

Menu option [8] measures all of this on your own machine rather than trusting the table above.

Practice

Five drills. Numbers 2 and 3 are the two things you have to get right before the search will work.

Warm-Up 15 min

Add up what a route costs

Seven squares walked. Two printed lines: the price, and the number of steps. They are not the same number.

python

COST = {".": 1, "~": 5, "^": 9}route = [".", ".", "~", "~", ".", "^", "."]total = 0for square in route:    total = total + COST[square]print(total)print(len(route))

Sample output

23
7

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

Hint 1

You pay for each square you step onto, not for each turn you make.

Hint 2

One hill costs as much as nine road squares.

Warm-Up 26 min

Write take_cheapest

Find the smallest first value, remove that entry, and return it. This is the only new function this week.

python

def take_cheapest(frontier):    # TODO    passwaiting = [(7, "a"), (3, "b"), (5, "c")]print(take_cheapest(waiting))print(waiting)print(take_cheapest(waiting))print(waiting)

Sample output

(3, 'b')
[(7, 'a'), (5, 'c')]
(5, 'c')
[(7, 'a')]

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

Hint 1

Track the index of the best you have seen, starting at 0.

Hint 2

frontier[index][0] is the cost. frontier[index][1] is the cell.

Warm-Up 37 min

The same square, pushed twice

X is in the frontier twice, at two different prices. Two printed lines. Say which copy won and why the other one was ignored.

python

frontier = [(10, "X"), (4, "X"), (6, "Y")]best = {}order = []while len(frontier) > 0:    best_index = 0    for i in range(len(frontier)):        if frontier[i][0] < frontier[best_index][0]:            best_index = i    cost, cell = frontier.pop(best_index)    if cell in best:        continue    best[cell] = cost    order.append(cell)print(order)print(best)

Sample output

['X', 'Y']
{'X': 4, 'Y': 6}

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

Hint 1

Always taking the cheapest means the first copy out is the best one.

Hint 2

That is why we never have to go back and fix an entry already in the list.

Warm-Up 46 min

A road map with prices

Add up the price of a named route. Then compare the two answers and say something surprising.

python

roads = {    "home": [("shop", 4), ("park", 1)],    "park": [("home", 1), ("shop", 2)],    "shop": [("home", 4), ("park", 2)],}def route_cost(roads, route):    # TODO    passprint(route_cost(roads, ["home", "shop"]))print(route_cost(roads, ["home", "park", "shop"]))

Sample output

4
3

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

Hint 1

Each entry is a pair: (where it goes, what it costs).

Hint 2

Walk the route two names at a time and look up the price of that one road.

Warm-Up 56 min

One-way streets

Weeks 5 and 6 added every road twice, once in each direction. Add it once and you get a one-way street.

python

def build_one_way(streets):    # TODO: every name must exist as a key, even with no way out    passstreets = [("a", "b"), ("b", "c"), ("c", "a")]graph = build_one_way(streets)print(graph["a"])print(graph["b"])print("a" in graph["b"])

Sample output

['b']
['c']
False

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

Hint 1

Give both names an empty list first, so a dead end still exists as a key.

Hint 2

The search code does not change at all. Only the map does.

Warm-Up 66 min

A list that keeps its smallest ready

Four printed lines. The fourth one is the surprise: watch what happens to (7, 'a').

python

from heapq import heappush, heappopheap = []heappush(heap, (7, "a"))heappush(heap, (3, "b"))heappush(heap, (5, "c"))print(heappop(heap))print(heappop(heap))heappush(heap, (1, "d"))print(heappop(heap))print(heappop(heap))

Sample output

(3, 'b')
(5, 'c')
(1, 'd')
(7, 'a')

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

Hint 1

A heap is not sorted. It only promises that the smallest is ready.

Hint 2

It compares tuples from the left, so the first number is the price.

Warm-Up 75 min

What can this budget reach?

Filter a dict of prices. Four printed lines, one per budget.

python

costs = {"a": 0, "b": 3, "c": 7, "d": 12, "e": 3}def within_budget(costs, budget):    # TODO    passprint(within_budget(costs, 0))print(within_budget(costs, 3))print(within_budget(costs, 7))print(within_budget(costs, 100))

Sample output

['a']
['a', 'b', 'e']
['a', 'b', 'c', 'e']
['a', 'b', 'c', 'd', 'e']

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

Hint 1

Budget 0 still reaches the square you are standing on, which costs 0.

Hint 2

Use <= , not < . A square that costs exactly your budget is affordable.

Warm-Up 86 min

Add up a trip with a stop

Three routes to school. Add each one up, then say which is cheapest and why that is surprising.

python

legs = {    ("home", "shop"): 4,    ("home", "park"): 1,    ("park", "shop"): 2,    ("shop", "school"): 3,    ("park", "school"): 9,}def trip_cost(legs, route):    # TODO    passprint(trip_cost(legs, ["home", "shop", "school"]))print(trip_cost(legs, ["home", "park", "shop", "school"]))print(trip_cost(legs, ["home", "park", "school"]))

Sample output

7
6
10

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

Hint 1

A pair of names can be a dict key, just like a pair of numbers.

Hint 2

Walk the route two names at a time, from index 1 to the end.

In The Terminal

A real frame from the finished program: Dijkstra has finished, and every square is labelled with the cheapest price found for reaching it. Read row 1 (0, 5, 10, 15 through the mud) against row 4 (3, 4, 5, 6, 7 along the road).

terminal

+----------------------------------------------------------------------------+|                            CHEAPEST  (DIJKSTRA)                            ||            take_cheapest()   - take whatever is cheapest so far            |+----------------------------------------------------------------------------+|                                                                            ||              ################################################              ||              ###  0  5 10 15  ~  ^  ^  ^  ^  ~  ~  ~  ~ 19###              ||              ###  1  6 11 16 17  ^  ^  ^  ^  ~  ~  ~  ~ 18###              ||              ###  2  7 10 11 12 17 18 19  ^ 17 18 19  ~ 17###              ||              ###  3  4  5  6  7  8  9 10 11 12 13 14 15 16###              ||              ###  4  5#########  9 10 11 12######### 16 17###              ||              ###  5  6  7  8  9 10 11 12 13 14 15 16 17 18###              ||              ###  6  7  8  9 10 11 12 13 14 15 16 17 18 19###              ||              ################################################              ||                                                                            |+----------------------------------------------------------------------------+| path length 19 steps     TOTAL COST 19                                     || squares taken out of the frontier: 73/92                                   ||  .  road 1    ~  mud 5    ^  hill 9    #  wall                             |+----------------------------------------------------------------------------+

Start it

bash

python3 terrain_paths.py# The build check runs first. The map only opens after TODO 1-6 pass.#  [1]  Fewest steps   (BFS)          - watch what it pays#  [2]  Cheapest       (Dijkstra)     - watch the cost spread#  [3]  Race them side by side#  [4]  The numbers#  [5]  Every square has a price      - the search with no goal#  [6]  What can you afford?          - raise the budget and watch#  [7]  Pick something up on the way  - search() called twice#  [8]  Let heapq do the scanning     (timed live, on your machine)#  [q]  Quit

01Choose [1]. Watch BFS walk straight over the hill, and read the cost it pays: 77.

02Choose [2]. The colour spreads by price, not by distance. It crawls over the hill last.

03Watch the frontier line at the bottom of [2]. The number it takes is always the smallest one there.

04Choose [3]. Both finish: 13 steps for 77, against 19 steps for 19.

05Choose [5]. It never stops early, so every one of the 92 squares ends up with a price.

06Choose [6] and watch the budget climb. The road opens up fast; the hill is last to light up.

07Choose [7]. One of the four checkpoints costs nothing extra. Work out why before reading on.

08Choose [8] on your own laptop. Same cost, same route, sometimes a different square count.

09Break it: in take_cheapest use > instead of <. You now always take the DEAREST.

10Break it: delete 'if current in best: continue' and watch a square get finished twice.

11Change one number: make hill cost 2 instead of 9. Dijkstra's route should change shape.

12In route_via, forget to skip the repeated via square. The cost stays right but the route lists it twice.

TODO Contract

Six functions. Four of them you have written before. Read the card before the code and run each checkpoint.

TODO 1Phase 1 - The map has prices

step_cost

Purpose

Look up what one square charges.

Input

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

Output / Return

The price of stepping onto that square, from COST.

State change

Nothing. 'S' and 'G' cost 1 like a road.

Checkpoint

python

print(step_cost(TERRAIN, (4, 1)))    # 1   roadprint(step_cost(TERRAIN, (1, 2)))    # 5   mudprint(step_cost(TERRAIN, (1, 6)))    # 9   hill

TODO 2Phase 1 - The map has prices

neighbors

Purpose

Where can I step from here? Same helper as weeks 5 and 6.

Input

grid; cell, a pair (row, col)

Output / Return

The open squares up, down, left and right, in DIRECTIONS order.

State change

Nothing. Cost is not this function's job.

Checkpoint

python

print(neighbors(TERRAIN, (1, 1)))    # [(2, 1), (1, 2)]print(len(neighbors(TERRAIN, (4, 4))))   # 4

TODO 3Phase 2 - The third take rule

take_cheapest

Purpose

The one genuinely new function of the week.

Input

frontier, a list of (cost, cell, came_from) triples

Output / Return

The triple with the smallest cost, removed from frontier.

State change

frontier loses exactly one triple. Still just pop().

Checkpoint

python

waiting = [(7, "a", None), (3, "b", None), (5, "c", None)]print(take_cheapest(waiting))   # (3, 'b', None)print(waiting)                  # [(7, 'a', None), (5, 'c', None)]

TODO 4Phase 2 - The third take rule

search

Purpose

One loop, two questions. Only the take line changes.

Input

grid, start, goal, mode ("steps" or "cheapest")

Output / Return

came_from, best (cell -> cheapest cost found) and the order taken.

State change

Push (cost so far + step_cost of the neighbour, neighbour, current).

Checkpoint

python

came_from, best, order = search(TERRAIN, START, GOAL, "cheapest")print(best[START])       # 0print(best[GOAL])        # 19came_from, best, order = search(TERRAIN, START, GOAL, "steps")print(best[GOAL])        # 77

TODO 5Phase 3 - The route

rebuild_path

Purpose

Turn came_from into a route you can walk. Same as week 5.

Input

came_from; goal, a pair

Output / Return

Cells from start to goal in walking order, or [] if unreached.

State change

Nothing.

Checkpoint

python

came_from, best, order = search(TERRAIN, START, GOAL, "cheapest")path = rebuild_path(came_from, GOAL)print(len(path) - 1)     # 19   stepsprint(path[0], path[-1]) # (1, 1) (1, 14)

TODO 6Phase 3 - The route

path_cost

Purpose

Add up the price of a finished route.

Input

grid; path, the list rebuild_path() gave back

Output / Return

The total price of walking it.

State change

The start square is free. You only pay to step ONTO a square.

Checkpoint

python

steps_from, _, _ = search(TERRAIN, START, GOAL, "steps")cheap_from, _, _ = search(TERRAIN, START, GOAL, "cheapest")print(path_cost(TERRAIN, rebuild_path(steps_from, GOAL)))   # 77print(path_cost(TERRAIN, rebuild_path(cheap_from, GOAL)))   # 19

TODO 7Phase 4 - Three more questions

cost_map

Purpose

Question 2: price EVERY square, not just the goal.

Input

grid; sources, a LIST of squares that start free

Output / Return

A dict, square -> cheapest price to reach it.

State change

Take the goal test out so it runs until the frontier empties.

Checkpoint

python

costs = cost_map(TERRAIN, [START])print(len(costs))                  # 92   every square has a priceprint(max(costs.values()))         # 37   the dearest oneprint(costs[START])                # 0

TODO 8Phase 4 - Three more questions

within_budget

Purpose

Question 3: with this much money, where can I get to?

Input

costs, the dict cost_map() returned; budget, a number

Output / Return

A sorted list of every square you can afford.

State change

Nothing. Use <= so a square costing exactly the budget counts.

Checkpoint

python

costs = cost_map(TERRAIN, [START])print(len(within_budget(costs, 5)))     # 10print(len(within_budget(costs, 15)))    # 52print(len(within_budget(costs, 40)))    # 92

TODO 9Phase 4 - Three more questions

route_via

Purpose

Question 4: go via somewhere. Call search() twice and glue.

Input

grid; start, via, goal

Output / Return

(the whole route, what it costs). ([], 0) if either half fails.

State change

Do not write the via square twice when you glue the halves.

Checkpoint

python

route, cost = route_via(TERRAIN, START, (4, 8), GOAL)print(cost)                        # 19   this one is free, it was on the wayroute, cost = route_via(TERRAIN, START, (1, 7), GOAL)print(cost)                        # 65   that hill is expensive

TODO 10Phase 5 - Let heapq help

search_with_heap

Purpose

The same search, with heapq doing the scanning for you.

Input

grid, start, goal

Output / Return

(came_from, best), exactly as search() would give.

State change

heappush instead of append, heappop instead of take_cheapest.

Checkpoint

python

heap_from, heap_best = search_with_heap(TERRAIN, START, GOAL)scan_from, scan_best, _ = search(TERRAIN, START, GOAL, "cheapest")print(heap_best[GOAL], scan_best[GOAL])                               # 19 19print(rebuild_path(heap_from, GOAL) == rebuild_path(scan_from, GOAL)) # True

Student Work Area

Only edit this part: All six TODOs live here. Read the comment at the top first — it lines up this week's take rule with the two you already know.

student_work.py

python

# ================================================================# THE THIRD TAKE RULE## Week 5:  frontier.pop(0)   take the OLDEST     -> a queue  -> BFS# Week 5:  frontier.pop()    take the NEWEST     -> a stack  -> DFS# This week: frontier.pop(i) take the CHEAPEST   -> a priority queue#                                               -> Dijkstra## All three are pop(). Everything else stays exactly where it was.# ================================================================def step_cost(grid, cell):    # TODO 1    # Input: grid, a list of strings; cell, a pair (row, col)    # Return: what it costs to walk ONTO that square, using COST    # Change: nothing    return 0def neighbors(grid, cell):    # TODO 2    # Input: grid; cell, a pair (row, col)    # Return: the squares up, down, left and right that are not '#'    #         and are still inside the grid, in DIRECTIONS order    # Change: nothing    return []def take_cheapest(frontier):    # TODO 3  -  the only genuinely new line of the week    # Input: frontier, a list of (cost, cell, came_from) triples    # Return: the triple with the SMALLEST cost, REMOVED from frontier    # Change: frontier loses exactly one triple    #    # Walk the list, remember the position of the smallest cost so far,    # then frontier.pop(that position).    return Nonedef search(grid, start, goal, mode):    # frontier holds triples: (cost to get here, the cell, the cell we came from)    frontier = [(0, start, None)]    best = {}    came_from = {}    order = []    while len(frontier) > 0:        # TODO 4a        #   mode == "steps"   -> take the OLDEST triple      (this is BFS)        #   mode == "cheapest" -> take the cheapest triple    (this is Dijkstra)        cost, current, parent = (0, start, None)        # Provided. A cell can be pushed more than once, so we decide when we        # TAKE IT OUT - exactly the rule you learnt for recursion last week.        # The first copy to come out is always the best one.        if current in best:            continue        best[current] = cost        came_from[current] = parent        order.append(current)        if current == goal:            return came_from, best, order        # TODO 4b        # For every neighbour that is not finished yet, push a new triple:        #   (cost so far + step_cost of that neighbour, the neighbour, current)    return came_from, best, orderdef rebuild_path(came_from, goal):    # TODO 5    # Input: came_from, the dict search() returned; goal, a pair    # Return: the cells from start to goal in walking order, or [] if unreached    # Change: nothing    return []def path_cost(grid, path):    # TODO 6    # Input: grid; path, the list rebuild_path() returned    # Return: the total cost of walking it    # Change: nothing    #    # You pay for every square you step ONTO, so the start square is free.    return 0# ================================================================# THE SAME SEARCH, THREE MORE QUESTIONS# ================================================================def cost_map(grid, sources):    # TODO 7  -  do not stop at a goal. Price EVERY square.    # Input: grid; sources, a LIST of squares that start at cost 0    # Return: a dict, square -> the cheapest price to reach it    # Change: nothing    #    # This is search() with the goal test taken out, so it keeps going    # until the frontier is empty. One source or several, same code.    return {}def within_budget(costs, budget):    # TODO 8    # Input: costs, the dict cost_map() returned; budget, a number    # Return: a sorted list of every square you can reach for budget or less    # Change: nothing    return []def route_via(grid, start, via, goal):    # TODO 9  -  pick something up on the way    # Input: grid; start, via, goal - three squares    # Return: (the whole route as one list, what it costs)    #         Return ([], 0) if either half cannot be walked.    # Change: nothing    #    # Run the search you already have TWICE: start -> via, then via -> goal.    # Glue the two routes together, but do not write the via square twice.    return [], 0def search_with_heap(grid, start, goal):    # TODO 10  -  the same search, letting heapq do the scanning    # Input: grid, start, goal    # Return: (came_from, best) exactly as search() would    # Change: nothing    #    # heappush(heap, item) puts an item in.    # heappop(heap) takes the SMALLEST item out, without any scanning.    # Everything else in the loop stays exactly as you already wrote it.    return {}, {}

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.

terrain_paths.py

python

import reimport sysfrom heapq import heappop, heappushfrom 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")# '#' wall, '.' road, '~' mud, '^' hill.# Walking ONTO a square costs what that square charges.TERRAIN = [    "################",    "#S~~~~^^^^~~~~G#",    "#.~~~~^^^^~~~~.#",    "#.~~~~^^^^~~~~.#",    "#..............#",    "#..###....###..#",    "#..............#",    "#..............#",    "################",]COST = {".": 1, "~": 5, "^": 9, "S": 1, "G": 1}DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]TERRAIN_STYLE = {    "#": ((46, 50, 68), (46, 50, 68), "  "),    ".": ((26, 34, 48), (120, 140, 170), " ."),    "~": ((28, 66, 84), (120, 210, 235), " ~"),    "^": ((78, 58, 30), (245, 190, 110), " ^"),    "S": ((72, 226, 255), (8, 24, 34), " S"),    "G": ((255, 96, 96), (40, 8, 8), " G"),}def rgb_bg(text, background, foreground):    if not USE_COLOR:        return str(text)    return (        f"{ESC}48;2;{background[0]};{background[1]};{background[2]}m"        f"{ESC}38;2;{foreground[0]};{foreground[1]};{foreground[2]}m{text}{RESET}"    )def rgb(text, red, green, blue, bold=False):    if not USE_COLOR:        return str(text)    return f"{ESC}{'1;' if bold else ''}38;2;{red};{green};{blue}m{text}{RESET}"def dim(text):    return str(text) if not USE_COLOR else f"{ESC}2m{text}{RESET}"def gradient_text(text, start=(120, 235, 255), end=(255, 170, 90)):    if not USE_COLOR or len(text) <= 1:        return str(text)    out = ""    for index, character in enumerate(text):        ratio = index / (len(text) - 1)        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="")def find_cell(grid, letter):    for row in range(len(grid)):        col = grid[row].find(letter)        if col >= 0:            return (row, col)    return NoneSTART = find_cell(TERRAIN, "S")GOAL = find_cell(TERRAIN, "G")def open_cells(grid):    return [        (row, col)        for row in range(len(grid))        for col in range(len(grid[row]))        if grid[row][col] != "#"    ]TOTAL_OPEN = len(open_cells(TERRAIN))def cost_colour(value, biggest):    """Cheap to reach is green; dear to reach is red."""    ratio = 0.0 if biggest <= 0 else min(1.0, value / biggest)    return (round(40 + 215 * ratio), round(205 - 145 * ratio), round(120 - 70 * ratio))def draw_map(grid, paint, labels=None, cell_width=3):    """paint: cell -> (r, g, b) background. labels: cell -> short text."""    if labels is None:        labels = {}    lines = []    for row in range(len(grid)):        line = ""        for col in range(len(grid[row])):            cell = (row, col)            character = grid[row][col]            background, foreground, text = TERRAIN_STYLE[character]            if cell in labels:                text = labels[cell]            if cell in paint and character != "#":                background = paint[cell]                foreground = (12, 16, 24)            if not USE_COLOR and character == "#":                text = "#" * cell_width            line += rgb_bg(str(text).strip().rjust(cell_width)[:cell_width],                           background, foreground)        lines.append(line)    return linesdef terrain_key():    parts = []    for character, label in ((".", "road 1"), ("~", "mud 5"), ("^", "hill 9"), ("#", "wall")):        background, foreground, text = TERRAIN_STYLE[character]        glyph = character if USE_COLOR else character        parts.append(rgb_bg(" " + glyph + " ", background, foreground) + " " + dim(label))    return "   ".join(parts)# ================================================================# THE THIRD TAKE RULE## Week 5:  frontier.pop(0)   take the OLDEST     -> a queue  -> BFS# Week 5:  frontier.pop()    take the NEWEST     -> a stack  -> DFS# This week: frontier.pop(i) take the CHEAPEST   -> a priority queue#                                               -> Dijkstra## All three are pop(). Everything else stays exactly where it was.# ================================================================def step_cost(grid, cell):    # TODO 1    # Input: grid, a list of strings; cell, a pair (row, col)    # Return: what it costs to walk ONTO that square, using COST    # Change: nothing    return 0def neighbors(grid, cell):    # TODO 2    # Input: grid; cell, a pair (row, col)    # Return: the squares up, down, left and right that are not '#'    #         and are still inside the grid, in DIRECTIONS order    # Change: nothing    return []def take_cheapest(frontier):    # TODO 3  -  the only genuinely new line of the week    # Input: frontier, a list of (cost, cell, came_from) triples    # Return: the triple with the SMALLEST cost, REMOVED from frontier    # Change: frontier loses exactly one triple    #    # Walk the list, remember the position of the smallest cost so far,    # then frontier.pop(that position).    return Nonedef search(grid, start, goal, mode):    # frontier holds triples: (cost to get here, the cell, the cell we came from)    frontier = [(0, start, None)]    best = {}    came_from = {}    order = []    while len(frontier) > 0:        # TODO 4a        #   mode == "steps"   -> take the OLDEST triple      (this is BFS)        #   mode == "cheapest" -> take the cheapest triple    (this is Dijkstra)        cost, current, parent = (0, start, None)        # Provided. A cell can be pushed more than once, so we decide when we        # TAKE IT OUT - exactly the rule you learnt for recursion last week.        # The first copy to come out is always the best one.        if current in best:            continue        best[current] = cost        came_from[current] = parent        order.append(current)        if current == goal:            return came_from, best, order        # TODO 4b        # For every neighbour that is not finished yet, push a new triple:        #   (cost so far + step_cost of that neighbour, the neighbour, current)    return came_from, best, orderdef rebuild_path(came_from, goal):    # TODO 5    # Input: came_from, the dict search() returned; goal, a pair    # Return: the cells from start to goal in walking order, or [] if unreached    # Change: nothing    return []def path_cost(grid, path):    # TODO 6    # Input: grid; path, the list rebuild_path() returned    # Return: the total cost of walking it    # Change: nothing    #    # You pay for every square you step ONTO, so the start square is free.    return 0# ================================================================# THE SAME SEARCH, THREE MORE QUESTIONS# ================================================================def cost_map(grid, sources):    # TODO 7  -  do not stop at a goal. Price EVERY square.    # Input: grid; sources, a LIST of squares that start at cost 0    # Return: a dict, square -> the cheapest price to reach it    # Change: nothing    #    # This is search() with the goal test taken out, so it keeps going    # until the frontier is empty. One source or several, same code.    return {}def within_budget(costs, budget):    # TODO 8    # Input: costs, the dict cost_map() returned; budget, a number    # Return: a sorted list of every square you can reach for budget or less    # Change: nothing    return []def route_via(grid, start, via, goal):    # TODO 9  -  pick something up on the way    # Input: grid; start, via, goal - three squares    # Return: (the whole route as one list, what it costs)    #         Return ([], 0) if either half cannot be walked.    # Change: nothing    #    # Run the search you already have TWICE: start -> via, then via -> goal.    # Glue the two routes together, but do not write the via square twice.    return [], 0def search_with_heap(grid, start, goal):    # TODO 10  -  the same search, letting heapq do the scanning    # Input: grid, start, goal    # Return: (came_from, best) exactly as search() would    # Change: nothing    #    # heappush(heap, item) puts an item in.    # heappop(heap) takes the SMALLEST item out, without any scanning.    # Everything else in the loop stays exactly as you already wrote it.    return {}, {}WIDTH = 78INSIDE = WIDTH - 4MAP_WIDTH = len(TERRAIN[0]) * 2MODE_NAME = {"steps": "FEWEST STEPS  (BFS)", "cheapest": "CHEAPEST  (DIJKSTRA)"}MODE_RULE = {    "steps": "frontier.pop(0)   - take whatever has waited longest",    "cheapest": "take_cheapest()   - take whatever is cheapest so far",}def 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(TERRAIN, paint, labels), footer)    if ANIMATE and delay > 0:        sleep(delay)def frontier_note(frontier, mode):    if len(frontier) == 0:        return dim("frontier  (empty)")    costs = sorted(entry[0] for entry in frontier)    shown = costs[:6]    body = " ".join(str(value) for value in shown)    if len(costs) > 6:        body += " ..."    if mode == "cheapest":        return "frontier costs  [ " + body + " ]   " + rgb(            f"taking {costs[0]}", 120, 235, 160, bold=True        )    return "frontier costs  [ " + body + " ]   " + dim("taking whichever waited longest")def run(mode):    came_from, best, order = search(TERRAIN, START, GOAL, mode)    path = rebuild_path(came_from, GOAL)    return came_from, best, order, pathdef replay(mode, delay=0.05):    """Re-walk the student's own search so the screen can show it growing."""    frontier = [(0, START, None)]    best = {}    frames = []    while len(frontier) > 0:        if mode == "steps":            cost, current, parent = frontier.pop(0)        else:            cost, current, parent = take_cheapest(frontier)        if current in best:            continue        best[current] = cost        frames.append((current, dict(best), list(frontier)))        if current == GOAL:            break        for step in neighbors(TERRAIN, current):            if step not in best:                frontier.append((cost + step_cost(TERRAIN, step), step, current))    return framesdef view_search(mode, delay=0.045):    came_from, best, order, path = run(mode)    frames = replay(mode)    biggest = max(best.values())    hide_cursor()    try:        for index, (current, so_far, frontier) in enumerate(frames):            paint = {cell: cost_colour(so_far[cell], biggest) for cell in so_far}            labels = {cell: str(so_far[cell]).rjust(2)[:2] for cell in so_far}            labels[current] = "()"            show(                MODE_NAME[mode],                MODE_RULE[mode],                paint,                labels,                [                    f"taken out {index + 1}/{len(frames)}"                    f"     cost to reach here {so_far[current]}"                    f"     still waiting {len(frontier)}",                    frontier_note(frontier, mode),                    terrain_key(),                ],                delay,            )        paint = {cell: cost_colour(best[cell], biggest) for cell in best}        for cell in path:            paint[cell] = (250, 240, 120)        labels = {cell: str(best[cell]).rjust(2)[:2] for cell in best}        show(            MODE_NAME[mode],            MODE_RULE[mode],            paint,            labels,            [                rgb(f"path length {len(path) - 1} steps", 150, 200, 255, bold=True)                + "     "                + rgb(f"TOTAL COST {path_cost(TERRAIN, path)}", 255, 210, 90, bold=True),                f"squares taken out of the frontier: {len(order)}/{TOTAL_OPEN}",                terrain_key(),            ],        )    finally:        show_cursor()def view_race(delay=0.05):    results = {}    for mode in ("steps", "cheapest"):        came_from, best, order, path = run(mode)        results[mode] = (best, path, replay(mode))    longest = max(len(results[m][2]) for m in results)    biggest = max(max(results[m][0].values()) for m in results)    gap = "   "    hide_cursor()    try:        for index in range(longest + 1):            grids, foot = [], []            for mode in ("steps", "cheapest"):                best, path, frames = results[mode]                at = min(index, len(frames) - 1)                current, so_far, frontier = frames[at]                done = index >= len(frames)                paint = {cell: cost_colour(so_far[cell], biggest) for cell in so_far}                labels = {cell: str(so_far[cell]).rjust(2)[:2] for cell in so_far}                if done:                    for cell in path:                        paint[cell] = (250, 240, 120)                else:                    labels[current] = "()"                grids.append(draw_map(TERRAIN, paint, {}, cell_width=2))                foot.append(                    center_visible(                        f"taken {min(index + 1, len(frames))}"                        + (f"   COST {path_cost(TERRAIN, path)}" if done else ""),                        MAP_WIDTH,                    )                )            clear_screen()            lines = [                rule(),                centered(gradient_text("FEWEST STEPS  vs  CHEAPEST")),                centered(dim("same map, same start, same goal, same loop")),                rule(),                row(""),                centered(                    center_visible(rgb("BFS  fewest steps", 150, 200, 255, bold=True), MAP_WIDTH)                    + gap                    + center_visible(rgb("DIJKSTRA  cheapest", 120, 235, 160, bold=True), MAP_WIDTH)                ),                row(""),            ]            for line_index in range(len(grids[0])):                lines.append(centered(grids[0][line_index] + gap + grids[1][line_index]))            lines.append(row(""))            lines.append(centered(foot[0] + gap + foot[1]))            lines.append(rule())            lines.append(row(terrain_key()))            lines.append(rule())            print("\n".join(lines))            if ANIMATE:                sleep(delay)    finally:        show_cursor()def view_numbers():    clear_screen()    rows = []    data = {}    for mode in ("steps", "cheapest"):        came_from, best, order, path = run(mode)        data[mode] = (len(path) - 1, path_cost(TERRAIN, path), len(order))    steps_s, cost_s, seen_s = data["steps"]    steps_c, cost_c, seen_c = data["cheapest"]    rows += [        rule(),        centered(gradient_text("THE NUMBERS")),        rule(),        row(""),        row(f"{'':<30}{'BFS':>12}{'DIJKSTRA':>12}"),        row(f"{'steps walked':<30}{steps_s:>12}{steps_c:>12}"),        row(f"{'TOTAL COST PAID':<30}{cost_s:>12}{cost_c:>12}"),        row(f"{'squares taken out':<30}{seen_s:>12}{seen_c:>12}"),        row(""),        rule(),        row(f"Dijkstra walks {steps_c - steps_s} MORE steps and pays {cost_s - cost_c} LESS."),        row(""),        row(dim("BFS answers 'fewest squares'. That is only the same thing as")),        row(dim("'cheapest' when every square charges the same price.")),        rule(),    ]    print("\n".join(rows))def _unused_view_speed():    from heapq import heappush, heappop    from random import Random    from time import perf_counter    clear_screen()    lines = [        rule(),        centered(gradient_text("HOW SLOW IS 'FIND THE CHEAPEST'?")),        centered(dim("scanning the whole list, versus letting heapq keep it sorted")),        rule(),        row(""),        row(f"  {'items':>8} {'scan the list':>16} {'heapq':>12} {'slower by':>11}"),    ]    for size in (2000, 4000, 8000):        rng = Random(7)        values = [rng.randint(0, 10 ** 6) for _ in range(size)]        plain = list(values)        start = perf_counter()        while plain:            best_index = 0            for index in range(len(plain)):                if plain[index] < plain[best_index]:                    best_index = index            plain.pop(best_index)        scan_time = perf_counter() - start        heap = []        start = perf_counter()        for value in values:            heappush(heap, value)        while heap:            heappop(heap)        heap_time = perf_counter() - start        lines.append(            row(f"  {size:>8} {scan_time * 1000:>14.1f}ms {heap_time * 1000:>10.1f}ms"                f" {rgb(f'{scan_time / heap_time:.0f}x', 255, 130, 130, bold=True):>11}")        )    lines += [        row(""),        rule(),        row("Double the items and the scan gets about FOUR times slower,"),        row("because every take has to look at everything still waiting."),        row(""),        row(dim("Your take_cheapest is the scan. It is correct, and it is")),        row(dim("perfectly fine on a map this size. When a frontier gets big,")),        row(dim("the same idea written with heapq is the one people reach for.")),        rule(),    ]    print("\n".join(lines))# ---------------------------------------------------------------- 6def view_cost_map():    costs = cost_map(TERRAIN, [START])    biggest = max(costs.values())    dearest = max(costs, key=lambda cell: (costs[cell], cell))    rings = sorted(set(costs.values()))    hide_cursor()    try:        for limit in rings:            shown = {cell: costs[cell] for cell in costs if costs[cell] <= limit}            paint = {cell: cost_colour(shown[cell], biggest) for cell in shown}            labels = {cell: str(shown[cell]) for cell in shown}            show(                "EVERY SQUARE HAS A PRICE",                "the same search with the goal test removed",                paint,                labels,                [                    f"cheapest price so far {limit}/{biggest}"                    f"     squares priced {len(shown)}/{TOTAL_OPEN}",                    dim("Nothing here stops early. It keeps going until the frontier is empty."),                    terrain_key(),                ],                0.05,            )        show(            "EVERY SQUARE HAS A PRICE",            "the same search with the goal test removed",            {cell: cost_colour(costs[cell], biggest) for cell in costs},            {cell: str(costs[cell]) for cell in costs},            [                rgb(f"dearest square {dearest} costs {costs[dearest]}", 255, 210, 90, bold=True),                f"every one of the {len(costs)} squares now has a price",                terrain_key(),            ],        )    finally:        show_cursor()# ---------------------------------------------------------------- 7def view_budget():    costs = cost_map(TERRAIN, [START])    biggest = max(costs.values())    hide_cursor()    try:        for budget in range(0, biggest + 2):            affordable = within_budget(costs, budget)            paint = {cell: cost_colour(costs[cell], budget if budget else 1) for cell in affordable}            labels = {cell: str(costs[cell]) for cell in affordable}            share = round(100 * len(affordable) / TOTAL_OPEN)            show(                "WHAT CAN YOU AFFORD?",                f"every square you can reach for {budget} coins or fewer",                paint,                labels,                [                    rgb(f"budget {budget:>3}", 120, 235, 160, bold=True)                    + f"     you can reach {len(affordable):>3}/{TOTAL_OPEN} squares  ({share}%)",                    "[" + "#" * round(len(affordable) / 3) + "." * (31 - round(len(affordable) / 3)) + "]",                    terrain_key(),                ],                0.11,            )    finally:        show_cursor()# ---------------------------------------------------------------- 8VIA_POINTS = [(4, 8), (7, 8), (7, 2), (1, 7)]def view_via():    direct_from, direct_best, _ = search(TERRAIN, START, GOAL, "cheapest")    direct = direct_best[GOAL]    clear_screen()    rows = [        rule(),        centered(gradient_text("PICK SOMETHING UP ON THE WAY")),        centered(dim("run the search you already have, twice, and glue the routes together")),        rule(),        row(""),        row(f"{'straight to the goal':<34}{'cost ' + str(direct):>12}{'detour':>10}"),        row(""),    ]    for via in VIA_POINTS:        route, cost = route_via(TERRAIN, START, via, GOAL)        character = TERRAIN[via[0]][via[1]]        extra = cost - direct        colour = (120, 235, 160) if extra == 0 else (255, 190, 90) if extra < 20 else (255, 120, 120)        rows.append(            row(f"{'via ' + str(via) + '  on ' + repr(character):<34}"                f"{'cost ' + str(cost):>12}"                + rgb(f"{'+' + str(extra):>10}", *colour, bold=True))        )    rows += [        row(""),        rule(),        row("One of these is free: that square already sits on the cheapest route,"),        row("so going through it costs nothing extra."),        row(""),        row(dim("Nothing new was written here. route_via just calls search() twice.")),        rule(),    ]    print("\n".join(rows))    best_via = min(VIA_POINTS, key=lambda cell: route_via(TERRAIN, START, cell, GOAL)[1])    route, cost = route_via(TERRAIN, START, best_via, GOAL)    input("\nPress Enter to see the cheapest of them drawn: ")    costs = cost_map(TERRAIN, [START])    paint = {cell: cost_colour(costs[cell], max(costs.values())) for cell in costs}    for cell in route:        paint[cell] = (250, 240, 120)    paint[best_via] = (120, 235, 160)    show(        "PICK SOMETHING UP ON THE WAY",        f"start -> {best_via} -> goal",        paint,        {best_via: " V"},        [            rgb(f"via {best_via}: {len(route) - 1} steps, cost {cost}", 255, 210, 90, bold=True),            f"straight to the goal would have cost {direct}",            terrain_key(),        ],    )# ---------------------------------------------------------------- 9def view_heap():    scan_from, scan_best, scan_order = search(TERRAIN, START, GOAL, "cheapest")    heap_from, heap_best = search_with_heap(TERRAIN, START, GOAL)    scan_path = rebuild_path(scan_from, GOAL)    heap_path = rebuild_path(heap_from, GOAL)    from time import perf_counter    from random import Random    clear_screen()    lines = [        rule(),        centered(gradient_text("LET heapq DO THE SCANNING")),        rule(),        row(""),        row(f"{'cost to the goal':<34}{'scan ' + str(scan_best[GOAL]):>14}"            f"{'heapq ' + str(heap_best[GOAL]):>16}"),        row(f"{'same route, square for square':<34}"            f"{str(scan_path == heap_path):>14}"),        row(f"{'squares taken out':<34}{len(scan_best):>14}{len(heap_best):>16}"),        row(""),        row(dim("Same answer, sometimes a different number of squares: when two")),        row(dim("squares tie on price, the two versions break the tie differently.")),        row(""),        rule(),        row(f"  {'items waiting':>14} {'scan the list':>16} {'heapq':>12} {'slower by':>11}"),    ]    for size in (2000, 4000, 8000):        rng = Random(7)        values = [rng.randint(0, 10 ** 6) for _ in range(size)]        plain = list(values)        started = perf_counter()        while plain:            best_index = 0            for index in range(len(plain)):                if plain[index] < plain[best_index]:                    best_index = index            plain.pop(best_index)        scan_time = perf_counter() - started        heap = []        started = perf_counter()        for value in values:            heappush(heap, value)        while heap:            heappop(heap)        heap_time = perf_counter() - started        lines.append(            row(f"  {size:>14} {scan_time * 1000:>14.1f}ms {heap_time * 1000:>10.1f}ms"                f" {rgb(f'{scan_time / heap_time:.0f}x', 255, 130, 130, bold=True):>11}")        )    lines += [        row(""),        rule(),        row("Double the items and the scan gets about FOUR times slower."),        row("heapq keeps the smallest ready at all times, so a take is cheap."),        row(""),        row(dim("Your scan is correct and is fine on a 92 square map. heapq is what")),        row(dim("you reach for when the frontier gets big.")),        rule(),    ]    print("\n".join(lines))# ---------------------------------------------------------------- checksTINY = [    "######",    "#S~~G#",    "#....#",    "######",]def run_build_checks():    assert step_cost(TERRAIN, (4, 1)) == 1, "TODO 1 failed: '.' costs 1."    assert step_cost(TERRAIN, (1, 2)) == 5, "TODO 1 failed: '~' costs 5."    assert step_cost(TERRAIN, (1, 6)) == 9, "TODO 1 failed: '^' costs 9."    assert step_cost(TERRAIN, START) == 1, "TODO 1 failed: 'S' costs 1."    assert neighbors(TINY, (1, 1)) == [(2, 1), (1, 2)], (        "TODO 2 failed: only down and right are open, in DIRECTIONS order."    )    assert neighbors(TINY, (2, 4)) == [(1, 4), (2, 3)], (        "TODO 2 failed: walls and the grid edge must both be rejected."    )    waiting = [(7, "a", None), (3, "b", None), (5, "c", None)]    assert take_cheapest(waiting) == (3, "b", None), (        "TODO 3 failed: return the triple with the smallest first value."    )    assert waiting == [(7, "a", None), (5, "c", None)], (        "TODO 3 failed: the triple must be REMOVED from frontier."    )    single = [(4, "only", None)]    assert take_cheapest(single) == (4, "only", None) and single == [], (        "TODO 3 failed: a one-item frontier must still work."    )    tiny_start, tiny_goal = find_cell(TINY, "S"), find_cell(TINY, "G")    came_from, best, order = search(TINY, tiny_start, tiny_goal, "cheapest")    assert best[tiny_start] == 0, "TODO 4 failed: the start costs 0 to reach."    assert tiny_goal in best, "TODO 4 failed: the goal was never reached."    assert best[tiny_goal] == 5, (        "TODO 4 failed: the cheapest way to G costs 5. Straight through the mud costs 11."    )    assert order[0] == tiny_start, "TODO 4 failed: the start comes out first."    assert len(order) == len(set(order)), "TODO 4 failed: no square may be finished twice."    path = rebuild_path(came_from, tiny_goal)    assert path[0] == tiny_start and path[-1] == tiny_goal, (        "TODO 5 failed: the path must run from S to G."    )    for index in range(1, len(path)):        gap = abs(path[index][0] - path[index - 1][0]) + abs(path[index][1] - path[index - 1][1])        assert gap == 1, "TODO 5 failed: every step must move exactly one square."    assert rebuild_path({tiny_start: None}, tiny_goal) == [], (        "TODO 5 failed: return [] when the goal was never reached."    )    assert path_cost(TINY, path) == 5, (        "TODO 6 failed: the start square is free, you only pay to step ON to a square."    )    steps_from_tiny, steps_best_tiny, _ = search(TINY, tiny_start, tiny_goal, "steps")    tiny_steps_path = rebuild_path(steps_from_tiny, tiny_goal)    assert len(tiny_steps_path) - 1 == 3 and path_cost(TINY, tiny_steps_path) == 11, (        "TODO 4 failed: mode 'steps' must take the OLDEST, which walks straight through the mud."    )    assert path_cost(TINY, []) == 0, "TODO 6 failed: an empty path costs 0."    everywhere = cost_map(TINY, [tiny_start])    assert len(everywhere) == len(open_cells(TINY)), (        "TODO 7 failed: cost_map must price EVERY square, not stop at a goal."    )    assert everywhere[tiny_start] == 0, "TODO 7 failed: a source costs 0."    assert everywhere[tiny_goal] == 5, (        "TODO 7 failed: the cheapest way to G costs 5 on the small map."    )    two_sources = cost_map(TINY, [tiny_start, tiny_goal])    assert two_sources[tiny_goal] == 0, (        "TODO 7 failed: with several sources, every source starts at 0."    )    assert within_budget(everywhere, 0) == [tiny_start], (        "TODO 8 failed: with no money you can only stand where you already are."    )    assert within_budget(everywhere, 100) == sorted(open_cells(TINY)), (        "TODO 8 failed: a huge budget reaches everything, sorted."    )    assert len(within_budget(everywhere, 2)) < len(within_budget(everywhere, 4)), (        "TODO 8 failed: a bigger budget must reach at least as much."    )    via_route, via_cost = route_via(TINY, tiny_start, (2, 2), tiny_goal)    assert via_route[0] == tiny_start and via_route[-1] == tiny_goal, (        "TODO 9 failed: the glued route must still run from start to goal."    )    assert via_route.count((2, 2)) == 1, (        "TODO 9 failed: do not write the via square twice when you glue the halves."    )    assert via_cost == path_cost(TINY, via_route), (        "TODO 9 failed: the cost you return must match the route you return."    )    heap_from, heap_best = search_with_heap(TINY, tiny_start, tiny_goal)    assert heap_best[tiny_goal] == 5, (        "TODO 10 failed: heapq must find the same cheapest price, 5."    )    assert rebuild_path(heap_from, tiny_goal) == path, (        "TODO 10 failed: heapq must find the same route on the small map."    )    # Dijkstra must never be beaten on price, and BFS must never be beaten on steps.    steps_from, steps_best, _ = search(TERRAIN, START, GOAL, "steps")    cheap_from, cheap_best, _ = search(TERRAIN, START, GOAL, "cheapest")    steps_path = rebuild_path(steps_from, GOAL)    cheap_path = rebuild_path(cheap_from, GOAL)    assert path_cost(TERRAIN, cheap_path) <= path_cost(TERRAIN, steps_path), (        "TODO 3 or 4 failed: the cheapest route cannot cost more than the BFS route."    )    assert len(steps_path) <= len(cheap_path), (        "TODO 4 failed: with mode 'steps' you must be taking the OLDEST, not the cheapest."    )    assert cheap_best[GOAL] == path_cost(TERRAIN, cheap_path), (        "TODO 4 or 6 failed: best[GOAL] and the path cost must agree."    )    big_heap_from, big_heap_best = search_with_heap(TERRAIN, START, GOAL)    assert big_heap_best[GOAL] == cheap_best[GOAL], (        "TODO 10 failed: heapq must agree with your scan on the real map too."    )MENU = [    "[1]  Fewest steps   (BFS)          - watch what it pays",    "[2]  Cheapest       (Dijkstra)     - watch the cost spread",    "[3]  Race them side by side",    "[4]  The numbers",    "[5]  Every square has a price      - the search with no goal",    "[6]  What can you afford?          - raise the budget and watch",    "[7]  Pick something up on the way  - search() called twice",    "[8]  Let heapq do the scanning     (timed live, on your machine)",    "[q]  Quit",]def show_menu():    clear_screen()    panel(        "THE THIRD TAKE RULE",        "road costs 1, mud costs 5, hill costs 9",        draw_map(TERRAIN, {}, {}),        MENU + ["", terrain_key()],    )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-6 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_search("steps"),        "2": lambda: view_search("cheapest"),        "3": view_race,        "4": view_numbers,        "5": view_cost_map,        "6": view_budget,        "7": view_via,        "8": view_heap,    }    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 checks pass. One of them proves the cheapest route can never cost more than the BFS route — get take_cheapest backwards and it fires immediately.

Optional Upgrades

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

Redraw the terrain

Edit TERRAIN. Keep one S and one G. Try to build a map where BFS and Dijkstra agree.

Add water you cannot cross

A new character with a huge price is almost a wall. Try 999 and see what changes.

Show the price on the path

Print each square of the final route with what it charged, and check they add to the total.

One-way streets on the grid

Make neighbors refuse to walk upward. Only that one function changes.

Teacher Checkpoints

Before any code: ask which is better, a 13-step route or a 19-step route. The right answer is 'it depends what a step costs'.

After TODO 3: ask what take_cheapest returns when two entries tie. Either is fine, and the answer is still correct.

After TODO 4: ask why we never go back and repair a dear entry already in the frontier.

After TODO 6: change hill from 9 to 1 and ask, before running, whether the two routes will now agree.

At the end: ask what BFS really computes on a weighted map. It is still fewest squares — that just stopped being the question.