{x}
blog image

Game of Life

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):

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state of the board is determined by applying the above rules simultaneously to every cell in the current state of the m x n grid board. In this process, births and deaths occur simultaneously.

Given the current state of the board, update the board to reflect its next state.

Note that you do not need to return anything.

 

Example 1:

Input: board = [[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]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

 

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 25
  • board[i][j] is 0 or 1.

 

Follow up:

  • Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
  • In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

Solution Explanation for Game of Life

This problem simulates Conway's Game of Life, updating the state of a cellular automaton based on the number of live neighbors each cell has. The challenge lies in performing the updates simultaneously, without using extra space.

Approach: In-place Marking with Bit Manipulation

The most efficient solution uses in-place marking and avoids creating a copy of the board. We leverage the fact that each cell's value is either 0 or 1. We can cleverly use the least significant bit to represent the current state (0 or 1) and the most significant bit to represent the next state.

Algorithm:

  1. Iteration 1: Count Live Neighbors and Update: Iterate through the board. For each cell:

    • Count the number of live neighbors (using a nested loop to check the 8 adjacent cells).
    • Based on the rules of the game, determine the next state of the cell. We encode this next state in the most significant bit of the cell's value:
      • If the cell is alive (currently 1) and will be dead (2), set its value to 2 (using bitwise operation 10).
      • If the cell is dead (currently 0) and will be alive (-1), set its value to -1 (using bitwise operation -1)

  2. Iteration 2: Update Final State: Iterate through the board again. For each cell, update its value based on the most significant bit:

    • If the most significant bit is set (value is 2 or -1), update the value to reflect the next state (0 or 1 using bitwise AND operations to preserve the least significant bit):

Time and Space Complexity:

  • Time Complexity: O(M * N), where M and N are the dimensions of the board. We iterate through the board twice.
  • Space Complexity: O(1). We perform the updates in-place, using only constant extra space.

Code Example (Python):

def gameOfLife(board):
    m, n = len(board), len(board[0])
    for i in range(m):
        for j in range(n):
            live_neighbors = 0
            for x in range(max(0, i - 1), min(m, i + 2)):
                for y in range(max(0, j - 1), min(n, j + 2)):
                    if (x, y) != (i, j) and board[x][y] & 1:  # Check current state (LSB)
                        live_neighbors += 1
            if board[i][j] & 1:  # Check current state (LSB)
                if live_neighbors < 2 or live_neighbors > 3:
                    board[i][j] |= 2  # Mark for death (set MSB)
            else:
                if live_neighbors == 3:
                    board[i][j] |= 2  # Mark for birth (set MSB)
 
    for i in range(m):
        for j in range(n):
            board[i][j] >>= 1  # Right-shift to reveal next state (LSB)

This Python code directly implements the bit manipulation approach for clarity. Other languages (Java, C++, etc.) would achieve the same using equivalent bitwise operators. Note that the core concept remains consistent across all languages: using the bit pattern to efficiently manage the current and next states within the existing board.