Tutorial 82026-09-03

The Graph That Changed Twice

Three-hour core plus a 60–90 minute extension bank · references and identity · copy depth · function boundaries · shared-state traps

The Question

By the end: You can copy a graph for an experiment without corrupting the original, explain why a shallow dict copy may still share adjacency lists, and apply the same object model to functions and classes.

Old model

Every variable is a box containing its own private value.

Correct model

Names are bound to objects; several names may reach one object.

Important limit

This is Python's object model, not a promise about exact RAM addresses.

Three-Hour Route

00:00-00:15

The impossible output

Copy a graph for a route experiment, add one edge, then explain why the original graph changes too.

00:15-00:40

Names and objects

Draw the graph dict, its neighbor lists, and the names pointing into that object graph.

00:40-01:05

Mutation and rebinding

Compare appending an edge, replacing one adjacency list, and redirecting a local variable.

01:05-01:35

Copy depth

Copy the graph dict only, each adjacency list, or the complete nested graph state.

01:35-01:45

Break

Before leaving, draw the two shared inner-row arrows in a shallow copy.

01:45-02:10

Across a function call

Track mutable and immutable arguments using Python's call-by-sharing model.

02:10-02:30

Instances, equality and identity

Apply the same model to class instances, then separate == from is.

02:30-02:50

Two famous traps

A tuple containing a list, and a mutable default argument that survives between calls.

02:50-03:00

Exit check

Ten predictions and one memory drawing. Every answer must include a reason.

Bridge From Tutorial 7 — A Graph Is Already An Object Graph

Nothing from the graph lessons is being discarded. We are zooming in on the exact graph, frontier, best and came_from structures used by BFS and Dijkstra, then asking what assignment and copying actually do to them.

python

graph = {    "A": [("B", 4), ("C", 1)],    "B": [("A", 4)],    "C": [("A", 1)],}frontier = [(0, "A", None)]best = {"A": 0}came_from = {"A": None}# Things from the graph lessons were already objects:# graph, frontier, best, came_from     -> mutable containers# "A", "B", "C", 0, 1, 4, None      -> immutable objects# ("B", 4), (0, "A", None)           -> immutable tuple shells# each graph[city]                     -> mutable neighbor list

old graph concept	Python object underneath	new question today
graph	dict -> neighbor lists	Which levels does graph.copy() copy?
frontier	list / deque	Does += mutate the waiting list?
came_from	dict of immutable names	When is a shallow copy sufficient?
(row, col)	tuple of ints	Why can it be a dictionary key?
RoadMap	class instance -> graph dict	Who owns the mutable graph?

trial = graph

Same dict, same neighbor lists.

graphG1

dict G12 keys

"A" → N1["B"]

"B" → N2[]

trialG1

dict G12 keys

"A" → N1["B"]

"B" → N2[]

graph is trial → Truegraph["A"] is trial["A"] → True

trial["A"].append("C")

Opening — Two Attempts To Copy The Graph

Do not run them yet. Both experiments try to add C only to trial_graph. Predict all four lines and explain why even dict.copy() fails to protect graph['A'].

python

graph = {    "A": ["B"],    "B": ["A"],}trial_graph = graphtrial_graph["A"].append("C")print(graph["A"])print(trial_graph is graph)

python

graph = {    "A": ["B"],    "B": ["A"],}trial_graph = graph.copy()trial_graph["A"].append("C")print(graph["A"])print(trial_graph is graph)

Part 1 — One Graph Can Have Several Names

One sentence: Assignment binds a name to an object; it does not put an automatic copy of that object inside the variable.

python

graph = {    "A": ["B", "C"],    "B": ["A"],    "C": ["A"],}trial_graph = graphprint(type(graph))                    # dictprint(graph == trial_graph)           # True: equal contentsprint(graph is trial_graph)           # True: same dict objectprint(graph["A"] is trial_graph["A"]) # True: same neighbor list# The graph is not one object only. It is an object graph:# one dict points to several mutable neighbor-list objects.

Live object map

Create one list

One list, two names, then two lists.

01 / 04

Current line

a = [10, 20]

What Python does

Python creates one list object, then binds the name a to it.

The variable box keeps a reference, not a private copy of the list.

Names

Objects

list L1list

0: 10

1: 20

names -> objects

In the animation, L1 is one adjacency list such as graph['A']. Zooming back out, the graph dict is another mutable object pointing to several lists like L1.

PRACTICE NOW

Finish these before moving to the next idea.

One adjacency list

3 min

Write the exact output.

python

graph = {"A": ["B"], "B": [], "C": []}neighbors = graph["A"]neighbors.append("C")print(graph["A"])

A new neighbor list

4 min

Write both lines, then name the operation that creates the new list.

python

graph = {"A": ["B"]}neighbors = graph["A"]neighbors = neighbors + ["C"]print(graph["A"])print(neighbors)

Part 2 — Mutable and Immutable

kind	common types	meaning
mutable	list · dict · set · class instance	The same object can change while keeping its identity.
immutable	int · float · bool · str · tuple · frozenset · None	An operation must produce another object instead of editing this one.

python

