← Back to course
Python 11-12 / Week 05 / Friday
5/6
Week 05 · Grids

Friday

Trace Friday: Neighbors
// The test field as rows and columns
⏱ about 30 min

Friday: Trace Friday: Neighbors

Comet sketches Pip on a cell with four arrows around it. "Next week Pip drives," she says. "From any cell, where can it go?"

Wren adds a column of numbers to his clipboard. "What does the evidence say?" he asks. "Some arrows hit rocks, and some fall off the edge. We should trace every one."

Nova projects one cell glowing, with its four neighbors outlined. "How can I help?" she asks. "Up, down, left and right. Ask is_open about each one."

"Lead programmer," Comet says, "paper first. Then we run it."

Four neighbors

A cell's neighbors are up, down, left and right. Up is row - 1 and down is row + 1. Left is col - 1 and right is col + 1.

Some neighbors are rocks and some are off the edge. is_open checks both. The field is made-up data from the FieldSim story.

Neighbor of (2, 2)CellIn bounds?MarkOpen?
up(1, 2)yes.yes
down(3, 2)yes.yes
left(2, 1)yes.yes
right(2, 3)yes#no
# neighbors.py
from field_data import FIELD
from grid import FieldGrid


def open_neighbors(grid, row, col):
    """Precondition: (row, col) is in bounds.
    Postcondition: gives back the open cells next to it, up, down, left, right."""
    found = []
    for d_row, d_col in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        r = row + d_row
        c = col + d_col
        if grid.is_open(r, c):
            found.append((r, c))
    return found


grid = FieldGrid(FIELD)
print(open_neighbors(grid, 0, 0))
print(open_neighbors(grid, 2, 2))
print(open_neighbors(grid, 4, 5))
assert open_neighbors(grid, 0, 0) == [(1, 0), (0, 1)]
assert len(open_neighbors(grid, 2, 2)) == 3
print("Neighbor tests passed")
TRACE NEIGHBORS.PY
  • Read the question.
  • Tap your answer.
What does open_neighbors(grid, 0, 0) give?
What does open_neighbors(grid, 2, 2) give?
What does open_neighbors(grid, 4, 5) give?
[(1, 0), (0, 1)]
[(1, 2), (3, 2), (2, 1)]
[(3, 5), (4, 4)]
Neighbor tests passed

Column totals

To total a column, swap the loops: the outer loop picks a column, and the inner loop walks down the rows. The cell is still read row first.

# column_counts.py
from field_data import FIELD
from grid import FieldGrid

grid = FieldGrid(FIELD)
for c in range(grid.width()):
    marked = 0
    for r in range(grid.height()):
        if grid.cell(r, c) != ".":
            marked += 1
    print("Column", c, "marked:", marked)
TRACE COLUMN_COUNTS.PY
  • Read the question.
  • Tap your answer.
What does the Column 2 line show?
What does the Column 5 line show?
Column 0 marked: 1
Column 1 marked: 1
Column 2 marked: 2
Column 3 marked: 1
Column 4 marked: 1
Column 5 marked: 2
StatementTrue or false?
In column_counts.py the outer loop walks the columns.?
grid.cell(r, c) still names the row first.?
A corner cell can have four open neighbors.?
The assert lines in neighbors.py are tests.?
WHY THIS EXERCISESwapping the loops changes the walking order, not the indexes, and a corner always loses two neighbors.
At your computer
1. In your fieldsim folder, type neighbors.py and run it. Check the four lines.
2. Add print(open_neighbors(grid, 3, 0)). Trace it on paper first, then run it.
3. Type column_counts.py and run it. Add the six numbers and check the total is 8: 4 rocks plus 4 stars.
  1. A 2D list is a list of lists, one inner list per row.
  2. cells[r][c]: the first index is the row, the second is the column.
  3. Nested loops walk the grid in row-major order. The inner line runs once per cell.
  4. grid.py and field_data.py now live in your fieldsim folder.
  5. Row 5 stops with an IndexError. Row -1 quietly reads the last row.
  6. in_bounds and is_open check before reading, so Pip stays on the field.

Excellent tracing. Tomorrow is a Mission Quest on graph paper.

← Thursday