Program for Conway’s Game Of Life | Set 1

Given a Binary Matrix mat[][] of order m*n. A cell with a value of zero is a Dead Cell, while a cell with a value of one is a Live Cell. The state of cells in a matrix mat[][] is known as Generation. The task is to find the next generation of cells based on the following rules:

• Any live cell with fewer than two live (< 2) neighbours dies as if caused by underpopulation.
• Any live cell with two or three live (= 2 or 3) neighbours lives on to the next generation.
• Any live cell with more than three live (> 3) neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live ( = 3) neighbours becomes a live cell, as if by reproduction.

Note: The neighbour cells that lie outside the matrix mat[][] are considered dead. Neighbours are the cells connected horizontally, vertically, or diagonally to a given cell. Or, the cells connected 8-directionally to a given cell are its neighbours.

Examples: 

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

Explanation: The cell at index {1, 1} with initial value 0 has exactly 3 live neighbors in index {1, 2}, {2, 1}, {2, 2}, thus it will be alive in next generation. Rest all three live cells have exactly 2 live neighboring cells each, thus they all will remain alive in next generation as well. All the remaining dead cells have less than 3 live cells thus they will remain dead.

Input: mat[][] = [[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
[0, 0, 1, 0, 0]]

Output: mat[][] = [[0, 0, 0, 0, 0],
[1, 1, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 1, 1, 0, 0]
[0, 0, 0, 0, 0]]

Explanation: The live cells at indices {1, 1}, {1, 2}, {2, 0}, {2, 1} have either 2 or 3 live neighbors, they will remain alive. The remaining live cells at indices {3, 3} and {4, 2} have only 1 live neighbor, thus they will become dead. The dead cells at indices {1, 0}, {3, 1} and {3, 2} have exactly three live neighbors, thus they will become alive. Dead cell at index {2, 2} has 4 live neighbors and all remaining dead cells have less than 2 live neighbors, thus they will remain dead.

[Naive Approach] Using an Additional Matrix – O(m*n) Time and O(m*n) Space

The idea is to create an auxiliary matrix nextGen[][] of order m*n to store the cells of next generation. After creating the matrix nextGen[][], traverse the matrix mat[][] and for each cell find the count of live neighbors (i.e. cells with value 1). If the cell at index {x, y} is dead (i.e. 0) and the count of live neighbors is three, set nextGen[x][y] = 1, which means that the cell will become alive in the next generation. Else if the cell is live (i.e. 1) and the count of live neighbors is not equal to two or three, set nextGen[x][y] = 0, which means that the cell will be dead in the next generation. After completing the traversal, return the matrix nextGen[][].

// C++ Program to find the next generation
// of a given matrix of cells
#include <bits/stdc++.h>
using namespace std;

// Function to find the next generation
void findNextGen(vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();

    // create matrix to store cells of next generation.
    vector<vector<int>> nextGen(m, vector<int>(n, 0));

    // Directions of eight possible neighbors
    vector<vector<int>> directions = 
    {{0, 1}, {1, 0}, {0, -1}, 
     {-1, 0}, {1, 1}, {-1, -1},
     {1, -1}, {-1, 1}};

    // Iterate over the matrix
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {

            // Count the number of live neighbors
            int live = 0;
            for (auto dir : directions) {
                int x = i + dir[0];
                int y = j + dir[1];

                // Check if the neighbor is live
                if (x >= 0 && x < m && y >= 0 && y < n && (mat[x][y] == 1)) {
                    live++;
                }
            }

            // If current cell is live and number of live neighbors
            // is less than 2 or greater than 3, then the cell will die
            if (mat[i][j] == 1 && (live < 2 || live > 3)) {
                nextGen[i][j] = 0;
            }

            // If current cell is dead and number of live neighbors
            // is equal to 3, then the cell will become live
            else if (mat[i][j] == 0 && live == 3) {
                nextGen[i][j] = 1;
            }

            // else the state of cells
            // will remain same.
            else {
                nextGen[i][j] = mat[i][j];
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << nextGen[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> mat = 
    {{0, 0, 0, 0}, {0, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
    findNextGen(mat);
    return 0;
}

// Java Program to find the next generation
// of a given matrix of cells
import java.util.*;

class GfG {

    // Function to find the next generation
    static void findNextGen(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        // create matrix to store cells of next generation.
        int[][] nextGen = new int[m][n];

        // Directions of eight possible neighbors
        int[][] directions = { { 0, 1 },  { 1, 0 },
                               { 0, -1 }, { -1, 0 },
                               { 1, 1 },  { -1, -1 },
                               { 1, -1 }, { -1, 1 } };

        // Iterate over the matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;

                // Count the number of live neighbors
                for (int[] dir : directions) {
                    int x = i + dir[0], y = j + dir[1];

                    if (x >= 0 && x < m && y >= 0 && y < n
                        && (mat[x][y] == 1)) {
                        live++;
                    }
                }

                // If current cell is live and number of
                // live neighbors is less than 2 or greater
                // than 3, then the cell will die
                if (mat[i][j] == 1
                    && (live < 2 || live > 3)) {
                    nextGen[i][j] = 0;
                }

                // If current cell is dead and number of
                // live neighbors is equal to 3, then the
                // cell will become live
                else if (mat[i][j] == 0 && live == 3) {
                    nextGen[i][j] = 1;
                }

                // else the state of cells
                // will remain same.
                else {
                    nextGen[i][j] = mat[i][j];
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(nextGen[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] mat = { { 0, 0, 0, 0 },
                        { 0, 0, 1, 0 },
                        { 0, 1, 1, 0 },
                        { 0, 0, 0, 0 } };
        findNextGen(mat);
    }
}

# Python Program to find the next generation
# of a given matrix of cells
def findNextGen(mat):
    m, n = len(mat), len(mat[0])
    
    # create matrix to store cells of next generation.
    nextGen = [[0 for _ in range(n)] for _ in range(m)]

    # Directions of eight possible neighbors
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0),
                  (1, 1), (-1, -1), (1, -1), (-1, 1)]

    # Iterate over the matrix
    for i in range(m):
        for j in range(n):
            live = 0

            # Count the number of live neighbors
            for dx, dy in directions:
                x, y = i + dx, j + dy
                
                # Check if the neighbor is live
                if 0 <= x < m and 0 <= y < n and (mat[x][y] == 1):
                    live += 1

            # If current cell is live and number of live neighbors
            # is less than 2 or greater than 3, then the cell will die
            if mat[i][j] == 1 and (live < 2 or live > 3):
                nextGen[i][j] = 0
                
            # If current cell is dead and number of live neighbors
            # is equal to 3, then the cell will become live
            elif mat[i][j] == 0 and live == 3:
                nextGen[i][j] = 1
            
            # else the state of cells
          	# will remain same.
            else :
                nextGen[i][j] = mat[i][j]

    for i in range(m):
        for j in range(n):
            print(nextGen[i][j], end=" ")
        print()

mat = [
    [0, 0, 0, 0],
    [0, 0, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
]
findNextGen(mat)

// C# Program to find the next generation
// of a given matrix of cells
using System;

class GfG {

    // Function to find the next generation
    static void FindNextGen(int[, ] mat) {
        int m = mat.GetLength(0), n = mat.GetLength(1);

        // create matrix to store cells of next generation.
        int[, ] nextGen = new int[m, n];

        // Directions of eight possible neighbors
        int[, ] directions = { { 0, 1 },  { 1, 0 },
                               { 0, -1 }, { -1, 0 },
                               { 1, 1 },  { -1, -1 },
                               { 1, -1 }, { -1, 1 } };

        // Iterate over the matrix
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;

                // Count the number of live neighbors
                for (int k = 0; k < 8; k++) {
                    int x = i + directions[k, 0];
                    int y = j + directions[k, 1];

                    if (x >= 0 && x < m && y >= 0 && y < n
                        && (mat[x, y] == 1)) {
                        live++;
                    }
                }

                // If current cell is live and number of
                // live neighbors is less than 2 or greater
                // than 3, then the cell will die
                if (mat[i, j] == 1
                    && (live < 2 || live > 3)) {
                    nextGen[i, j] = 0;
                }

                // If current cell is dead and number of
                // live neighbors is equal to 3, then the
                // cell will become live
                else if (mat[i, j] == 0 && live == 3) {
                    nextGen[i, j] = 1;
                }

                // else the state of cells
                // will remain same.
                else {
                    nextGen[i, j] = mat[i, j];
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Console.Write(nextGen[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static void Main(string[] args) {
        int[, ] mat = { { 0, 0, 0, 0 },
                        { 0, 0, 1, 0 },
                        { 0, 1, 1, 0 },
                        { 0, 0, 0, 0 } };

        FindNextGen(mat);
    }
}

// JavaScript Program to find the next generation
// of a given matrix of cells
function findNextGen(mat) {
    let m = mat.length, n = mat[0].length;

    // create matrix to store cells of next generation.
    let nextGen
        = Array.from({length : m}, () => Array(n).fill(0));
    // Directions of eight possible neighbors
    let directions = [
        [ 0, 1 ], [ 1, 0 ], [ 0, -1 ], [ -1, 0 ], [ 1, 1 ],
        [ -1, -1 ], [ 1, -1 ], [ -1, 1 ]
    ];

    // Iterate over the matrix
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let live = 0;

            // Count the number of live neighbors
            for (let [dx, dy] of directions) {
                let x = i + dx, y = j + dy;

                // check if the neighbor is live
                if (x >= 0 && x < m && y >= 0 && y < n
                    && (mat[x][y] === 1)) {
                    live++;
                }
            }

            // If current cell is live and number of live
            // neighbors is less than 2 or greater than 3,
            // then the cell will die
            if (mat[i][j] === 1 && (live < 2 || live > 3)) {
                nextGen[i][j] = 0;
            }

            // If current cell is dead and number of live
            // neighbors is equal to 3, then the cell will
            // become live
            else if (mat[i][j] === 0 && live === 3) {
                nextGen[i][j] = 1;
            }

            // else the state of cells
            // will remain same.
            else {
                nextGen[i][j] = mat[i][j];
            }
        }
    }

   for (let i = 0; i < m; i++) {
      let row = "";
      for (let j = 0; j < n; j++) {
          row += nextGen[i][j] + " ";
      }
      console.log(row.trim());
  }
}

//driver code
const mat = [
    [ 0, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 1, 1, 0 ],
    [ 0, 0, 0, 0 ]
];
findNextGen(mat);

0 0 0 0 
0 1 1 0 
0 1 1 0 
0 0 0 0 

Time Complexity : O(m*n), where m is the number of rows and n is the number of columns.
Auxiliary Space : O(m*n), because we are using an auxiliary matrix to store cells.

[Expected Approach] Without Using an Additional Matrix – O(m*n) Time and O(1) Space

The matrix mat[][] itself is used store the next generation of cells, minimizing the space required to create an additional matrix. Please refer to Program for Conway’s Game Of Life | Set 2