distances = {"A": 0, "B": 4}old_distance = distances["B"]distances["B"] = distances["B"] + 3# The int 4 was not edited. Integers cannot be mutated.# The dict slot for "B" was redirected to the int 7.print(old_distance)             # 4print(distances["B"])          # 7# Graph containers are mutable: dict, list, set, class instances.# Common graph labels are immutable: str, int, coordinate tuple.

python

frontier_entry = ((2, 5), ["A", "C", "F"])# frontier_entry[0] = (3, 5)  # TypeError: tuple slot cannot changefrontier_entry[1].append("G") # valid: the PATH LIST changesprint(frontier_entry)# ((2, 5), ['A', 'C', 'F', 'G'])# The tuple kept the same reference in slot 1.# The mutable path object reached through it changed.

Immutable does not mean every object reachable through it is immutable. The tuple keeps the same reference to the same list; that list is still free to change.

PRACTICE NOW

Finish these before moving to the next idea.

Immutable path cost

3 min

Write the exact output. Was the int 7 changed?

python

path_cost = 7old_cost = path_costpath_cost += 1print(old_cost, path_cost)

TODO 6

boost(score, amount)

Purpose

Compute and return an increased integer score.

Input

score: int; amount: int

Output / Return

The integer score + amount.

State change

No object is mutated; integers are immutable.

Checkpoint

python

score = 40result = boost(score, 7)assert score == 40assert result == 47

Part 3 — Mutation Is Not Rebinding

Read each line aloud before running it. Say either 'edit the object' or 'redirect the name'. This predicts whether an alias can see the result.

python

graph = {"A": ["B"], "B": ["A"], "C": []}neighbors = graph["A"]neighbors.append("C")          # MUTATE the shared neighbor listprint(graph["A"])              # ['B', 'C']neighbors = neighbors + ["D"]  # NEW list; rebind local name onlyprint(graph["A"])              # still ['B', 'C']graph["A"] = graph["A"] + ["D"]# NEW list, then mutate the graph dict by replacing value at key 'A'print(graph["A"])              # ['B', 'C', 'D']

Mutate: append, extend, sort, clear, set.add, item assignment

New object + rebind: +, slicing, sorted(), list comprehension, ordinary assignment

PRACTICE NOW

Finish these before moving to the next idea.

TODO 1

alias_and_append(values, item)

Purpose

Create a second name for values, append item through it, and return it.

Input

values: list; item: any value

Output / Return

Return the exact same list object as values.

State change

values gains item at the end.

Checkpoint

python

source = [1, 2]result = alias_and_append(source, 3)assert source == [1, 2, 3]assert result is source

Part 4 — Alias, Shallow Copy, Deep Copy

Question to ask: Not 'did I copy it?', but 'which levels became independent, and which inner objects are still shared?'

You already saw this on the adjacency dictionary above: graph.copy() copies the outer dict but shares the inner neighbor lists. The board below is the same object shape as a grid graph, so use it to test the rule in another representation.

test = board

board

test

outer shared · rows shared

test[0][0] = "X"

expression	outer	nested mutable objects	when it fits
clone = original	shared	shared	You deliberately want one object with two names.
clone = original.copy()	new	shared	Flat data, or shared inner objects are intended.
clone = original[:]	new	shared	A shallow copy of a list only.
clone = copy.copy(original)	new	shared	A general shallow copy, including a class instance.
clone = copy.deepcopy(original)	new	new	Nested mutable state must be independent.

Deep copy is not automatically better. It does more work and may copy state you intended to share. Choose it when nested mutable state must be independent.

PRACTICE NOW

Finish these before moving to the next idea.

New outer graph

4 min

Adding a new key changes which dictionary?

python

graph = {"A": ["B"], "B": ["A"]}trial = graph.copy()trial["C"] = []print(len(graph), len(trial))

Shallow graph, not enough

5 min

Write both lines and identify the shared object.

python

graph = {"A": ["B"], "B": []}trial = graph.copy()trial["A"].append("C")print(graph["A"])print(trial["A"])

Independent graph

4 min

Write graph['A'] after editing the copied graph.

python

import copygraph = {"A": ["B"], "B": []}trial = copy.deepcopy(graph)trial["A"].append("C")print(graph["A"])

Shallow dictionary copy

5 min

Write the two printed values and draw the shared list.

python

player = {"name": "Nova", "items": ["key"]}clone = player.copy()clone["name"] = "Echo"clone["items"].append("map")print(player["name"])print(player["items"])

TODO G1

copy_adjacency_lists(graph)

Purpose

Copy the graph dict and copy every neighbor list inside it.

Input

graph: dict mapping each node to a flat neighbor list

Output / Return

An equal graph with a new dict and new neighbor lists.

State change

The input graph must not change.

Checkpoint

python

graph = {"A": ["B"], "B": ["A"]}trial = copy_adjacency_lists(graph)trial["A"].append("C")assert graph == {"A": ["B"], "B": ["A"]}assert trial["A"] is not graph["A"]

TODO G2

graph_with_edge(graph, start, end)

Purpose

Return an independent graph containing one extra directed edge.

Input

graph: adjacency dict; start and end: existing node names

Output / Return

A copied graph in which end appears at the end of trial[start].

State change

