I started a new game, and the old board changed too

See the problem

Your noughts and crosses game keeps an empty board, EMPTY, and each new game starts from a copy of it. You test one game: X plays the top-left corner.

Then you press “New game”. The new board already has an X in the corner. So does every game after it. Your “copy” wasn’t one.

Define the task

• Input: a template board: a list of rows, each a list of cells.
• Output: a new board equal to the template, sharing nothing with it.
• Rules: changing any cell of the new board leaves the template alone.
• The hard part: a copy can be new on the outside and shared on the inside.

Example: game = new_game(EMPTY), then game[0][0] = "X". EMPTY[0][0] is still " ".

Pause and think

⏸ Pause and think

EMPTY.copy() makes a new list. What does the new list hold: new rows, or the same rows?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

board = EMPTY makes a second name for the same list. Nothing is copied.

Hint 2 of 3

EMPTY.copy() makes a new outer list holding the same three row objects.

Hint 3 of 3

copy.deepcopy(EMPTY) copies the rows too, and anything inside them.

Understand the idea

== compares values. is compares objects. Two separate lists can be equal (== is True) without being the same object (is is False). is asks “are these two names on one object?”. Use it for None, True, False and markers you made yourself.

A shallow copy makes a new container and puts the same items in it. list.copy(), lst[:], list(lst), dict(d) and copy.copy(x) are all shallow. For a list of numbers, that’s a full copy. For a list of lists, the rows are shared.

A deep copy, copy.deepcopy(x), copies the container and everything inside it, all the way down.

Step through it. shallow is a new list, but its rows are the rows of empty, so the X shows up in both. deep has rows of its own.

A shallow copy shares the rows

⤢ Full view

Names

none yet

Objects

no lists, dicts or tuples yet

• → #2 points to object #2
• changed by this line
• nothing points to it

Step 1 of 8. Before the first line runs, there are no names and no objects.

◀ BackPlayNext ▶Reset Ask me first Show as text

1empty = [[" ", " "], [" ", " "]]
2shallow = empty.copy()
3shallow[0][0] = "X"
4import copy
5deep = copy.deepcopy(empty)
6deep[1][0] = "O"
7print(shallow is empty, shallow[0] is empty[0], deep[1] is empty[1])

Try your own input

Python, one line per rowempty = [[" ", " "], [" ", " "]] shallow = empty.copy() shallow[0][0] = "X" import copy deep = copy.deepcopy(empty) deep[1][0] = "O" print(shallow is empty, shallow[0] is empty[0], deep[1] is empty[1])

Use numbers, text, lists, dicts and tuples. It knows =, +=, del, print(), comparisons, slices, comprehensions, the common list methods, sorted(), list(), dict(), tuple(), range(), and copy.deepcopy() after import copy.

Show it

★Key insight

== asks “equal?”; is asks “the same object?”. A shallow copy is new only on the outside. When the items inside can change, copy them too, with copy.deepcopy.

Climb the ladder

Here n is the number of cells on the board.

Okay

Assign it

The idea: board = template, then return board.

Each game starts with an empty board, the first time.

EMPTY = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


def new_game(template: list[list[str]]) -> list[list[str]]:
    board = template  # a second name for the same board, not a copy
    return board

Time

O(1)

Space

O(1)

Why

Nothing is copied.

Where it breaks: = never copies. game is EMPTY, so every move lands on the template.

Better

A shallow copy

The idea: Return template.copy(): a new outer list.

The waste in Okay: no copy at all.

Adding or removing rows now leaves the template alone.

Highlighted lines are new in this rung.

EMPTY = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


def new_game(template: list[list[str]]) -> list[list[str]]:
    return template.copy()  # a new outer list, but the same three rows inside

Time

O(rows)

Space

O(rows)

Why

Copies one reference per row.

What changed from the previous rung

EMPTY = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


