Game of Life

medium matrix simulation

Problem

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970." The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation.

Input[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]

Output[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Classic blinker → glider transition.

board (rows ';', cells ',', 0/1)

def game_of_life(board):
    m, n = len(board), len(board[0])
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    for r in range(m):
        for c in range(n):
            live = 0
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and board[nr][nc] & 1:
                    live += 1
            cur = board[r][c] & 1
            nxt = 1 if (cur == 1 and live in (2, 3)) or (cur == 0 and live == 3) else 0
            board[r][c] |= nxt << 1
    for r in range(m):
        for c in range(n):
            board[r][c] >>= 1

function gameOfLife(board) {
  const m = board.length, n = board[0].length;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      let live = 0;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && (board[nr][nc] & 1) === 1) live++;
      }
      const cur = board[r][c] & 1;
      const next = (cur === 1 && (live === 2 || live === 3)) || (cur === 0 && live === 3) ? 1 : 0;
      board[r][c] |= (next << 1);
    }
  }
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) board[r][c] >>= 1;
  }
}

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int live = 0;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && (board[nr][nc] & 1) == 1) live++;
                }
                int cur = board[r][c] & 1;
                int next = ((cur == 1 && (live == 2 || live == 3)) || (cur == 0 && live == 3)) ? 1 : 0;
                board[r][c] |= (next << 1);
            }
        }
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) board[r][c] >>= 1;
    }
}

void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    for (int r = 0; r < m; ++r) {
        for (int c = 0; c < n; ++c) {
            int live = 0;
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && (board[nr][nc] & 1)) live++;
            }
            int cur = board[r][c] & 1;
            int nx = ((cur == 1 && (live == 2 || live == 3)) || (cur == 0 && live == 3)) ? 1 : 0;
            board[r][c] |= (nx << 1);
        }
    }
    for (int r = 0; r < m; ++r)
        for (int c = 0; c < n; ++c) board[r][c] >>= 1;
}

Explanation

The tricky part of Game of Life is that every cell's next state depends on its current neighbors, so if you overwrite cells as you go you would corrupt the answers for nearby cells. The clever fix here updates the board in place using a bit trick, so no second copy of the grid is needed.

Each cell stores its state in bit 0 (the current value) and we use bit 1 to remember the next value. To read the current value we use board[r][c] & 1, which ignores whatever we stash in the higher bit.

For every cell we count its live neighbors among the 8 surrounding cells using the dirs list of offsets, checking the bounds so edge cells don't read outside the grid. We apply the rules to get nxt (1 if it survives or is born, else 0), then do board[r][c] |= nxt << 1 to write that next state into bit 1 while leaving bit 0 untouched.

After the whole grid is processed, a second pass does board[r][c] >>= 1 on every cell, which drops the old current value and slides the next value down into bit 0 — turning the encoded board into the real next generation.

Example: a live cell with 2 live neighbors survives, so its cell goes from 1 (binary 01) to 11 after the OR; the final right shift turns 11 into 1. A dead cell that stays dead simply ends up 0.

Time: O(m · n) Space: O(1)