Grid conventions and direction arrays

A grid problem gives you a map stored as a list of rows: the seats of a cinema, a maze, a game board, the pixels of a picture. A few grid conventions keep that code short and correct. Name every cell by its row first and its column second, grid[r][c], because the first index of a list of lists picks a row. Check that a cell is on the map in one place, in_bounds(r, c), before you read it. Keep the steps to a cell’s neighbours in a direction array, a list of (change in row, change in column) pairs: four of them for up, down, left and right, eight with the diagonals. Then one loop over that list visits every neighbour, and the edges of the map need no special cases. Two more conventions finish the set: number a cell r * cols + c when it has to be a single number, and give every row a list of its own. This lesson shows each convention with code that runs, then solves one problem in full, from the brute force to code in four languages and a stress test that catches a bug.

Rows first, then columns

In grid[r][c], r is the row and grows downwards, from row 0 at the top, and c is the column and grows to the right. rows = len(grid) and cols = len(grid[0]). This is the opposite of the (x, y) order of school maths, where the across direction comes first: a point (x, y) is grid[y][x]. Name the loop variables r and c and the sizes rows and cols, and most swaps become visible as you type them.

Here is a cinema’s seat map, row 0 nearest the screen: '#' is a booked seat, '.' an empty seat and ' ' a gap with no seat, such as an aisle. Both programs read the same cells, then step off each edge of the map:

"""Reading a seat map by (row, column), and what happens at its edges."""

seat_map = [
    "#.# .",  # row 0, nearest the screen
    ".## #",  # row 1
    "#.. .",  # row 2
]
rows, cols = len(seat_map), len(seat_map[0])
print(f"{rows} rows, {cols} columns")


def read(r, c):
    """What seat_map[r][c] gives: the character, or the error it raises."""
    try:
        return repr(seat_map[r][c])
    except IndexError as error:
        return f"IndexError: {error}"


# Row first, then column. The same two numbers swapped ask for row 4.
print("seat_map[1][4] ->", read(1, 4))
print("seat_map[4][1] ->", read(4, 1))

# One step off each edge: below the last row, past the last column, above row 0, left of column 0.
for r, c in [(3, 0), (0, 5), (-1, 0), (0, -1)]:
    print(f"seat_map[{r}][{c}] ->", read(r, c))


def in_bounds(r, c):
    return 0 <= r < rows and 0 <= c < cols


print("in_bounds:", [in_bounds(r, c) for r, c in [(1, 4), (3, 0), (0, 5), (-1, 0), (0, -1)]])

3 rows, 5 columns
seat_map[1][4] -> '#'
seat_map[4][1] -> IndexError: list index out of range
seat_map[3][0] -> IndexError: list index out of range
seat_map[0][5] -> IndexError: string index out of range
seat_map[-1][0] -> '#'
seat_map[0][-1] -> '.'
in_bounds: [True, False, False, False, False]

// Reading a seat map by (row, column), and what happens at its edges.
const seatMap = [
  "#.# .", // row 0, nearest the screen
  ".## #", // row 1
  "#.. .", // row 2
];
const rows = seatMap.length;
const cols = seatMap[0].length;
console.log(`${rows} rows, ${cols} columns`);

// What seatMap[r][c] gives: the character, undefined, or the name of the error it throws.
function read(r, c) {
  try {
    return JSON.stringify(seatMap[r][c]) ?? "undefined";
  } catch (error) {
    return error.name;
  }
}

// Row first, then column. The same two numbers swapped ask for row 4.
console.log("seatMap[1][4] ->", read(1, 4));
console.log("seatMap[4][1] ->", read(4, 1));

// One step off each edge: below the last row, past the last column, above row 0, left of column 0.
for (const [r, c] of [[3, 0], [0, 5], [-1, 0], [0, -1]]) {
  console.log(`seatMap[${r}][${c}] ->`, read(r, c));
}

// at() counts back from the end for a negative index, as Python's indexing does.
console.log("seatMap.at(-1) is row 2:", seatMap.at(-1) === seatMap[2]);

3 rows, 5 columns
seatMap[1][4] -> "#"
seatMap[4][1] -> TypeError
seatMap[3][0] -> TypeError
seatMap[0][5] -> undefined
seatMap[-1][0] -> TypeError
seatMap[0][-1] -> undefined
seatMap.at(-1) is row 2: true

seat_map[1][4] is row 1, column 4, a booked seat. The same two numbers swapped ask for row 4 of a map that has 3 rows, and fail. On a square map they would not fail: they would quietly read another seat. Test grid code on a map that is not square, because swapped indexes and a bound written with rows where cols belongs pass every square test.

The edges behave differently in each language, and the quiet cases are the dangerous ones:

• Python raises IndexError for row 3 and column 5, one step past the end. Row −1 is no error at all: the documentation of sequence operations says that a negative index counts from the end, so seat_map[-1] is the last row and seat_map[0][-1] the last seat of row 0.
• JavaScript gives undefined for a row that does not exist, and reading a seat of undefined throws a TypeError, so rows 3 and −1 fail loudly. A column past either end of a string gives undefined and no error. Only at() counts back from the end, as Python’s indexing does.

