Conway's Cellular Automaton Step

medium matrix simulation

Problem

Apply one Game-of-Life step to a board: a live cell with two or three live neighbours stays alive; a dead cell with exactly three live neighbours becomes alive; everything else dies or stays dead. To do it in place, encode transitions in two extra bits — keep the current state in bit 0 and the next state in bit 1, then right-shift every cell at the end. Counting neighbours uses the eight surrounding offsets.

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;
}

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