Scale Conway's Game of Life to a Dense 1M x 1M Board With File-Backed Row Streaming

Conway's Game of Life is played on a grid of cells, each either alive (1) or dead (0). Each generation is computed from the previous one, with every cell updated at the same time: a live cell with two or three live neighbors stays alive, a dead cell with exactly three live neighbors becomes alive, and every other cell is dead in the next generation. A cell's neighbors are the up to eight cells that touch it horizontally, vertically or diagonally. You are given working starter code for a small board. It is roughly equivalent to this: ```python import random class GameOfLife: def __init__(self, rows: int, cols: int, p: float): # every cell starts alive independently with probability p, 0 <= p <= 1 self.rows, self.cols = rows, cols self.board = [[1 if random.random() < p else 0 for _ in range(cols)] for _ in range(rows)] def next_gen(self) -> None: """Replace the board with the next generation.""" new_board = [[0] * self.cols for _ in range(self.rows)] for r in range(self.rows): for c in range(self.cols): self._process_cell(self.board, new_board, r, c) self.board = new_board def _process_cell(self, old_board, new_board, row, col) -> None: """Count the live neighbors of (row, col) in old_board and write the cell's next state to new_board[row][col].""" live = 0 for dr in (-1, 0, 1): for dc in (-1, 0, 1): r, c = row + dr, col + dc if (dr, dc) != (0, 0) and 0 <= r < len(old_board) and 0 <= c < len(old_board[r]): live += old_board[r][c] alive = old_board[row][col] == 1 new_board[row][col] = 1 if live == 3 or (alive and live == 2) else 0 ``` Extend this to a board of 1M × 1M cells (1,000,000 rows and 1,000,000 columns). Because `p` can be anywhere from 0 to 1, the board can be very dense, so storing only the live cells is not an option. The life-and-death rule is already written in `_process_cell` and does not need to change; the task is how the board is stored and how `next_gen` produces the next generation. Details beyond this are given only when asked for, including which resources are available and whether any storage other than memory exists. ### Constraints and Clarifications - `N = 1,000,000`: the board has `N × N = 10^12` cells. - Cells beyond the edge of the board count as dead, as in the starter code's bounds check. - `next_gen` advances the board by exactly one generation. - Reuse `_process_cell` as it is rather than rewriting the rule. ### Clarifying Questions - How much memory does the machine have, and is any storage other than memory available? - Once the board lives outside memory, how is it laid out: one byte per cell, row by row? - Do cells beyond the edge count as dead, or does the board wrap around? - Can the previous generation be discarded once the next one is complete? - Is a single process expected, or may the work be split across several workers? ### Part 1 — Check whether the current design scales Before changing any code, estimate how much memory the starter code needs at 1M × 1M, how that changes with more compact encodings of a cell, and why storing only the live cells does not help here. Conclude what the new design must avoid. ```hint Count the bytes Start from the number of cells, then work out what one cell costs in a list of Python lists, in one byte and in one bit. Remember how many boards `next_gen` holds at once. ``` #### What This Part Should Cover - The cell count and the memory for one board under at least two encodings - The cost of holding the old and the new board at the same time - Why a set of live-cell coordinates is worse than dense storage for a random board ### Part 2 — Design the update window Once you have shown that the board does not fit in memory, the interviewer provides two file-system helpers: ```python def read(name: str, offset: int, length: int) -> bytes: """Return `length` bytes of file `name`, starting at byte `offset`.""" def append(name: str, data: bytes) -> None: """Append `data` to the end of file `name`, creating the file if needed.""" ``` Assume the current generation is stored in one file, row by row, with one byte per cell (0 or 1), so row `r` starts at byte offset `r * N`. Design how to compute the next generation into a new file while holding only a small part of the board in memory. Explain what you keep in memory, in what order you read and write, and how the first and last rows are handled. ```hint What one row depends on Look at which cells `_process_cell` reads to decide one cell. What does it need in order to decide an entire row? ``` ```hint Edges of the window Check what your window holds when you compute the first and the last row, and what `_process_cell` does with a neighbor that falls outside the board it is given. ``` #### What This Part Should Cover - Which old rows each new row depends on, and the window that follows from it - Reading each old row once and appending new rows in order - Handling of the boundary rows and columns - The memory held at any moment ### Part 3 — Implement next_gen on files Write `next_gen`, and the random initialization, against `read` and `append`, reusing `_process_cell` unchanged. Then state the time, memory and I/O of one generation. ```hint Hand the rule a tiny board `_process_cell` only sees the boards and indices you pass it. Decide what you can pass as `old_board` and `new_board` so the rule runs on your window without modification. ``` #### What This Part Should Cover - Correct byte offsets, and new rows appended in order to a fresh output file - Sliding the window so each input row is read exactly once - Row indices passed to `_process_cell` relative to the window - Time, memory and total bytes read and written per generation ### What a Strong Answer Covers - Asks about memory and storage early instead of guessing which algorithm is wanted - A numeric memory estimate that rules out both the in-memory board and sparse storage - A sliding window of three rows with correct edge handling and unchanged reuse of the rule - Working code that uses only `read` and `append` and never writes into the generation it is reading - Where the cost goes, compute time versus I/O, and how to reduce each ### Follow-up Questions - How would you run many generations in a row, and how much disk is needed when `append` is the only way to write? - How would you split one generation across several workers? - How could a single pass over the file compute several generations at once to save I/O? - What changes if the board wraps around at its edges?