Solve the Game of Life problem in C++

John Horton Conway devised the Game of Life, a cellular automation with an m x n board. It doesn't function as a traditional board game, but rather as a mathematical model that simulates the behavior of a collection of cells on a grid. It serves as the basis of a popular interview question that we may face in the future.

Rules

This game's grid comprises a two-dimensional array of alive or dead cells. These cells interact with their neighbors (eight cells). This interaction is based on a set of rules that will decide the resultant state of the cell.

The rules are as follows:

Alive: Any live cell with two or three live neighbors remains alive. Moreover, any dead cell with exactly three live neighbors becomes alive.
Dead: Live cells with less than two live neighbors and more than three live neighbors die.

These rules are continuously applied to the entire board. This process is iterated for each subsequent generation, wherein the newly generated cells become the current generation.

In this Answer, we'll learn how to return the next state of the board, given any initial state.

Implementation

#include <iostream>
#include <vector>
using namespace std;
void print(const vector<vector<int>>& board) {
    for (size_t i = 0; i < board.size(); ++i) {
        const vector<int>& row = board[i];
        for (size_t j = 0; j < row.size(); ++j) {
            int cell = row[j];
            cout << cell << " ";
        }
        cout << endl;
    }
    cout << endl;
}
int countLiveNeighbors(int i, int j, const vector<vector<int>>& board) {
    int count = 0;
    vector<pair<int, int>> neighbors = {
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1}
    };
    int m = board.size();
    int n = board[0].size();
    
    for (size_t k = 0; k < neighbors.size(); ++k) {
        int x = i + neighbors[k].first;
        int y = j + neighbors[k].second;
        if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == -1)) {
            count++;
        }
    }
    
    return count;
}
void gameOfLife(vector<vector<int>>& board) {
    if (board.empty()) return;
    int m = board.size();
    int n = board[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int liveNeighbors = countLiveNeighbors(i, j, board);
            // Rule 1 and Rule 3
            if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                board[i][j] = -1;
            }
            // Rule 4
            if (board[i][j] == 0 && liveNeighbors == 3) {
                board[i][j] = 2;
            }
        }
    }
    // Convert values back to 0 and 1
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 2) {
                board[i][j] = 1;
            }
            else if (board[i][j] == -1) {
                board[i][j] = 0;
            }
        }
    }
}
int main() {
    vector<vector<int>> board = {
        {1, 1, 0},
        {1, 0, 1},
        {1, 0, 1},
        {0, 0, 1}
    };
    cout << "Initial Board" << endl;
    print(board);
    gameOfLife(board);
    cout << "New Board" << endl;
    print(board);
    return 0;
}

The explanation of the code is as follows:

Lines 6–16: We define the print function that prints the board. It takes a 2D vector board as a parameter and prints each cell by looping over the board.
Lines 18–34: The countLiveNeighbors function counts the number of live neighbors for each cell. It loops for each cell's neighbors, incrementing the count if a neighbor is alive. For this, we define a vector of pair neighbors, which represents the relative coordinates of neighboring cells. Each pair in the vector represents the offset in row and column values from the current cell.
Lines 39–71: The gameOfLife function implements the rules of the Game of Life. It takes a 2D vector board as input and calculates its output.
- Line 40: We check if the board is empty. If it is, return from the function.
- Lines 49–52: This section checks whether the cell will die in the next state. We implement both rules that lead to a cell's death and use the value -1 to represent a newly dead cell.
- Lines 54–56: This section checks whether the cell will be alive in the next state. We loop over the board with nested loops to visit each cell and use the count of live neighbors to determine its value. We use the value of 2 to represent a new live cell. This is to stop the new cell from interfering with the count of live cells in the next iteration.
- Lines 61–70: A loop that converts the values (-1 and 2) to 0 and 1, respectively.
Lines 73–90: Here, we have our int main that we use to call the gameofLife function we defined. We use a sample initial state represented in the 2D vector board.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources