~/problems / Simulation & OOP design / Simulation

Game of Life: in place, then on an infinite board

medium 2 levels ~45 min Citadel

Level 1 Game of Life, in place

A grid board holds cells that are alive (1) or dead (0). Every cell has up to 8 neighbours (horizontal, vertical, diagonal); cells outside the grid count as dead. One generation later:

  • a live cell with 2 or 3 live neighbours stays alive, otherwise it dies;
  • a dead cell with exactly 3 live neighbours becomes alive, otherwise it stays dead.

All cells update at the same time, based on the old board. Write game_of_life(board) that advances the board by one generation in place and returns None.

  • 1 <= rows, cols <= 50.
  • Don't allocate a second rows x cols grid: use O(1) extra memory (a row or two of scratch space is fine). The classic bug is updating cells one by one and then counting already-updated neighbours.
b = [[0, 1, 0],
     [0, 1, 0],
     [0, 1, 0]]
game_of_life(b)
b   # [[0, 0, 0],
    #  [1, 1, 1],
    #  [0, 0, 0]]
Show hint

each cell only needs to hold 0 or 1, but it can hold any small integer. Could one cell remember both its old state and its new one?

Level 2 unlocks when level 1 passes.

Topic: Simulation. Model the process exactly; watch simultaneous updates and direction arithmetic.

0:00
Ctrl ' run · Ctrl ↵ submit
esc