def new_game(template: list[list[str]]) -> list[list[str]]:
    board = template  # a second name for the same board, not a copy
    return board
    return template.copy()  # a new outer list, but the same three rows inside

Where it breaks: the rows inside are shared. game[0][0] = "X" changes EMPTY[0], which is the same list.

Best

copy.deepcopy

The idea: Copy the outer list, every row, and anything inside them.

The waste in Better: a copy that is new only on the outside.

deepcopy works however deep the data goes, and copies a shared object once, so shapes stay the same.

Highlighted lines are new in this rung.

import copy

EMPTY = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


def new_game(template: list[list[str]]) -> list[list[str]]:
    return copy.deepcopy(template)  # new lists all the way down

Time

O(n)

Space

O(n)

Why

Every cell is visited and copied.

What changed from the previous rung

import copy

EMPTY = [[" ", " ", " "], [" ", " ", " "], [" ", " ", " "]]


def new_game(template: list[list[str]]) -> list[list[str]]:
    return template.copy()  # a new outer list, but the same three rows inside
    return copy.deepcopy(template)  # new lists all the way down

When Best isn’t best: deepcopy is slow, because it checks every object. For exactly two levels, [row[:] for row in template] is several times faster.

Write it yourself

Write new_game(template). The tests change the copy, then look at the template.

A board that shares nothing

Ctrl + Enter runs

import copy def new_game(template): return template

Run testsReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: X plays in the copy: the template → [[' ', ' '], [' ', ' ']]
2. ○Not run yet: a row added to the copy: the template → [[1]]
3. ○Not run yet: is the copy equal? → True
4. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

new_game()Run onceVisualize

Compare

Way	New outer list	New rows	Deeper	Use it when
Okay: =	No	No	No	You want a second name, not a copy
Better: .copy(), [:]	Yes	No	No	The items can’t change: numbers, strings
[row[:] for row in t]	Yes	Yes	No	Exactly two levels, and speed matters
Best: copy.deepcopy	Yes	Yes	Yes	Nested data you will change

Common mistakes and edge cases

![[0] * 3] * 3 shares one row

* on a list repeats references. [[0] * 3] * 3 is three names for one row, so setting board[0][0] changes every row. Build each row on its own: [[0] * 3 for _ in range(3)].

• x is None, not x == None: a class can make == say anything, but there is only one None.
• Don’t use is for numbers or strings: a is b can be True for small ints and short strings, because CPython reuses them, and False for others. Use ==.
• id(x) is a number unique to an object while it is alive. Two names with the same id are on one object.
• Tuples copy cheaply: copy.copy of a tuple returns the same tuple, because it can’t change. But a tuple holding a list can still change inside.
• A function argument is not a copy: the function gets the same object, so changing it changes the caller’s.

Say it in the interview

Questions to ask first

• Will anything inside be changed, or only replaced?
• How deep does the data go, and how big is it?

A 60-second walkthrough

“Assignment never copies; it gives the same object a second name. list.copy() or a slice makes a shallow copy: a new outer list holding the same items. For a board of rows, the rows are shared, so writing a cell in the copy changes the template. copy.deepcopy copies recursively and keeps shared objects shared within the copy. It’s O(n) in the size of the data, and slower than a two-level list comprehension, which I’d use if I know the shape. And is is for identity, like is None; == is for values.”

Likely follow-ups

• How does deepcopy handle a list that contains itself? It keeps a memo of objects already copied, so cycles and shared parts are copied once.
• How do you make a class copy itself properly? Define __copy__ and __deepcopy__.
• Why does a is b give True for 256 and False for 257 built at run time? CPython keeps one object for each int from -5 to 256.

Practice

Three problems, from easy to hard. Each has hints, tests you can run here, and its own Okay, Better and Best answers. Try before you open them.

1. Missing or not (easy)

describe(value) returns "missing" when value is None, and "present" for anything else, including 0, "" and [].

Hint 1 of 3

