alexgolec.dev - Reddit Interview Problems: The Game of Life

Suppose you have an M by N board of cells, where each cell is marked as "alive" or "dead." This arrangement of the board is called the "state," and our task is to compute the cells in the next board state according to a set of rules:

- Neighbors: each cell has eight neighbors, up, down, left, right, and along the diagonals.
- Underpopulation: a live cell with zero or one live neighbors becomes dead in the next state.
- Survival: a live cell with exactly two or three live neighbors remains alive in the next state.
- Overpopulation: a live cell with four or more live neighbors becomes dead in the next state.
- Reproduction: a dead cell with exactly three live neighbors becomes alive in the next state.

Visual example of the rules above:
https://alexgolec.dev/content/images/size/w1000/2021/08/Screen-Shot-2021-08-15-at-8.49.29-AM.png

Given an array of arrays representing the board state ( 'x' for alive and '' for "dead"), compute the next state.

---

As another exercise for the reader, consider the problem of ridiculously large boards: instead of a few hundred cells, what if your board had trillions of cells? What if only a small percentage of those cells was populated at any given time? How would your solution change? A few follow ups come to mind:

- The implementations I presented here are dense, meaning they explicitly represent both live and dead cells. If the vast majority of the board is empty, representing dead cells is wasteful. How would you design a sparse implementation, i.e. one which only represents live cells?
- These inputs have edges, beyond which cells cannot be read or written. Can you design an implementation that has no edges and allows cells to be written arbitrarily far out?
- Suppose you were computing more live cells than could reasonably be represented on a single machine. How would you distribute the computation uniformly across nodes? Keep in mind that over multiple iterations dead cells that were nowhere near live ones can eventually become live as live cells "approach" the dead ones.