Do not modify graph or any of its neighbor lists.

Checkpoint

python

graph = {"A": ["B"], "B": [], "C": []}trial = graph_with_edge(graph, "A", "C")assert graph["A"] == ["B"]assert trial["A"] == ["B", "C"]

TODO G5

shares_neighbors(first, second, node)

Purpose

Detect whether two graphs share the exact neighbor list for one node.

Input

first and second: graph dicts; node: a key in both

Output / Return

True only when first[node] is second[node].

State change

Nothing changes.

Checkpoint

python

graph = {"A": ["B"]}shallow = graph.copy()independent = copy_adjacency_lists(graph)assert shares_neighbors(graph, shallow, "A") is Trueassert shares_neighbors(graph, independent, "A") is False

TODO 2

copied_append(values, item)

Purpose

Make a shallow copy, append item to the copy, and return the copy.

Input

values: flat list; item: any value

Output / Return

A new list containing the old items followed by item.

State change

The input list remains unchanged.

Checkpoint

python

source = [1, 2]result = copied_append(source, 3)assert source == [1, 2]assert result == [1, 2, 3]assert result is not source

TODO 3

shallow_clone(matrix)

Purpose

Copy only the outer list of a matrix.

Input

matrix: a list of row lists

Output / Return

A new outer list whose rows are shared with matrix.

State change

Do not modify matrix or its rows.

Checkpoint

python

matrix = [[1, 2], [3, 4]]clone = shallow_clone(matrix)assert clone is not matrixassert clone[0] is matrix[0]

TODO 4

deep_clone(matrix)

Purpose

Create a fully independent nested copy with copy.deepcopy().

Input

matrix: a list containing mutable row lists

Output / Return

A new matrix with new row objects and equal values.

State change

Do not modify the input matrix.

Checkpoint

python

matrix = [[1, 2], [3, 4]]clone = deep_clone(matrix)clone[0][0] = 99assert matrix[0][0] == 1assert clone[0] is not matrix[0]

TODO 14

same_row(first, second, index)

Purpose

Detect whether two nested lists share one row object.

Input

first, second: nested lists; index: valid row index

Output / Return

True only when first[index] is second[index].

State change

Nothing changes.

Checkpoint

python

matrix = [[1], [2]]shallow = matrix.copy()deep = copy.deepcopy(matrix)assert same_row(matrix, shallow, 0) is Trueassert same_row(matrix, deep, 0) is False

Tutorial 1

Color Sort hint

A flat board of immutable strings

python

test_board = board.copy()swap_blocks(test_board, i, j)# board and test_board are different outer lists.# Their strings may be shared safely because strings cannot mutate.

Explain

Why is a shallow copy enough here?

Tutorial 5–7

Graph adjacency lists

A dictionary whose values are mutable lists

python

trial_graph = {    node: neighbors.copy()    for node, neighbors in graph.items()}trial_graph["A"].append("X")# graph["A"] remains unchanged.

Explain

What would trial_graph = graph.copy() still share?

Part 5 — What Crosses A Function Call

Accurate wording: Python passes an object reference by assigning it to the parameter name. This is often called call by sharing.

python

def add_directed_edge(graph, start, end):    graph[start].append(end)       # mutate caller's neighbor listdef with_extra_cost(cost, amount):    cost = cost + amount           # rebind only this local name    return cost                    # send the new int reference backroads = {"A": ["B"], "B": [], "C": []}path_cost = 4add_directed_edge(roads, "A", "C")path_cost = with_extra_cost(path_cost, 3)print(roads["A"])                 # ['B', 'C']print(path_cost)                   # 7

1 · bind

The parameter starts by reaching the caller's object.

2 · execute

Mutation is shared; rebinding stays local.

3 · return

A returned reference can be assigned back by the caller.

PRACTICE NOW

Finish these before moving to the next idea.

A function adds an edge

4 min

Write the output and underline the mutating line.

python

def add_edge(graph, start, end):    graph[start].append(end)roads = {"A": [], "B": []}add_edge(roads, "A", "B")print(roads)

A function rebinds locally

5 min

Why does this not add B to roads['A']?

python

def add_edge(graph, start, end):    neighbors = graph[start]    neighbors = neighbors + [end]roads = {"A": [], "B": []}add_edge(roads, "A", "B")print(roads["A"])

TODO G3

add_undirected_edge(graph, one, two)

Purpose

Mutate one graph by adding the road in both directions.

Input

graph: adjacency dict; one and two: existing node names

Output / Return

Return None.

State change

Append two to graph[one] and one to graph[two].

Checkpoint

python

graph = {"A": [], "B": []}result = add_undirected_edge(graph, "A", "B")assert result is Noneassert graph == {"A": ["B"], "B": ["A"]}

TODO 5

heal(stats, amount)

Purpose

Mutate stats['hp'] by amount without exceeding stats['max_hp'].

Input

stats: dict with hp and max_hp; amount: non-negative int

Output / Return

Return None.

State change

hp becomes min(old hp + amount, max_hp).

Checkpoint

python

stats = {"hp": 80, "max_hp": 100}result = heal(stats, 50)assert result is Noneassert stats == {"hp": 100, "max_hp": 100}

