Game of Life

Updated on 30 May, 2025
Game of Life header image

Problem Statement

The Game of Life is a cellular automaton envisioned by John Horton Conway in 1970, often used to illustrate complex systems and emergent behaviors through simple rules. The game is structured as a grid (m x n), where every cell holds a binary state, indicating "live" (1) or "dead" (0). Each cell's fate in the next iteration of the game is determined by its current state along with the states of its eight neighboring cells.

The transition rules are:

  1. A live cell with fewer than two live neighbors dies, simulating under-population.
  2. A live cell with two or three live neighbors will survive to the next generation.
  3. A live cell with more than three live neighbors will die, depicting over-population.
  4. A dead cell with exactly three live neighbors becomes alive, representing reproduction.

The task is to update the game board to its next state based on the rules applied simultaneously across all cells.

Examples

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.

Approach and Intuition

Understanding the problem involves analyzing how each cell interacts with its neighbors and affects the overall board state over time. The complexity arises because the update of one cell might affect the conditions for updating its neighboring cells. However, the problem stipulates that all updates occur simultaneously, capturing a snapshot of all the next states based on the current states before any are updated. This requires a careful handling of state transitions, ensuring no premature updates that could cascade incorrect changes across the board.

Given the constraints, there are a few straightforward methods to solve this:

  • Double-Buffering: Use two boards; one for the current state and another to calculate and store the next state. This ensures that changes do not affect the cell updates still to be processed.

  • In-place Update with Markers: Since only two states are possible as described by the rule, use a special marker to distinguish "will live" or "will die" without needing additional memory apart from the original board.

Example Walkthroughs:

Example 1:

  1. Board initially: [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
    • Regular scanning of each cell to apply the 4 rules.
    • After applying rules, the board transforms to: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:

  1. Initial board setup: [[1,1],[1,0]]
    • Apply the game rules cell by cell.
    • The board updates to: [[1,1],[1,1]]

In each case, understanding the neighborhood state is crucial. Efficient checking of cell boundaries and neighbor counts directly affects the performance and correctness of the simulation. This method is computationally manageable given the constraints (m, n <= 25), ensuring the processing of each cell and its neighbors remains efficient.

Solutions

  • Java
  • Python
java
class Solution {
    public void simulateGameOfLife(int[][] grid) {
        int[] delta = {0, 1, -1}; // different changes for neighbor indices

        int numRows = grid.length;
        int numCols = grid[0].length;

        // Clone the grid to original grid to keep the original state
        int[][] originalGrid = new int[numRows][numCols];

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                originalGrid[i][j] = grid[i][j];
            }
        }

        // Process each cell of the board
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {

                int aliveNeighbors = 0; // counter for alive neighboring cells

                for (int x = 0; x < 3; x++) {
                    for (int y = 0; y < 3; y++) {

                        if (!(delta[x] == 0 && delta[y] == 0)) {
                            int neighbour_x = (i + delta[x]);
                            int neighbour_y = (j + delta[y]);

                            if ((neighbour_x < numRows && neighbour_x >= 0) && (neighbour_y < numCols && neighbour_y >= 0) && (originalGrid[neighbour_x][neighbour_y] == 1)) {
                                aliveNeighbors += 1;
                            }
                        }
                    }
                }

                // Rules application
                if ((originalGrid[i][j] == 1) && (aliveNeighbors < 2 || aliveNeighbors > 3)) {
                    grid[i][j] = 0;
                }
                if (originalGrid[i][j] == 0 && aliveNeighbors == 3) {
                    grid[i][j] = 1;
                }
            }
        }
    }
}

This summary outlines the Java solution for simulating the "Game of Life", based on the Conway's game of life rules. This implementation processes a given grid of cells, which can either be alive (1) or dead (0), and updates the grid according to the game's rules through multiple generations.

  • The code first initializes a delta array which is used to locate the 8 possible neighbors of any cell (diagonally, vertically, and horizontally adjacent).
  • It creates a copy of the original grid - originalGrid. This duplication is crucial as it preserves the initial state of the grid while the new states are being calculated, preventing any updates during the iteration from affecting subsequent calculations in the current generation.
  • The code then iterates over each cell in the grid, counting live neighbors by using the delta array to check each of the eight surrounding positions. Exception handling ensures it doesn't check out-of-bound indices.
  • Based on the count of alive neighbors and the current state of the cell, the game's rules are applied:
    • A live cell with fewer than two or more than three live neighbors dies (represented by setting the cell's value to 0).
    • A dead cell with exactly three live neighbors becomes alive (setting the cell's value to 1).

The procedure directly modifies the original grid array, which represents the state of the game board post-simulation of the current generation step. This approach efficiently updates the game state in place, utilizing minimal additional memory for the clone of the original grid state only.

python
class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        # Array to reference 8 surrounding cells
        neighbor_directions = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        num_rows = len(board)
        num_cols = len(board[0])

        # Clone the board
        original_board = [[board[r][c] for c in range(num_cols)] for r in range(num_rows)]

        # Process each cell in the board
        for r in range(num_rows):
            for c in range(num_cols):

                # Count live neighboring cells
                live_neighbors = 0
                for direction in neighbor_directions:
                    row, col = r + direction[0], c + direction[1]

                    # Ensure the cell is within bounds and check if it's live
                    if (0 <= row < num_rows) and (0 <= col < num_cols) and (original_board[row][col] == 1):
                        live_neighbors += 1

                # Apply the rules of the Game of Life
                if original_board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[r][c] = 0
                elif original_board[r][c] == 0 and live_neighbors == 3:
                    board[r][c] = 1

This Python solution implements the Game of Life, a cellular automation devised by the mathematician John Horton Conway. The problem requires updating the board for the next generation based on the following rules:

  • Any live cell with fewer than two or more than three live neighbors dies, as if by underpopulation or overpopulation.
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Solution steps are as follows:

  1. Define neighbor_directions to reference all eight possible surrounding cells relative to any given cell.
  2. Determine the number of rows (num_rows) and columns (num_cols) of the board.
  3. Clone the original board into original_board to preserve the state of the board at the beginning of the operation, allowing independent evaluation of each cell.
  4. Iterate through each cell of the board using nested loops.
  5. Initialize live_neighbors to count the live cells surrounding the current cell.
  6. For each possible direction in neighbor_directions, calculate potential neighbor's row and column index.
  7. Validate that the computed indices are within board boundaries and the neighbor cell is alive. If conditions are met, increase live_neighbors count.
  8. Apply Game of Life rules:
    • If a live cell has <2 or >3 live neighbors, set it to dead (0).
    • If a dead cell has exactly 3 live neighbors, set it to live (1).

This implementation ensures that the board is evaluated consistently based on its state at the start of the function call, adhering to the rules of the Game of Life for simultaneous updates.

Comments

No comments yet.