So check before you read, in one function:

• in_bounds(r, c) is 0 <= r < rows and 0 <= c < cols. Python reads a chained comparison such as 0 <= r < rows as 0 <= r and r < rows.
• Put the check first in the condition, as in in_bounds(nr, nc) and grid[nr][nc] == '#'. and in Python and && in JavaScript, Java and C++ stop at the first false operand, so the read never happens for a cell off the map.

Direction arrays: 4 and 8 neighbours

A cell’s neighbours sit at fixed steps from it. Each step is a pair (change in row, change in column):

A direction array lists the steps a problem allows: DIRS4 for the four side neighbours, DIRS8 for those four and the four diagonals. One loop then visits every neighbour, and the bounds check drops the steps that leave the map. The words of a statement tell you which list to use. “Adjacent horizontally or vertically”, “shares a side” and “up, down, left or right” mean four directions; “touching”, “including diagonally” and “the eight surrounding cells” mean eight.

"""Direction arrays: the steps to a cell's neighbours, and how many of them a cell has on a 3 x 4 map."""

# (change in row, change in column): up, down, left, right.
DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# The same four, then the four diagonals.
DIRS8 = DIRS4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)]

# The eight steps again, from two loops: every change of -1, 0 or 1, except no change at all.
generated = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if (dr, dc) != (0, 0)]
print("the loops give the same eight steps:", sorted(generated) == sorted(DIRS8))

rows, cols = 3, 4


def in_bounds(r, c):
    return 0 <= r < rows and 0 <= c < cols


def neighbours(r, c, dirs):
    """The cells next to (r, c) that are on the map, in the order of dirs."""
    return [(r + dr, c + dc) for dr, dc in dirs if in_bounds(r + dr, c + dc)]


for name, (r, c) in [("corner", (0, 0)), ("edge", (0, 2)), ("middle", (1, 1))]:
    four, eight = neighbours(r, c, DIRS4), neighbours(r, c, DIRS8)
    print(f"{name} {(r, c)}: {len(four)} of 4, {len(eight)} of 8:", eight)

# Every cell of the map, with the number of neighbours it has (8 directions).
for r in range(rows):
    print(" ".join(str(len(neighbours(r, c, DIRS8))) for c in range(cols)))

the loops give the same eight steps: True
corner (0, 0): 2 of 4, 3 of 8: [(1, 0), (0, 1), (1, 1)]
edge (0, 2): 3 of 4, 5 of 8: [(1, 2), (0, 1), (0, 3), (1, 1), (1, 3)]
middle (1, 1): 4 of 4, 8 of 8: [(0, 1), (2, 1), (1, 0), (1, 2), (0, 0), (0, 2), (2, 0), (2, 2)]
3 5 5 3
5 8 8 5
3 5 5 3

The eight steps are exactly the pairs whose parts are each −1, 0 or 1, except (0, 0), which is the cell itself: the first line of the output checks that two nested loops over −1, 0 and 1 produce the same eight steps as DIRS8. The rest of the output shows what the bounds check does at the edges. A corner keeps 3 of its 8 neighbours, a cell on an edge keeps 5, and a cell inside the map keeps all 8. The same loop handles all three without an if for the corners, which is the point of direction arrays.

Keep the order of the list in mind when the problem fixes one. A robot that turns right is easiest to model with the four directions in clockwise order, up, right, down, left, so that turning right is d = (d + 1) % 4 and turning left is d = (d + 3) % 4.

A problem solved in full: the quietest empty seat

Five examples, which every version of the code below runs:

1. The map from the first section, "#.# .", ".## #", "#.. .", gives (0, 4). The seats (0, 4) and (2, 4) both have one booked neighbour, and row 0 comes first.
2. "##", "##" gives (−1, −1): every seat is booked.
3. A single empty seat, ".", gives (0, 0), with no neighbours at all.
4. One row, "#.#..#", gives (0, 3). The seats (0, 3) and (0, 4) have one booked neighbour each and (0, 1) has two, so the tie goes to (0, 3).
5. One column, "#", ".", "#", ".", gives (3, 0): its one neighbour is booked, while (1, 0) has two booked neighbours.

The brute force: compare every pair of seats

Two seats touch when their rows and their columns are each at most 1 apart, and they are not the same seat. That definition turns straight into code: for each empty seat, look at every seat of the map and count the booked ones that touch it.

"""The quietest empty seat, straight from the definition: compare each empty seat with every seat on the map."""


def quietest_seat_brute(seat_map):
    rows, cols = len(seat_map), len(seat_map[0])
    best, best_count = (-1, -1), None
    for r in range(rows):
        for c in range(cols):
            if seat_map[r][c] != ".":
                continue
            count = 0
            for r2 in range(rows):  # every seat on the map ...
                for c2 in range(cols):
                    # ... counts if it is booked and touches (r, c): row and column each at most 1 away, not (r, c) itself
                    if seat_map[r2][c2] == "#" and max(abs(r2 - r), abs(c2 - c)) == 1:
                        count += 1
            if best_count is None or count < best_count:
                best, best_count = (r, c), count
    return best