Part 6 — Class Instances Obey The Same Rules

python

class RoadMap:    def __init__(self, name, graph):        self.name = name        self.graph = graph    def add_road(self, start, end):        self.graph[start].append(end)roads = {"A": ["B"], "B": [], "C": []}sydney = RoadMap("Sydney", roads)planner = sydneyplanner.add_road("A", "C")print(sydney.graph["A"])           # ['B', 'C']print(sydney is planner)            # True# self is a parameter that reaches the RoadMap instance.

There is no special class-only memory rule. hero, partner and self are names. The Fighter instance, its integer hp and its inventory list are objects connected by references.

PRACTICE NOW

Finish these before moving to the next idea.

TODO G6

clone_network(network, new_name)

Purpose

Deep-copy a Network so route experiments cannot affect the original.

Input

network: Network instance; new_name: str

Output / Return

A new Network with new_name and an independent graph.

State change

The original Network and graph must not change.

Checkpoint

python

network = Network("Sydney", {"A": ["B"], "B": []})trial = clone_network(network, "Roadworks Test")trial.graph["A"].append("C")assert network.name == "Sydney"assert network.graph["A"] == ["B"]assert trial.name == "Roadworks Test"

TODO 9

clone_fighter(fighter, new_name)

Purpose

Deep-copy a Fighter, rename the clone, and keep inventories independent.

Input

fighter: Fighter instance; new_name: str

Output / Return

A new Fighter with equal hp, new_name, and an independent inventory.

State change

The original fighter must not change.

Checkpoint

python

hero = Fighter("Nova", 80, ["key"])clone = clone_fighter(hero, "Echo")clone.inventory.append("map")assert hero.name == "Nova"assert hero.inventory == ["key"]assert clone.name == "Echo"assert clone.inventory == ["key", "map"]

Tutorial 3

Battle save state

An instance containing mutable inventory

python

snapshot = copy.deepcopy(hero)hero.hp -= 30hero.inventory.append("crystal")print(snapshot.hp)          # old hpprint(snapshot.inventory)   # old inventory

Explain

Why can copy.copy(hero) still be dangerous?

Part 7 — == Asks Value, is Asks Identity

python

first = {"A": ["B"], "B": []}second = {"A": ["B"], "B": []}alias = firstprint(first == second)   # True: equal graph contentsprint(first is second)   # False: separate dict objectsprint(first is alias)    # True: one graph, two names# Use == to compare graph values.# Use is to ask whether two names reach the exact same object.

a == b

Do these objects represent equal values?

a is b

Are these references to the exact same object?

PRACTICE NOW

Finish these before moving to the next idea.

Equal graphs or one graph

5 min

Write all three booleans in order.

python

a = {"A": ["B"], "B": []}b = {"A": ["B"], "B": []}c = aprint(a == b)print(a is b)print(a is c)

TODO 7

compare_objects(first, second)

Purpose

Report value equality and object identity separately.

Input

first and second: any two Python objects

Output / Return

A pair: (first == second, first is second).

State change

Nothing changes.

Checkpoint

python

a = [1, 2]b = [1, 2]assert compare_objects(a, b) == (True, False)assert compare_objects(a, a) == (True, True)

Part 8 — The Mutable Default Trap

Default argument expressions run when def executes, not once per call. A default list can therefore remember every earlier call.

Shared by accident

python

def add_city(city, graph={}):   # graph is created ONCE    graph[city] = []    return graphprint(add_city("A"))              # {'A': []}print(add_city("B"))              # {'A': [], 'B': []}

Fresh when omitted

python

def add_city(city, graph=None):    if graph is None:        graph = {}                 # fresh graph for this call    graph[city] = []    return graphprint(add_city("A"))              # {'A': []}print(add_city("B"))              # {'B': []}

PRACTICE NOW

Finish these before moving to the next idea.

The graph that remembers

6 min

Predict both lines, then repair the function without clear().

python

def add_city(city, graph={}):    graph[city] = []    return graphprint(add_city("A"))print(add_city("B"))

TODO 8

add_badge(badge, badges=None)

Purpose

Use None so omitted calls never share a default list.

Input

badge: str; badges: optional list of strings

Output / Return

The supplied list, or a fresh list, with badge appended.

State change

A supplied list mutates; omitted calls use separate lists.

Checkpoint

python

first = add_badge("A")second = add_badge("B")assert first == ["A"]assert second == ["B"]assert first is not second

Part 9 — += Can Mean Mutation

Do not guess from the symbol: For a mutable list, += normally extends the existing object. For an immutable tuple or integer, += has to create another object and rebind the name.

python

graph = {"A": ["B"], "B": [], "C": []}neighbors = graph["A"]neighbors += ["C"]             # list.__iadd__: mutate shared listprint(graph["A"])              # ['B', 'C']graph = {"A": ["B"], "B": [], "C": []}neighbors = graph["A"]neighbors = neighbors + ["C"]  # list.__add__: build new listprint(graph["A"])              # ['B'] — graph still has old list# Same symbols, different object operation.

This is why replacing test_board = board with test_board += [] does not repair the old hint function. The object is still shared. You need a real copy.

PRACTICE NOW

Finish these before moving to the next idea.