if not value treats 0 and "" as missing.

Hint 2 of 3

value == None can be tricked by a class that says it equals everything.

Hint 3 of 3

value is None checks for the one None object.

Missing or not

Ctrl + Enter runs

def describe(value: object) -> str: if not value: # 0, "" and [] are falsy too return "missing" return "present"

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: describe(None) → 'missing'
2. ○Not run yet: describe('ana') → 'present'
3. ○Not run yet: describe(0) → 'present'
4. ○Not run yet: describe('') → 'present'
5. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

describe()Run onceVisualize

Show the Okay, Better and Best answers

Okay

== None

The idea: Compare the value to None with ==.

Right for every built-in type.

def describe(value: object) -> str:
    if value == None:  # noqa: E711  (the rung's flaw: == can be overridden)
        return "missing"
    return "present"

Time

O(1)

Space

O(1)

Why

One comparison.

Where it breaks: == calls the object’s __eq__, which can say anything. Linters flag it as E711.

Better

if not value

The idea: Treat anything falsy as missing.

The waste in Okay: it asks the object, which may lie.

Highlighted lines are new in this rung.

def describe(value: object) -> str:
    if not value:  # 0, "" and [] are falsy too
        return "missing"
    return "present"

Time

O(1)

Space

O(1)

Why

One truth test.

What changed from the previous rung

def describe(value: object) -> str:
    if value == None:  # noqa: E711  (the rung's flaw: == can be overridden)
    if not value:  # 0, "" and [] are falsy too
        return "missing"
    return "present"

Where it breaks: 0, "" and [] are falsy too, so a price of 0 is called missing.

Best

is None

The idea: Ask whether value is the None object.

The waste in Better: it lumps real values in with missing ones.

Highlighted lines are new in this rung.

def describe(value: object) -> str:
    if value is None:  # there is only one None, so ask "is it that object?"
        return "missing"
    return "present"

Time

O(1)

Space

O(1)

Why

One identity check.

What changed from the previous rung

def describe(value: object) -> str:
    if not value:  # 0, "" and [] are falsy too
    if value is None:  # there is only one None, so ask "is it that object?"
        return "missing"
    return "present"

When Best isn’t best: when None is a real value too, use your own marker, like MISSING = object(), and check is MISSING.

2. Settings that don’t leak (medium)

make_settings(overrides) starts from DEFAULTS and applies the overrides. Each user must get settings of their own: adding a tag for one user must not change another user’s tags, or DEFAULTS.

Hint 1 of 3

settings = DEFAULTS is the same dict.

Hint 2 of 3

dict(DEFAULTS) is a new dict, but its "tags" list is shared.

Hint 3 of 3

copy.deepcopy(DEFAULTS) copies the list too.

Settings that don’t leak

Ctrl + Enter runs

DEFAULTS = {"theme": "light", "tags": ["new"]} def make_settings(overrides: dict | None = None) -> dict: settings = DEFAULTS # the same dict for every user settings.update(overrides or {}) return settings

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: ana gets a dark theme and a vip tag; then a new user → {'theme': 'light', 'tags': ['new']}
2. ○Not run yet: make_settings({'theme': 'dark'}) → {'theme': 'dark', 'tags': ['new']}
3. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

make_settings()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Use DEFAULTS

The idea: settings = DEFAULTS, then update it.

The first user gets the right settings.

DEFAULTS = {"theme": "light", "tags": ["new"]}


def make_settings(overrides: dict | None = None) -> dict:
    settings = DEFAULTS  # the same dict for every user
    settings.update(overrides or {})
    return settings

Time

O(k)

Space

O(1)

Why

update() copies k overrides into the one shared dict.

Where it breaks: every user gets the same dict. One user’s dark theme becomes everyone’s.

Better

dict(DEFAULTS)

The idea: Make a new dict, then update it.

The waste in Okay: no copy at all.