if __name__ == "__main__":
    maps = [
        ["#.# .", ".## #", "#.. ."],
        ["##", "##"],
        ["."],
        ["#.#..#"],
        ["#", ".", "#", "."],
    ]
    for seat_map in maps:
        print(quietest_seat_brute(seat_map))
    seats = 1000 * 1000
    print(f"1,000 x 1,000 seats, nearly all empty: about {seats * seats:,} seats read")

(0, 4)
(-1, -1)
(0, 0)
(0, 3)
(3, 0)
1,000 x 1,000 seats, nearly all empty: about 1,000,000,000,000 seats read

It gets all five examples right, and it is far too slow. Each empty seat reads every seat of the map, so a map of rows × cols seats costs up to (rows × cols)² reads: 10¹² at 1,000 × 1,000, the last line of the output. At the rough budgets of the lesson on reading constraints, 10⁸ simple steps a second for compiled code and about 10⁷ for Python, that is close to three hours in C++ and more than a day in Python.

What to notice

The brute force searches the whole map for neighbours, but it never needs to: a seat’s neighbours are always at the same eight steps from it. Generating them with a direction array costs at most 8 reads per empty seat instead of rows × cols.

The direction-array version

1. Start with best = (-1, -1) and best_count = 9, more than any seat can have.
2. Visit the cells in reading order, row by row, each row from left to right.
3. For each empty seat, count the booked seats at the eight steps of DIRS8, skipping every step that leaves the map.
4. If the count is smaller than best_count, this seat becomes best.
5. Return best.

Here is that plan as code in four languages. Press Run to try the Python and JavaScript tabs on this page:

"""The quietest empty seat: look only at the eight seats around each empty seat."""

# (change in row, change in column) to the eight seats around a seat.
DIRS8 = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]


def booked_neighbours(seat_map, r, c):
    """How many of the seats around (r, c) are booked."""
    rows, cols = len(seat_map), len(seat_map[0])
    count = 0
    for dr, dc in DIRS8:
        nr, nc = r + dr, c + dc
        # The bounds check comes first: `and` stops before seat_map[nr][nc] when the step leaves the map.
        if 0 <= nr < rows and 0 <= nc < cols and seat_map[nr][nc] == "#":
            count += 1
    return count


def quietest_seat(seat_map):
    """The empty seat with the fewest booked neighbours; a tie goes to the first one in reading order."""
    best, best_count = (-1, -1), 9  # 9: more than any seat can have
    for r in range(len(seat_map)):
        for c in range(len(seat_map[0])):
            if seat_map[r][c] == ".":
                count = booked_neighbours(seat_map, r, c)
                if count < best_count:  # strictly fewer, so an earlier seat keeps a tie
                    best, best_count = (r, c), count
    return best


if __name__ == "__main__":
    maps = [
        ["#.# .", ".## #", "#.. ."],
        ["##", "##"],
        ["."],
        ["#.#..#"],
        ["#", ".", "#", "."],
    ]
    for seat_map in maps:
        print(quietest_seat(seat_map))

(0, 4)
(-1, -1)
(0, 0)
(0, 3)
(3, 0)

// The quietest empty seat: look only at the eight seats around each empty seat.

// [change in row, change in column] to the eight seats around a seat.
const DIRS8 = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];

// How many of the seats around (r, c) are booked.
function bookedNeighbours(seatMap, r, c) {
  const rows = seatMap.length;
  const cols = seatMap[0].length;
  let count = 0;
  for (const [dr, dc] of DIRS8) {
    const nr = r + dr;
    const nc = c + dc;
    // The bounds check comes first: && stops before seatMap[nr][nc] when the step leaves the map.
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && seatMap[nr][nc] === "#") count++;
  }
  return count;
}

// The empty seat with the fewest booked neighbours; a tie goes to the first one in reading order.
function quietestSeat(seatMap) {
  let best = [-1, -1];
  let bestCount = 9; // more than any seat can have
  for (let r = 0; r < seatMap.length; r++) {
    for (let c = 0; c < seatMap[0].length; c++) {
      if (seatMap[r][c] !== ".") continue;
      const count = bookedNeighbours(seatMap, r, c);
      if (count < bestCount) {
        // strictly fewer, so an earlier seat keeps a tie
        best = [r, c];
        bestCount = count;
      }
    }
  }
  return best;
}

const maps = [
  ["#.# .", ".## #", "#.. ."],
  ["##", "##"],
  ["."],
  ["#.#..#"],
  ["#", ".", "#", "."],
];
for (const seatMap of maps) {
  const [r, c] = quietestSeat(seatMap);
  console.log(`(${r}, ${c})`);
}

(0, 4)
(-1, -1)
(0, 0)
(0, 3)
(3, 0)