The in-place plus

4 min

Write both lines. Is b still an alias after +=?

python

a = [1]b = ab += [2]print(a)print(a is b)

Plus without equals

4 min

Change only += to = +. What changes in the output?

python

a = [1]b = ab = b + [2]print(a)print(a is b)

TODO 10

extend_in_place(values, extra)

Purpose

Use += to extend values and prove the returned value is the same list.

Input

values: list; extra: list

Output / Return

The exact values object after extension.

State change

values gains every item from extra.

Checkpoint

python

source = [1, 2]result = extend_in_place(source, [3, 4])assert source == [1, 2, 3, 4]assert result is source

Part 10 — Repetition Repeats References

Sequence multiplication does not rerun the expression that created each item. It repeats the references already inside the sequence. Immutable zeros are harmless; one repeated mutable row is not.

python

# A grid is another representation of a graph:# each open cell is a node, and nearby cells are connected.# WRONG: repeat one row reference three timesgrid = [[0] * 3] * 3grid[0][0] = 9print(grid)# [[9, 0, 0], [9, 0, 0], [9, 0, 0]]# RIGHT: create a separate row object each timegrid = [[0] * 3 for _ in range(3)]grid[0][0] = 9print(grid)# [[9, 0, 0], [0, 0, 0], [0, 0, 0]]

Program

grid = [[0] * 3] * 3
grid[0][0] = 9

Three outer slots all reach ROW1.

Independent version

grid = [[0] * 3 for _ in range(3)]

grid[0]grid[1]grid[2]

↘ ↓ ↙

ROW1

[0, 0, 0]

PRACTICE NOW

Finish these before moving to the next idea.

Three rows or one?

5 min

Write the whole grid and count the distinct row objects.

python

grid = [[0, 0]] * 3grid[1][0] = 7print(grid)print(grid[0] is grid[2])

Rows made separately

5 min

Compare this with Question 13.

python

grid = [[0, 0] for _ in range(3)]grid[1][0] = 7print(grid)print(grid[0] is grid[2])

TODO 11

make_grid(rows, cols, fill)

Purpose

Build a grid whose row lists are all independent.

Input

rows, cols: non-negative ints; fill: immutable value

Output / Return

A rows-by-cols nested list filled with fill.

State change

No input changes; changing one output row must not change another.

Checkpoint

python

grid = make_grid(3, 2, 0)grid[0][0] = 9assert grid == [[9, 0], [0, 0], [0, 0]]assert grid[0] is not grid[1]

Tutorial 5

Maze experiment

A nested list needs independent rows

python

trial = [row.copy() for row in maze]trial[2][3] = "#"# New outer list, and every row expression makes a new row.# This copies exactly two levels without copying immutable cells.

Explain

Why would trial = maze.copy() be insufficient?

Part 11 — del Removes A Route, Not Necessarily An Object

python

graph = {"A": ["B"], "B": ["A"]}search_graph = graphdel graph                 # remove the NAME, not the dict objectprint(search_graph["A"]) # ['B'] — search_graph still reaches itdel search_graph["B"]     # different: mutate the dict itselfprint(search_graph)       # {'A': ['B']}search_graph = None       # the old graph is now unreachable here# Python may reclaim an unreachable object automatically.

del name

Remove one name binding.

del values[0]

Mutate a container by removing one slot.

unreachable

Python may reclaim the object automatically.

PRACTICE NOW

Finish these before moving to the next idea.

Delete a name

4 min

Does del a destroy the list? Write the output.

python

a = [4, 5]b = adel ab.append(6)print(b)

Part 12 — Returning State Is An Ownership Decision

API question: When a method returns a list, is the caller allowed to edit the real internal list, or should it receive a snapshot? Both designs can be correct, but the contract must say which one.

python

class RoadMap:    def __init__(self, graph):        self.graph = graph    def neighbors_live(self, city):        return self.graph[city]          # caller can edit my graph    def neighbors_copy(self, city):        return self.graph[city].copy()   # caller gets a snapshotroads = RoadMap({"A": ["B"], "B": []})leaked = roads.neighbors_live("A")leaked.append("C")print(roads.graph["A"])                 # ['B', 'C']safe = roads.neighbors_copy("A")safe.append("D")print(roads.graph["A"])                 # still ['B', 'C']

Live reference: fast and intentional when callers are allowed to mutate shared state.

Defensive copy: protects internal state, but has a time and memory cost.

PRACTICE NOW

Finish these before moving to the next idea.

A returned live list

5 min

Write the output and identify who owns the changed list.

python

def get_items(player):    return player["items"]hero = {"items": ["key"]}outside = get_items(hero)outside.append("map")print(hero["items"])

A defensive snapshot

5 min

Write the output. Which operation breaks the sharing?

python

def get_items(player):    return player["items"].copy()hero = {"items": ["key"]}outside = get_items(hero)outside.append("map")print(hero["items"])

TODO G4

neighbors_snapshot(graph, node)

Purpose

Return an immutable snapshot of one node's current neighbors.

Input

graph: adjacency dict; node: an existing key

Output / Return

A tuple containing graph[node]'s current values.

State change

Nothing changes; later graph edits cannot rewrite the tuple.