Themes no longer leak.

Highlighted lines are new in this rung.

DEFAULTS = {"theme": "light", "tags": ["new"]}


def make_settings(overrides: dict | None = None) -> dict:
    settings = dict(DEFAULTS)  # a new dict, but the same "tags" list inside
    settings.update(overrides or {})
    return settings

Time

O(s + k)

Space

O(s)

Why

Copies the s top-level settings.

What changed from the previous rung

DEFAULTS = {"theme": "light", "tags": ["new"]}


def make_settings(overrides: dict | None = None) -> dict:
    settings = DEFAULTS  # the same dict for every user
    settings = dict(DEFAULTS)  # a new dict, but the same "tags" list inside
    settings.update(overrides or {})
    return settings

Where it breaks: the copy is shallow. Every user’s "tags" is the one list in DEFAULTS, so ana’s "vip" tag appears for everyone.

Best

copy.deepcopy

The idea: Deep-copy DEFAULTS, then update it.

The waste in Better: it shares the one part that people change.

Highlighted lines are new in this rung.

import copy

DEFAULTS = {"theme": "light", "tags": ["new"]}


def make_settings(overrides: dict | None = None) -> dict:
    settings = copy.deepcopy(DEFAULTS)  # nothing shared with DEFAULTS
    settings.update(overrides or {})
    return settings

Time

O(s + k)

Space

O(s)

Why

Copies every value in the s settings.

What changed from the previous rung

import copy

DEFAULTS = {"theme": "light", "tags": ["new"]}


def make_settings(overrides: dict | None = None) -> dict:
    settings = dict(DEFAULTS)  # a new dict, but the same "tags" list inside
    settings = copy.deepcopy(DEFAULTS)  # nothing shared with DEFAULTS
    settings.update(overrides or {})
    return settings

When Best isn’t best: make defaults that can’t change, like a tuple for tags, or build them fresh in a function. Then a shallow copy is enough.

3. Find the shared rows (hard)

A board made with [[" "] * 3] * 3 has one row three times. Write shared_rows(board), which returns groups of row numbers that are the same object, like [[0, 1, 2]]. Rows that are only equal don’t count. It must be fast on 40,000 rows.

Hint 1 of 3

== finds equal rows. You want the same object: is.

Hint 2 of 3

Comparing each row with every other is O(n²).

Hint 3 of 3

id(row) is unique for each object alive now. Group row numbers by id in a dict.

Find the shared rows

Ctrl + Enter runs

def shared_rows(board): return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: shared_rows([[" "] * 3] * 3) → [[0, 1, 2]]
2. ○Not run yet: shared_rows([[0], [0]]): equal, not shared → []
3. ○Not run yet: shared_rows([a, b, a, [1], b]) → [[0, 2], [1, 4]]
4. ○Not run yet: shared_rows(40,000 separate rows) → []

Try your own input

Arguments, separated by commas as in Python

shared_rows()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Group equal rows

The idea: Put each row in the first group whose row is == to it.

It finds the [[" "] * 3] * 3 rows.

def shared_rows(board: list[list]) -> list[list[int]]:
    groups: list[list[int]] = []
    for i, row in enumerate(board):
        for group in groups:
            if board[group[0]] == row:  # equal values, not the same object
                group.append(i)
                break
        else:
            groups.append([i])
    return [g for g in groups if len(g) > 1]

Time

O(n × g)

Space

O(n)

Why

Each row is compared with up to g groups.

Where it breaks: two separate rows that happen to be equal are grouped too. And 40,000 rows is far too slow.

Better

Group with is

The idea: The same loops, but compare rows with is.

The waste in Okay: it asks the wrong question.

Highlighted lines are new in this rung.

def shared_rows(board: list[list]) -> list[list[int]]:
    groups: list[list[int]] = []
    for i, row in enumerate(board):
        for group in groups:  # compares with every group so far: O(n²)
            if board[group[0]] is row:
                group.append(i)
                break
        else:
            groups.append([i])
    return [g for g in groups if len(g) > 1]