// The quietest empty seat: look only at the eight seats around each empty seat.
public class QuietSeat {
    // {change in row, change in column} to the eight seats around a seat.
    static final int[][] DIRS8 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

    // How many of the seats around (r, c) are booked.
    static int bookedNeighbours(String[] seatMap, int r, int c) {
        int rows = seatMap.length, cols = seatMap[0].length();
        int count = 0;
        for (int[] d : DIRS8) {
            int nr = r + d[0], nc = c + d[1];
            // The bounds check comes first: && stops before charAt when the step leaves the map.
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && seatMap[nr].charAt(nc) == '#') count++;
        }
        return count;
    }

    // The empty seat with the fewest booked neighbours; a tie goes to the first one in reading order.
    static int[] quietestSeat(String[] seatMap) {
        int[] best = {-1, -1};
        int bestCount = 9; // more than any seat can have
        for (int r = 0; r < seatMap.length; r++) {
            for (int c = 0; c < seatMap[0].length(); c++) {
                if (seatMap[r].charAt(c) != '.') continue;
                int count = bookedNeighbours(seatMap, r, c);
                if (count < bestCount) { // strictly fewer, so an earlier seat keeps a tie
                    best = new int[] {r, c};
                    bestCount = count;
                }
            }
        }
        return best;
    }

    public static void main(String[] args) {
        String[][] maps = {
            {"#.# .", ".## #", "#.. ."},
            {"##", "##"},
            {"."},
            {"#.#..#"},
            {"#", ".", "#", "."},
        };
        for (String[] seatMap : maps) {
            int[] seat = quietestSeat(seatMap);
            System.out.println("(" + seat[0] + ", " + seat[1] + ")");
        }
    }
}

// The quietest empty seat: look only at the eight seats around each empty seat.
#include <array>
#include <print>
#include <string>
#include <utility>
#include <vector>

// {change in row, change in column} to the eight seats around a seat.
constexpr std::array<std::pair<int, int>, 8> DIRS8{{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}};

// How many of the seats around (r, c) are booked.
int booked_neighbours(const std::vector<std::string>& seat_map, int r, int c) {
    const int rows = static_cast<int>(seat_map.size());
    const int cols = static_cast<int>(seat_map[0].size());
    int count = 0;
    for (const auto& [dr, dc] : DIRS8) {
        const int nr = r + dr, nc = c + dc;
        // The bounds check comes first: && stops before seat_map[nr][nc] when the step leaves the map.
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && seat_map[nr][nc] == '#') ++count;
    }
    return count;
}

// The empty seat with the fewest booked neighbours; a tie goes to the first one in reading order.
std::pair<int, int> quietest_seat(const std::vector<std::string>& seat_map) {
    std::pair<int, int> best{-1, -1};
    int best_count = 9;  // more than any seat can have
    const int rows = static_cast<int>(seat_map.size());
    const int cols = static_cast<int>(seat_map[0].size());
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (seat_map[r][c] != '.') continue;
            const int count = booked_neighbours(seat_map, r, c);
            if (count < best_count) {  // strictly fewer, so an earlier seat keeps a tie
                best = {r, c};
                best_count = count;
            }
        }
    }
    return best;
}

int main() {
    const std::vector<std::vector<std::string>> maps{
        {"#.# .", ".## #", "#.. ."},
        {"##", "##"},
        {"."},
        {"#.#..#"},
        {"#", ".", "#", "."},
    };
    for (const auto& seat_map : maps) {
        const auto [r, c] = quietest_seat(seat_map);
        std::println("({}, {})", r, c);
    }
}

The Java and C++ versions, run as you would run them in a terminal:

"""Runs the Java version, then builds and runs the C++ version."""
from terminal import run

run("""
java --version | head -n 1 | cut -d ' ' -f 1,2
java QuietSeat.java
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined quiet_seat.cpp -o quiet_seat
./quiet_seat
""")

$ java --version | head -n 1 | cut -d ' ' -f 1,2
openjdk 27
$ java QuietSeat.java
(0, 4)
(-1, -1)
(0, 0)
(0, 3)
(3, 0)
$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined quiet_seat.cpp -o quiet_seat
$ ./quiet_seat
(0, 4)
(-1, -1)
(0, 0)
(0, 3)
(3, 0)

All four print the same five answers. A few details differ between the languages:

• Since Java 11 (JEP 330), the java launcher accepts a source file: java QuietSeat.java compiles the class in memory and starts it, with no separate javac step.
• In C++, seat_map[nr] with nr equal to −1 would be undefined behaviour: operator[] checks nothing, and only at() throws std::out_of_range. The bounds check comes first, so that read never happens. The build adds -fsanitize=address,undefined anyway: AddressSanitizer reports out-of-bounds reads while the program runs.
• 9 as the starting count works in every language, because a seat has at most eight neighbours: the first empty seat always replaces it.

Why it is correct

Two facts make the fast version give the brute force’s answer.