Checkpoint

python

graph = {"A": ["B"]}snapshot = neighbors_snapshot(graph, "A")graph["A"].append("C")assert snapshot == ("B",)assert graph["A"] == ["B", "C"]

TODO 12

inventory_snapshot(fighter)

Purpose

Return an immutable snapshot of the current inventory.

Input

fighter: Fighter whose inventory is a list

Output / Return

A tuple containing the current inventory items.

State change

The fighter and inventory remain unchanged.

Checkpoint

python

hero = Fighter("Nova", 80, ["key"])snapshot = inventory_snapshot(hero)hero.inventory.append("map")assert snapshot == ("key",)assert hero.inventory == ["key", "map"]

TODO 13

safe_inventory(fighter)

Purpose

Return a list the caller may edit without changing the Fighter.

Input

fighter: Fighter with a flat list of string items

Output / Return

A shallow copy of fighter.inventory.

State change

The Fighter must not change when the returned list changes.

Checkpoint

python

hero = Fighter("Nova", 80, ["key"])outside = safe_inventory(hero)outside.append("map")assert hero.inventory == ["key"]assert outside == ["key", "map"]

Tutorial 1 & 3

Undo history

A history must freeze the old state

python

# Flat board:history.append(board.copy())# Nested mutable game state:history.append(copy.deepcopy(game_state))# Appending the live object itself is not a snapshot.

Explain

What goes wrong with history.append(board)?

Part 13 — Class Attributes May Be Shared

An attribute written in the class body belongs to the class. If it is a mutable list, every instance can find the same list. Per-player state belongs in __init__ on self.

python

class BrokenMap:    graph = {}                   # ONE dict stored on the classsydney = BrokenMap()melbourne = BrokenMap()sydney.graph["A"] = ["B"]print(melbourne.graph)           # {'A': ['B']} — shared by accidentclass RoadMap:    def __init__(self):        self.graph = {}          # one fresh dict per map instancex = RoadMap()y = RoadMap()x.graph["A"] = ["B"]print(y.graph)                   # {}

Class attributes are useful for true shared constants such as MAX_HP = 100. The danger is mutable per-instance state such as inventory = [] or history = {}.

PRACTICE NOW

Finish these before moving to the next idea.

Shared class state

5 min

Write both lines. Why does beta have a key?

python

class Player:    items = []alpha = Player()beta = Player()alpha.items.append("key")print(alpha.items)print(beta.items)

Independent instance state

5 min

Move items into __init__. Write both outputs.

python

class Player:    def __init__(self):        self.items = []alpha = Player()beta = Player()alpha.items.append("key")print(alpha.items)print(beta.items)

TODO 15

Team(name)

Purpose

Give every Team instance its own fresh members list.

Input

name: str passed to the constructor

Output / Return

A Team with that name and an empty members list.

State change

Adding to one team's members must not affect another team.

Checkpoint

python

red = Team("red")blue = Team("blue")red.members.append("Nova")assert red.members == ["Nova"]assert blue.members == []assert red.members is not blue.members

Part 14 — Classes Can Define Value Equality

python

class City:    def __init__(self, name, position):        self.name = name        self.position = position    def __eq__(self, other):        if not isinstance(other, City):            return NotImplemented        return self.name == other.name and self.position == other.positiona = City("Library", (2, 5))b = City("Library", (2, 5))print(a == b)       # True: __eq__ compared node dataprint(a is b)       # False: two separate City objects

Without __eq__, two ordinary instances usually compare by identity. __eq__ gives == a value rule. is remains an identity test and cannot be redefined.

PRACTICE NOW

Finish these before moving to the next idea.

Equality can be taught

6 min

Write both booleans. Which method answers the first question?

python

class Card:    def __init__(self, rank):        self.rank = rank    def __eq__(self, other):        return isinstance(other, Card) and self.rank == other.ranka = Card(7)b = Card(7)print(a == b)print(a is b)

Part 15 — Why Dictionary Keys Cannot Be Lists

Stable location: Dictionary keys and set members use a hash to choose a storage position. A mutable list could change after insertion, so Python refuses to hash it.

python

prices = {"road": 1, (2, 5): 9}# Dictionary keys and set members need a stable hash.# Immutable values are often hashable.print(prices[(2, 5)])       # 9# A list can change after insertion, so it is not hashable.# prices[[2, 5]] = 9        # TypeError: unhashable type: 'list'# A tuple is hashable only when every item inside is hashable.good = ("room", 3)bad = ("room", [3])print(hash(good))# print(hash(bad))          # TypeError because the inner list is unhashable

PRACTICE NOW

Finish these before moving to the next idea.

A key must stay stable

5 min

Name the exception raised on the final line and explain why.

python

visited = {(2, 5)}print((2, 5) in visited)position = [2, 5]print(position in visited)

Tutorial 6–7

Coordinates as keys

Why search uses (row, col)

python

cell = (2, 5)came_from[cell] = (2, 4)best[cell] = 17# A tuple of ints is immutable and hashable.# [2, 5] cannot be a dict key.

Explain

What property makes the tuple safe as a dictionary key?

Main Graph Work Area

Continue the old graph: The adjacency dictionary is already familiar. The new work is deciding exactly which object each operation may change.