Time

O(n²)

Space

O(n)

Why

With no shared rows, each row is checked against every group so far.

What changed from the previous rung

def shared_rows(board: list[list]) -> list[list[int]]:
    groups: list[list[int]] = []
    for i, row in enumerate(board):
        for group in groups:
            if board[group[0]] == row:  # equal values, not the same object
        for group in groups:  # compares with every group so far: O(n²)
            if board[group[0]] is row:
                group.append(i)
                break
        else:
            groups.append([i])
    return [g for g in groups if len(g) > 1]

Where it breaks: 40,000 rows is about 800 million checks, and the test runs out of time.

Best

A dict keyed by id

The idea: Add each row number to by_object[id(row)], then keep groups of two or more.

The waste in Better: a search where a look-up would do.

Highlighted lines are new in this rung.

def shared_rows(board: list[list]) -> list[list[int]]:
    by_object: dict[int, list[int]] = {}
    for i, row in enumerate(board):
        # id() is unique for each object alive now, and the board keeps them alive
        by_object.setdefault(id(row), []).append(i)
    return [g for g in by_object.values() if len(g) > 1]

Time

O(n)

Space

O(n)

Why

One dict step per row.

What changed from the previous rung

def shared_rows(board: list[list]) -> list[list[int]]:
    groups: list[list[int]] = []
    by_object: dict[int, list[int]] = {}
    for i, row in enumerate(board):
        for group in groups:  # compares with every group so far: O(n²)
            if board[group[0]] is row:
                group.append(i)
                break
        else:
            groups.append([i])
    return [g for g in groups if len(g) > 1]
        # id() is unique for each object alive now, and the board keeps them alive
        by_object.setdefault(id(row), []).append(i)
    return [g for g in by_object.values() if len(g) > 1]

When Best isn’t best: an id can be reused once its object is freed. So only compare ids of objects that are all still alive, like rows held by one board.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputWhat does this print?

   a = [[0], [0]]
   b = a.copy()
   b[0].append(1)
   b.append([2])
   print(a)

   [[0], [0]][[0, 1], [0]][[0, 1], [0], [2]][[0], [0], [2]]

   Check answer
2. Predict the outputWhat does this print?

   board = [[0] * 2] * 2
   board[0][0] = 9
   print(board)

   [[9, 0], [0, 0]][[9, 0], [9, 0]][[9, 9], [0, 0]]An error

   Check answer
3. Multiple choiceWhich is the right way to check for None?

   x == Nonex is Nonenot xx is False

   Check answer
4. Predict the outputWhat does this print?

   a = [1, 2]
   b = [1, 2]
   print(a == b, a is b)

   True TrueTrue FalseFalse FalseFalse True

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1What is the difference between == and is?Show answer
• Card 2What does a shallow copy share with the original?Show answer
• Card 3How do you copy a list of lists so nothing is shared?Show answer
• Card 4Why does [[0] * 3] * 3 go wrong?Show answer

Add 4 cards to my review deck

Cheat sheet

• == equal values; is same object. x is None.
• b = a: no copy. a.copy(), a[:], dict(d): shallow.
• copy.deepcopy(x): copies everything inside.
• [[0] * 3 for _ in range(3)], never [[0] * 3] * 3.
• id(x): unique while the object is alive.

Go deeper

• copy, shallow and deep copies.
• Comparisons, including is.
• Before this: Mutability. Next: Logging.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Say when to use is and when to use ==, and why x is None is the rule
• Predict what a shallow copy shares, for list.copy(), list[:], dict() and copy.copy
• Copy nested data with copy.deepcopy, and say when a cheaper copy is enough
• Spot the [[0] * 3] * 3 bug, and find shared objects with id()

✓Mark as completeI already know this

Status: Not started