1. The counts are the same. The eight steps of DIRS8 are exactly the pairs (dr, dc) with dr and dc each −1, 0 or 1, except (0, 0). Added to (r, c), they give exactly the seats that the brute force accepts as touching. The bounds check removes only the steps that leave the map, which the brute force never looks at, so booked_neighbours returns the brute force’s count for every seat.
2. The tie rule holds. The loop keeps one fact true, its invariant: after each cell, best is the first empty seat in reading order, among those visited so far, with the fewest booked neighbours. A later seat replaces it only with a strictly smaller count, never with an equal one, so the earliest of the tied seats stays. If no seat is empty, nothing replaces (−1, −1).

A dry run

The first map, one empty seat per line, in the order the loop visits them:

1. (0, 1): booked (0, 0), (0, 2), (1, 1) and (1, 2), a count of 4. It is the first empty seat, so best becomes (0, 1) with 4.
2. (0, 4): booked (1, 4) only, a count of 1, fewer than 4, so best becomes (0, 4) with 1.
3. (1, 0): booked (0, 0), (1, 1) and (2, 0), a count of 3, so best stays.
4. (2, 1): booked (1, 1), (1, 2) and (2, 0), a count of 3, so best stays.
5. (2, 2): booked (1, 1) and (1, 2), a count of 2, so best stays.
6. (2, 4): booked (1, 4) only, a count of 1. That ties with best, and a tie never replaces it, so the answer is (0, 4).

For (0, 4), three of the eight steps stay on the map: (0, 3) and (1, 3) are gaps and (1, 4) is booked. The five steps that leave the map are dropped by the bounds check before anything is read.

The cost

At 1,000 × 1,000 the direction-array version reads at most 9 × 10⁶ seats, each seat once in the scan and up to 8 neighbours of each empty seat, against up to 10¹² for the brute force.

Check it against the brute force

The brute-force-to-optimal lesson checks a fast solution against a slow one that is easy to trust. Here that check runs both versions on 2,000 small random maps. It also tries a third version with the eight neighbours written out by hand, the way they are often typed against the clock, and counts how many seats each version reads:

"""Checks quietest_seat against the brute force on random maps, tries a version with the neighbours written out by
hand, and counts how many seats each version reads."""
import random

from brute import quietest_seat_brute
from quiet_seat import quietest_seat


def quietest_seat_by_hand(seat_map):
    """The same search with the eight neighbours written out one by one, and one of them copied wrongly."""
    rows, cols = len(seat_map), len(seat_map[0])

    def booked(r, c):
        return 0 <= r < rows and 0 <= c < cols and seat_map[r][c] == "#"

    best, best_count = (-1, -1), 9
    for r in range(rows):
        for c in range(cols):
            if seat_map[r][c] == ".":
                count = (booked(r - 1, c) + booked(r + 1, c) + booked(r, c - 1) + booked(r, c + 1)
                         + booked(r - 1, c - 1) + booked(r - 1, c + 1) + booked(r + 1, c - 1) + booked(r - 1, c + 1))
                if count < best_count:
                    best, best_count = (r, c), count
    return best


def random_map(rng, rows, cols):
    return ["".join(rng.choice("##.. ") for _ in range(cols)) for _ in range(rows)]


rng = random.Random(15)
maps = [random_map(rng, rng.randint(1, 5), rng.randint(1, 5)) for _ in range(2000)]

agree = sum(quietest_seat(m) == quietest_seat_brute(m) for m in maps)
print(f"quietest_seat agrees with the brute force on {agree:,} of {len(maps):,} maps")

wrong = [m for m in maps if quietest_seat_by_hand(m) != quietest_seat_brute(m)]
smallest = min(wrong, key=lambda m: (len(m) * len(m[0]), m))
print(f"the hand-written version is wrong on {len(wrong)} maps; the smallest:")
for row in smallest:
    print(f"  {row!r}")
print("  by hand:", quietest_seat_by_hand(smallest), " brute force:", quietest_seat_brute(smallest))


class CountingRow(str):
    """A row of a seat map that counts every seat read from it."""

    reads = 0

    def __getitem__(self, index):
        CountingRow.reads += 1
        return super().__getitem__(index)


def seats_read(search, seat_map):
    CountingRow.reads = 0
    search([CountingRow(row) for row in seat_map])
    return CountingRow.reads


for side in (15, 30):
    m = random_map(random.Random(side), side, side)
    print(f"{side} x {side} map: brute force reads {seats_read(quietest_seat_brute, m):,} seats,"
          f" eight neighbours {seats_read(quietest_seat, m):,}")

quietest_seat agrees with the brute force on 2,000 of 2,000 maps
the hand-written version is wrong on 210 maps; the smallest:
  ' #'
  '..'
  by hand: (1, 1)  brute force: (1, 0)
15 x 15 map: brute force reads 22,050 seats, eight neighbours 934
30 x 30 map: brute force reads 329,400 seats, eight neighbours 3,656