graph_copy_work.py

python

import copyclass Network:    def __init__(self, name, graph):        self.name = name        self.graph = graphdef copy_adjacency_lists(graph):    # TODO G1    # New dict, and a new neighbor list for every node.    passdef graph_with_edge(graph, start, end):    # TODO G2    # Return an independent graph with one extra directed edge.    passdef add_undirected_edge(graph, one, two):    # TODO G3    # Mutate graph in both directions. Return None.    passdef neighbors_snapshot(graph, node):    # TODO G4    # Return the current neighbors as a tuple.    passdef shares_neighbors(first, second, node):    # TODO G5    # Test the identity of the two neighbor lists.    passdef clone_network(network, new_name):    # TODO G6    # Deep-copy the Network, rename the copy, and return it.    pass

graph_copy_practice.py

python

import copyclass Network:    def __init__(self, name, graph):        self.name = name        self.graph = graphdef copy_adjacency_lists(graph):    # TODO G1    # New dict, and a new neighbor list for every node.    passdef graph_with_edge(graph, start, end):    # TODO G2    # Return an independent graph with one extra directed edge.    passdef add_undirected_edge(graph, one, two):    # TODO G3    # Mutate graph in both directions. Return None.    passdef neighbors_snapshot(graph, node):    # TODO G4    # Return the current neighbors as a tuple.    passdef shares_neighbors(first, second, node):    # TODO G5    # Test the identity of the two neighbor lists.    passdef clone_network(network, new_name):    # TODO G6    # Deep-copy the Network, rename the copy, and return it.    passdef run_graph_checks():    graph = {"A": ["B"], "B": ["A"]}    trial = copy_adjacency_lists(graph)    trial["A"].append("C")    assert graph == {"A": ["B"], "B": ["A"]}    assert trial["A"] is not graph["A"]    graph = {"A": ["B"], "B": [], "C": []}    trial = graph_with_edge(graph, "A", "C")    assert graph["A"] == ["B"]    assert trial["A"] == ["B", "C"]    graph = {"A": [], "B": []}    assert add_undirected_edge(graph, "A", "B") is None    assert graph == {"A": ["B"], "B": ["A"]}    graph = {"A": ["B"]}    snapshot = neighbors_snapshot(graph, "A")    graph["A"].append("C")    assert snapshot == ("B",)    graph = {"A": ["B"]}    shallow = graph.copy()    independent = copy_adjacency_lists(graph)    assert shares_neighbors(graph, shallow, "A") is True    assert shares_neighbors(graph, independent, "A") is False    network = Network("Sydney", {"A": ["B"], "B": []})    trial = clone_network(network, "Roadworks Test")    trial.graph["A"].append("C")    assert network.name == "Sydney"    assert network.graph["A"] == ["B"]    assert trial.name == "Roadworks Test"    assert trial.graph["A"] == ["B", "C"]    print("6/6 graph checks passed")if __name__ == "__main__":    run_graph_checks()

Student Work Area

Only edit this part: Nine short definitions, no game loop and no UI code. Complete one TODO, run its checkpoint, then continue.

student_work.py

python

import copyclass Fighter:    def __init__(self, name, hp, inventory):        self.name = name        self.hp = hp        self.inventory = inventorydef alias_and_append(values, item):    # TODO 1    # Return the SAME list after appending item through an alias.    passdef copied_append(values, item):    # TODO 2    # Return a NEW list with item appended. Do not change values.    passdef shallow_clone(matrix):    # TODO 3    # Return a new outer list whose inner rows remain shared.    passdef deep_clone(matrix):    # TODO 4    # Return a fully independent nested copy.    passdef heal(stats, amount):    # TODO 5    # Mutate stats["hp"]. Cap it at stats["max_hp"]. Return None.    passdef boost(score, amount):    # TODO 6    # Return the increased integer.    passdef compare_objects(first, second):    # TODO 7    # Return (equal values, same object).    passdef add_badge(badge, badges=None):    # TODO 8    # When badges is omitted, create a fresh list for this call.    passdef clone_fighter(fighter, new_name):    # TODO 9    # Deep-copy fighter, rename the copy, and return it.    pass

Practice Template

This is the student area with all nine automatic checks attached. The final message appears only when every reference and copy contract is correct.

reference_practice.py

python

