Nested Data and Grids

A dictionary field can contain a list. A list item can contain another list. Combining structures lets a program represent relationships, but it also gives us more objects to keep track of.

The useful question is still the same:

What does one item represent, and what information belongs inside it?

A Field Can Contain a List

A reading entry might contain several tags:

entry = {
    "title": "The Quiet Forest",
    "tags": ["fiction", "nature"]
}

print(entry["tags"][0])

The expression retrieves the tags list and then its first item. It prints fiction.

You can give the intermediate object a name:

tags = entry["tags"]
tags.append("short")
assert entry["tags"] == ["fiction", "nature", "short"]

The assignment did not copy the tags. Both access paths reach the same list.

A Shallow Copy Does Not Copy Everything Inside

Predict this example before running it:

entry = {"title": "The Quiet Forest", "tags": ["fiction"]}
other = entry.copy()
other["tags"].append("nature")

print(entry["tags"])

It prints ['fiction', 'nature']. The two dictionaries are different, but both contain a reference to the same tags list.

When a contract requires an independent entry of this known shape, copy the mutable field as well:

def copy_entry(entry):
    return {
        "title": entry["title"],
        "tags": entry["tags"].copy()
    }

Lists also have a .copy() method. Here, copying the outer dictionary and the tags list is enough because the list contains only immutable strings.

This function is not a general-purpose copier of arbitrarily nested data. It copies a structure whose fields we have specified. That makes its responsibility something we can explain and test.

Compare both copying choices in one trace. other is a shallow copy; independent is built with the same dictionary expression as copy_entry. Follow their "tags" references before predicting which lists each append changes.

Apply this reasoning to the nested records below. Follow each lookup one level at a time, and identify which dictionaries and lists are shared before predicting the effects of an update.

Equal contents alone do not show whether two records are independent. In the next exercise, change a copied record’s scores list and check whether the original changes before deciding how to repair the copy.

When Position Describes the Information

Not every relationship needs a field name. A seating plan has rows and seats within those rows:

seats = [
    ["free", "taken", "free"],
    ["taken", "free", "free"]
]

This is a two-dimensional list: the outer list contains rows, and each row is itself a list. For this example, all rows have the same length.

print(seats[0][1])
seats[1][2] = "taken"

The first expression prints taken. The assignment changes the last seat in the second row.

Keep the coordinate convention explicit: seats[row][column]. The row comes first. A graphical framework might use horizontal and vertical coordinates in another order, so do not infer the convention merely from two numbers.

Nested Loops Follow the Structure

To inspect every seat, process each row and then each seat in that row:

This prints 4. The inner loop runs through a complete row each time the outer loop supplies a new row.

Trace the order as positions: first (0, 0), then (0, 1), then (0, 2), followed by the seats in row 1. These coordinate pairs describe the trace; the program above does not need to create tuple values to visit the seats.

The counter starts before both loops because it remembers a count for the whole grid. Putting it inside the outer loop would reset it for each row.

Where you initialize the total determines whether it accumulates across the whole grid or starts again for each row. Check that placement and the order in which the cells are visited before reusing the nested loops.

Counting and rendering can traverse the same grid while accumulating different kinds of results.

Inside a string, "\n" represents a newline character. For example, print("A\nB") displays A and B on separate lines. You can add this character to a text result just as you add any other string.

assert render_grid([[".", "B", "."], ["T", "B", "."]]) == ".B.\nTB.\n"
assert render_grid([["B"], [], [".", "T"]]) == "B\n\n.T\n"
assert render_grid([]) == ""

A Grid Can Be One Field of a Record

Grids appear in more places than seating plans. A spreadsheet is a grid of values, a maze is a grid of tiles, and a small image can be a grid of pixels. The grid can also belong to a larger record.

This avatar record gives the picture a name. In its pixel grid, 1 means a dark pixel and 0 means a light pixel. The nested loop follows the same row-by-row traversal as the seating example, building a line of text for each row:

Run the example, then change one pixel and run it again. The expression avatar["pixels"][1][0] follows three decisions: select the pixels field, select row 1, and select column 0.

The visible picture also makes unwanted sharing easier to notice. If two avatar records share a row, changing one pixel can unexpectedly change both pictures. To make an independent pixel grid of this known shape, create a new outer list and copy each row into it:

copied_pixels = []
for row in avatar["pixels"]:
    copied_pixels.append(row.copy())

This is the same copying decision as the tags example, repeated once for every mutable row.

Create a New Row for Each Position

The following code creates one row and stores it twice:

row = [".", "."]
grid = []
grid.append(row)
grid.append(row)
grid[0][0] = "X"

assert grid[1][0] == "X"

The surprise is not a new rule about grids. It is the same aliasing from Part 3. Both items refer to one row.

Build each row separately when independence is required. This example creates two rows with three cells each:

grid = []

for row_index in range(2):
    grid.append([".", ".", "."])

The list expression inside the loop creates a new row on each iteration. Changing one row now leaves the other unchanged:

grid[0][0] = "X"
assert grid[1] == [".", ".", "."]

The shared-row example above stored the same row twice. The stepper follows the corrected loop with two cells per row: watch a new row appear on each iteration, then predict which row changes when grid[0][0] is updated.

Apply the same idea to a function whose caller chooses the number of rows and columns:

Check Your Understanding

1. Which object does entry["tags"] refer to?
2. Why does copying only the outer dictionary not make a nested list independent?
3. What do the two indexes in seats[row][column] select?
4. When does an inner loop begin again in a grid traversal?
5. Why must each iteration create a new row when the rows should be independent?