The direction-array version agrees with the brute force on all 2,000 maps. The hand-written version is wrong on 210 of them, and the smallest is a map of 2 × 2. Its last term repeats booked(r - 1, c + 1) where booked(r + 1, c + 1) belongs, so the seat (1, 0) counts the booked seat above and to its right twice, and no seat ever looks down and to the right. Eight terms typed by hand hide such a slip well; a list of eight steps written once does not, and a stress test against the brute force exposes the slip on its first run.

The last two lines are counts of the seats each version read. Doubling the side of the map from 15 to 30 multiplies the brute force’s reads by about 15, close to the 16 of (rows × cols)², and the direction array’s by about 4.

Edge cases

• A 1 × 1 map has no neighbours: every step leaves the map, and an empty seat there counts 0.
• A single row or a single column keeps at most 2 of the 8 steps. The bounds check handles it with no special case, and examples 4 and 5 run it.
• No empty seat leaves best at (−1, −1).
• Gaps are neither candidates nor booked seats: the count tests for '#' and the scan for '.'.
• Rows of different lengths are ruled out by the statement. If a problem allows them, cols is len(grid[nr]) for the row you are about to read, so ask about it while you clarify the problem.

Follow-up questions

The guest only cares about the seats directly to the left and right. What changes? Only the direction array: [(0, -1), (0, 1)]. The loop, the bounds check and the tie rule stay as they are, which is one more reason to keep the steps in a list.

Guests now book one seat at a time, and the page shows the quietest seat after every booking. Do you count the whole map again? No. A new booking changes the count of at most eight seats, those around it, so keep the counts in a grid and add 1 to each neighbour of the new booking. Finding the smallest count quickly after each change is a job for a heap, the subject of the heaps and top-K module.

Numbering cells: r × cols + c