import copyclass Fighter:    def __init__(self, name, hp, inventory):        self.name = name        self.hp = hp        self.inventory = inventorydef alias_and_append(values, item):    # TODO 1    # Return the SAME list after appending item through an alias.    passdef copied_append(values, item):    # TODO 2    # Return a NEW list with item appended. Do not change values.    passdef shallow_clone(matrix):    # TODO 3    # Return a new outer list whose inner rows remain shared.    passdef deep_clone(matrix):    # TODO 4    # Return a fully independent nested copy.    passdef heal(stats, amount):    # TODO 5    # Mutate stats["hp"]. Cap it at stats["max_hp"]. Return None.    passdef boost(score, amount):    # TODO 6    # Return the increased integer.    passdef compare_objects(first, second):    # TODO 7    # Return (equal values, same object).    passdef add_badge(badge, badges=None):    # TODO 8    # When badges is omitted, create a fresh list for this call.    passdef clone_fighter(fighter, new_name):    # TODO 9    # Deep-copy fighter, rename the copy, and return it.    passdef run_checks():    source = [1, 2]    result = alias_and_append(source, 3)    assert source == [1, 2, 3]    assert result is source    source = [1, 2]    result = copied_append(source, 3)    assert source == [1, 2]    assert result == [1, 2, 3]    assert result is not source    matrix = [[1, 2], [3, 4]]    shallow = shallow_clone(matrix)    assert shallow is not matrix    assert shallow[0] is matrix[0]    deep = deep_clone(matrix)    deep[0][0] = 99    assert matrix[0][0] == 1    assert deep[0] is not matrix[0]    stats = {"hp": 80, "max_hp": 100}    assert heal(stats, 50) is None    assert stats == {"hp": 100, "max_hp": 100}    score = 40    assert boost(score, 7) == 47    assert score == 40    a = [1, 2]    b = [1, 2]    assert compare_objects(a, b) == (True, False)    assert compare_objects(a, a) == (True, True)    first = add_badge("A")    second = add_badge("B")    assert first == ["A"]    assert second == ["B"]    assert first is not second    supplied = []    assert add_badge("VIP", supplied) is supplied    assert supplied == ["VIP"]    hero = Fighter("Nova", 80, ["key"])    clone = clone_fighter(hero, "Echo")    clone.inventory.append("map")    assert hero.name == "Nova"    assert hero.inventory == ["key"]    assert clone.name == "Echo"    assert clone.hp == 80    assert clone.inventory == ["key", "map"]    assert clone is not hero    print("9/9 checks passed")if __name__ == "__main__":    run_checks()

bash

python3 reference_practice.py

Extension Work Area and Template

Reserve material: Use TODO 10–15 when the core work finishes early, or assign them after class. They have a separate 6/6 check so the core 9/9 file stays small.

extension_work.py

python

def extend_in_place(values, extra):    # TODO 10    # Use += and return the SAME list object.    passdef make_grid(rows, cols, fill):    # TODO 11    # Every row list must be a separate object.    passdef inventory_snapshot(fighter):    # TODO 12    # Return the current inventory as a tuple.    passdef safe_inventory(fighter):    # TODO 13    # Return a list the caller may edit safely.    passdef same_row(first, second, index):    # TODO 14    # Return whether the two rows are the exact same object.    passclass Team:    def __init__(self, name):        # TODO 15        # Store name and create a fresh members list.        pass

reference_extension.py

python

import copyclass Fighter:    def __init__(self, name, hp, inventory):        self.name = name        self.hp = hp        self.inventory = inventorydef extend_in_place(values, extra):    # TODO 10    # Use += and return the SAME list object.    passdef make_grid(rows, cols, fill):    # TODO 11    # Every row list must be a separate object.    passdef inventory_snapshot(fighter):    # TODO 12    # Return the current inventory as a tuple.    passdef safe_inventory(fighter):    # TODO 13    # Return a list the caller may edit safely.    passdef same_row(first, second, index):    # TODO 14    # Return whether the two rows are the exact same object.    passclass Team:    def __init__(self, name):        # TODO 15        # Store name and create a fresh members list.        passdef run_extension_checks():    source = [1, 2]    result = extend_in_place(source, [3, 4])    assert source == [1, 2, 3, 4]    assert result is source    grid = make_grid(3, 2, 0)    grid[0][0] = 9    assert grid == [[9, 0], [0, 0], [0, 0]]    assert grid[0] is not grid[1]    hero = Fighter("Nova", 80, ["key"])    snapshot = inventory_snapshot(hero)    hero.inventory.append("map")    assert snapshot == ("key",)    outside = safe_inventory(hero)    outside.append("coin")    assert hero.inventory == ["key", "map"]    assert outside == ["key", "map", "coin"]    matrix = [[1], [2]]    shallow = matrix.copy()    deep = copy.deepcopy(matrix)    assert same_row(matrix, shallow, 0) is True    assert same_row(matrix, deep, 0) is False    red = Team("red")    blue = Team("blue")    red.members.append("Nova")    assert red.name == "red"    assert red.members == ["Nova"]    assert blue.members == []    assert red.members is not blue.members    print("6/6 extension checks passed")if __name__ == "__main__":    run_extension_checks()

Final Model

01Names are bound to objects.

02Assignment copies a reference.

03Mutation changes an object.

04Rebinding redirects one name.

05Shallow copy leaves inner objects shared.

06Function parameters obey the same rules.

07== compares value; is compares identity.

08Copy depth is a design decision.

09Repetition can repeat one mutable reference.

10Returning a container defines an ownership boundary.

11Per-instance mutable state belongs on self.

12Hashable keys need stable values.

Teacher Checkpoints

Ask: after b = a, how many lists exist? Do not continue until the answer is one.

Before each line in Part 3, require the student to say mutate or rebind.

A shallow matrix drawing must show four objects: two outer lists and two shared rows.

Do not accept 'lists pass by reference'. The parameter gets the same object reference, then the function mutates that object.

Finish by returning to test_board = board from the old hint function and repairing it without help.