Some code needs a cell as one number: a list of rows × cols “seen” flags in a search, the parent array of a union-find, a set of cells in a language whose sets hold numbers more easily than pairs. Number the cells in reading order, index = r * cols + c, and go back with divmod(index, cols), which the Python documentation defines as (index // cols, index % cols) for integers:

"""Numbering the cells of a 3 x 4 map: (r, c) to r * cols + c, and back with divmod."""

rows, cols = 3, 4


def index_of(r, c):
    return r * cols + c


def cell_of(i):
    return divmod(i, cols)  # (i // cols, i % cols)


# Every cell gets its own number, from 0 to rows * cols - 1, in reading order.
for r in range(rows):
    print(" ".join(f"{index_of(r, c):2}" for c in range(cols)))

print("cell 7 is", cell_of(7), "and", cell_of(7), "is cell", index_of(*cell_of(7)))
print("all", rows * cols, "cells survive the round trip:", all(index_of(*cell_of(i)) == i for i in range(rows * cols)))

# Multiplying by rows instead of cols gives two cells one number on a map that is not square.
numbers = {}
for r in range(rows):
    for c in range(cols):
        numbers.setdefault(r * rows + c, []).append((r, c))
print(f"r * rows + c: {len(numbers)} numbers for {rows * cols} cells; shared:",
      {i: cells for i, cells in numbers.items() if len(cells) > 1})

 0  1  2  3
 4  5  6  7
 8  9 10 11
cell 7 is (1, 3) and (1, 3) is cell 7
all 12 cells survive the round trip: True
r * rows + c: 10 numbers for 12 cells; shared: {3: [(0, 3), (1, 0)], 6: [(1, 3), (2, 0)]}

The numbers run from 0 to rows × cols − 1, so a flat list of that length holds one value per cell, and every number turns back into its cell. Multiply by cols, the length of a row, never by rows: the last line shows that r * rows + c gives 10 numbers for 12 cells on this 3 × 4 map, so (0, 3) and (1, 0) share the number 3. On a square map the two formulas agree, which is why the mistake survives square tests.

In Python you can often skip the numbering: the glossary explains that a tuple is hashable when its items are, so (r, c) can go straight into a set or be a dictionary key. Numbering pays off when the cells index a list, and in Java, C++ and Go, where reading an array at a number needs no hashing at all.

Making a grid: a list of its own for every row

A common way to make a grid of zeros in Python looks right and is not:

"""Making a 3 x 4 grid of zeros: one row listed three times, then three rows of their own."""

rows, cols = 3, 4

shared = [[0] * cols] * rows  # the same row object, three times
shared[0][0] = 1
print("shared:", shared)
print("  one row object?", shared[0] is shared[1] is shared[2])

own = [[0] * cols for _ in range(rows)]  # the loop makes a new row on every pass
own[0][0] = 1
print("own:   ", own)
print("  one row object?", own[0] is own[1])

# Copying a grid has the same trap: grid[:] copies the outer list, not the rows.
outer_only = own[:]
outer_only[1][1] = 5
print("own after a change to own[:]:", own)

deep = [row[:] for row in own]  # a copy of every row
deep[2][2] = 7
print("own after a change to a row-by-row copy:", own)

shared: [[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]
  one row object? True
own:    [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
  one row object? False
own after a change to own[:]: [[1, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]]
own after a change to a row-by-row copy: [[1, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]]

// Making a 3 x 4 grid of zeros: one row in every slot, then three rows of their own.
const rows = 3;
const cols = 4;

const shared = new Array(rows).fill(new Array(cols).fill(0)); // fill() puts the same row object in every slot
shared[0][0] = 1;
console.log("shared:", JSON.stringify(shared));
console.log("  one row object?", shared[0] === shared[1] && shared[1] === shared[2]);

const own = Array.from({ length: rows }, () => new Array(cols).fill(0)); // the function makes a new row per slot
own[0][0] = 1;
console.log("own:   ", JSON.stringify(own));
console.log("  one row object?", own[0] === own[1]);

// Copying a grid has the same trap: [...grid] copies the outer array, not the rows.
const outerOnly = [...own];
outerOnly[1][1] = 5;
console.log("own after a change to [...own]:", JSON.stringify(own));

const deep = own.map((row) => [...row]); // a copy of every row
deep[2][2] = 7;
console.log("own after a change to a row-by-row copy:", JSON.stringify(own));

shared: [[1,0,0,0],[1,0,0,0],[1,0,0,0]]
  one row object? true
own:    [[1,0,0,0],[0,0,0,0],[0,0,0,0]]
  one row object? false
own after a change to [...own]: [[1,0,0,0],[0,5,0,0],[0,0,0,0]]
own after a change to a row-by-row copy: [[1,0,0,0],[0,5,0,0],[0,0,0,0]]

[[0] * cols] * rows builds one row and then a list that refers to that same row rows times, three times here. The Python documentation warns about exactly this in its notes on the * operator for sequences: the items are not copied but referred to again, so changing one row changes them all. The output shows the 1 written into row 0 appearing in every row. The comprehension [[0] * cols for _ in range(rows)] runs [0] * cols once per row, so each row is a new list; the Python FAQ answers “How do I create a multidimensional list?” the same way. Repeating the 0 inside a row is safe, because a number is never changed in place: own[0][0] = 1 puts a new value into the slot.

JavaScript has the same trap. MDN’s page on fill() says that when the value is an object, every slot refers to that one object, so new Array(rows).fill(new Array(cols).fill(0)) shares one row too. Array.from({ length: rows }, () => new Array(cols).fill(0)) calls its function once per slot, and each call makes a new row.

Copies hide the same trap: own[:] in Python and [...own] in JavaScript copy the outer list but share the rows, so the 5 written through the copy lands in own as well. A copy of every row, [row[:] for row in own] or own.map((row) => [...row]), leaves own alone, which is what a simulation that builds the next state from the current one needs.

The other languages make separate rows by default:

• Java: new int[rows][cols] makes every row. The language specification shows it is equivalent to creating each row in a loop. Arrays.fill(grid, row) would put one row in every slot, because it assigns the same reference to each element.
• C++: std::vector<std::vector<int>> grid(rows, std::vector<int>(cols)) fills the outer vector with copies of the row, so each row is its own vector.
• Go: make([][]int, rows) and then make([]int, cols) for each row, the first of the two ways that Effective Go shows. Its other way, one large slice cut into rows, also works when rows never grow.

Grids in each language

To sum up, how to make a grid of zeros with rows rows and cols columns, and what one step off the grid does, in each language:

• Python: [[0] * cols for _ in range(rows)]. Index rows or cols raises IndexError, and index −1 reads the last row or column with no error.
• JavaScript: Array.from({ length: rows }, () => new Array(cols).fill(0)). A missing row is undefined, so reading a cell in it throws a TypeError; a missing column gives undefined with no error.
• Java: new int[rows][cols]. The language specification says that an index below 0, or at least the length, throws ArrayIndexOutOfBoundsException.
• C++: std::vector<std::vector<int>> grid(rows, std::vector<int>(cols)). operator[] checks nothing, so a read off the end is undefined behaviour, while at() throws std::out_of_range.
• Go: make([][]int, rows), then make([]int, cols) for each row. The specification says that an index out of range at run time causes a run-time panic.

Exercise

occupied_neighbours(["#.", ".#"])
# [[1, 2], [2, 1]]

DIRS8 = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]


def occupied_neighbours(seat_map):
    """For every cell of the map: how many of the cells around it are booked seats ('#')."""
    # Replace this line with your code.
    return []

import random

from neighbours import occupied_neighbours


def trusted(seat_map):
    """Answers the tests trust: for each cell, look at every cell of the map and count the booked ones that touch it."""
    rows, cols = len(seat_map), len(seat_map[0])
    return [
        [
            sum(seat_map[r2][c2] == "#" and max(abs(r2 - r), abs(c2 - c)) == 1 for r2 in range(rows) for c2 in range(cols))
            for c in range(cols)
        ]
        for r in range(rows)
    ]


def as_lists(result):
    """Accept rows given as lists or tuples."""
    return [list(row) for row in result]


def test_prompt_example():
    """the example from the prompt"""
    assert as_lists(occupied_neighbours(["#.", ".#"])) == [[1, 2], [2, 1]]


def test_one_seat():
    """a 1 x 1 map has no neighbours at all"""
    assert as_lists(occupied_neighbours(["#"])) == [[0]]
    assert as_lists(occupied_neighbours(["."])) == [[0]]


def test_single_row():
    """a map of one row: only the left and right neighbours exist"""
    assert as_lists(occupied_neighbours(["#.#.#"])) == [[0, 2, 0, 2, 0]]


def test_single_column():
    """a map of one column: only the neighbours above and below exist"""
    assert as_lists(occupied_neighbours(["#", "#", "."])) == [[1], [1], [1]]


def test_gaps_count_as_nothing():
    """a gap is not a booked seat, and gaps get counts too"""
    assert as_lists(occupied_neighbours(["# #", "   "])) == [[0, 2, 0], [1, 2, 1]]


def test_wider_than_tall():
    """2 rows of 5 seats: swapped rows and columns fail here"""
    assert as_lists(occupied_neighbours(["#....", "....#"])) == [[0, 1, 0, 1, 1], [1, 1, 0, 1, 0]]


def test_no_wrap_around():
    """booked seats on the far edges: reading row -1 or column -1 would count them"""
    assert as_lists(occupied_neighbours(["...", "...", "###"])) == [[0, 0, 0], [2, 3, 2], [1, 2, 1]]
    assert as_lists(occupied_neighbours(["..#", "..#"])) == [[0, 2, 1], [0, 2, 1]]


def test_rows_are_separate_lists():
    """changing one row of the result must leave the other rows alone"""
    result = occupied_neighbours(["...", "...", "..."])
    result[0][0] = 99
    assert result[1][0] == 0 and result[2][0] == 0


def test_random_maps():
    """300 random maps from 1 x 1 to 6 x 6, against the trusted answers"""
    rng = random.Random(2)
    for _ in range(300):
        rows, cols = rng.randint(1, 6), rng.randint(1, 6)
        seat_map = ["".join(rng.choice("#. ") for _ in range(cols)) for _ in range(rows)]
        assert as_lists(occupied_neighbours(seat_map)) == trusted(seat_map), seat_map


class CountingRow(str):
    """A row of a seat map that counts the seats read from it, and stops a solution that reads too many."""

    reads = 0
    limit = 0

    def __getitem__(self, index):
        CountingRow.reads += len(range(*index.indices(len(self)))) if isinstance(index, slice) else 1
        if CountingRow.reads > CountingRow.limit:
            raise AssertionError(
                f"too slow: more than {CountingRow.limit:,} seats were read from a map of {CountingRow.limit // 10:,}"
                " seats; read only the eight cells around each cell"
            )
        return super().__getitem__(index)


def test_reads_only_neighbours():
    """a 60 x 60 map: at most 10 seats read for each seat on the map"""
    rng = random.Random(60)
    plain = ["".join(rng.choice("#.") for _ in range(60)) for _ in range(60)]
    CountingRow.reads, CountingRow.limit = 0, 10 * 60 * 60
    result = occupied_neighbours([CountingRow(row) for row in plain])
    assert as_lists(result) == trusted(plain)

Interview questions

Why do grid solutions keep the neighbour steps in a direction array instead of writing out each neighbour?

A direction array lists the allowed steps once, as (change in row, change in column) pairs: four for up, down, left and right, eight with the diagonals. One loop over it, with one bounds check, then visits every neighbour, so corners and edges need no special cases. It also prevents slips: eight neighbours written out by hand are eight chances to type a wrong sign, and a wrong sign gives counts that are wrong on only some maps, so it passes most tests. A list written once is easy to check against a diagram. Changing the rule, from 8 neighbours to 4 or to knight moves, then changes only the list, never the loop. The cost is the same as writing the neighbours out: at most eight steps per cell, O(rows × cols) for a whole grid.

How do you turn a cell (r, c) into a single number and back, and when is it useful?

Number the cells in reading order: index = r * cols + c, where cols is the length of a row. The numbers run from 0 to rows × cols − 1, and divmod(index, cols) gives back (r, c). Multiplying by rows instead is a common mistake: on a map that is not square, two cells get the same number, while square tests still pass. The number is useful when a cell must index a flat list or array: “seen” flags in a search, a union-find parent array, a set or map of cells in Java, C++ or Go. In Python, a tuple (r, c) can be a set member or dictionary key directly, so the numbering is optional there.

Key takeaways

• Name cells grid[r][c], row first; rows = len(grid) and cols = len(grid[0]). Test on a map that is not square.
• Check 0 <= r < rows and 0 <= c < cols before every read. Python’s index −1 is the last row, with no error.
• Keep neighbour steps in a direction array, DIRS4 or DIRS8, and loop over it: edges need no special cases.
• A seat’s neighbours are at fixed steps: generating them turned 10¹² reads into at most 9 × 10⁶.
• Number cells r * cols + c and go back with divmod(index, cols).
• Give every row its own list: [[0] * cols for _ in range(rows)] in Python, Array.from in JavaScript, and copy grids row by row.