Solution For Game Of Life

Game of Life is a popular problem on LeetCode, it’s a simulation problem where we need to simulate the evolving state of cells in a grid following certain rules.

Problem Statement:

You are given a 2D board representing the life of a cell. Each cell has a value of either 0 or 1. The 0 represents the dead cell and 1 represents the live cell. The game of life is a cellular automaton where each cell follows the below rules:
– If a live cell has fewer than two live neighbors, it dies.
– If a live cell has more than three live neighbors, it dies.
– If a dead cell has exactly three live neighbors, it comes back to life.
– If a live cell has exactly two or three live neighbors, it continues to live.

Now, we have to implement a function that takes the board as input and returns an updated board.

Solution:

The problem statement mentions that we have to simulate the changes of evolving cells in the given board. To implement the simulation logic, we can follow these steps:

Step 1: Iterate over each cell in the board.
Step 2: For each cell, calculate the number of live neighbors.
Step 3: Apply the rules of the game of life to that cell.
Step 4: Store the updated state of each cell in a separate board.
Step 5: After all cells have been updated, copy the updated board to the original board.

Let’s implement this solution in Python:

def gameOfLife(board: List[List[int]]) -> None:
row, col = len(board), len(board[0])
updated_board = [[0] * col for _ in range(row)]

def count_live_neighbors(i, j):
    count = 0
    for x in range(max(0, i - 1), min(i + 2, row)):
        for y in range(max(0, j - 1), min(j + 2, col)):
            count += board[x][y]
    count -= board[i][j]
    return count

for i in range(row):
    for j in range(col):
        live_neighbors = count_live_neighbors(i, j)
        cell_state = board[i][j]
        if cell_state == 1 and (live_neighbors == 2 or live_neighbors == 3):
            updated_board[i][j] = 1
        elif cell_state == 0 and live_neighbors == 3:
            updated_board[i][j] = 1

for i in range(row):
    for j in range(col):
        board[i][j] = updated_board[i][j]

Let’s understand the code step by step:

• In the function signature, we have taken the input board as a List of Lists and the return type as None.
• We have initialized the row and col variable to the dimensions of the input board and created an updated_board with the same size.
• We have defined a nested function called count_live_neighbors which takes the current cell’s indices as arguments and returns the count of live neighbors.
• In the main loop, we have iterated over each cell in the board and calculated the number of live neighbors using the count_live_neighbors function.
• We have applied the rules of the game of life to update the current cell, and stored the updated state in the updated_board.
• Finally, we have copied the updated_board to the original board.

Complexity Analysis:

• Time Complexity: O(row * col) because we are iterating over each cell in the board once.
• Space Complexity: O(row * col) because we are creating an updated copy of the board in memory.

Conclusion:

In this blog post, we discussed the Game of Life problem on LeetCode and implemented its solution in Python. We followed a step-by-step approach to simulate the evolution of cells in the input board and update their state using the game of life rules. This problem teaches us the importance of breaking down a complex problem into smaller sub-problems and solving them step by step.

Step by Step Implementation For Game Of Life

class Solution {
    // in-place solution
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int lives = liveNeighbors(board, m, n, i, j);
                
                // In the beginning, every 2nd bit is 0;
                // So we only need to care about when the 2nd bit will become 1.
                if (board[i][j] == 1 && lives >= 2 && lives <= 3) {  
                    board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
                }
                if (board[i][j] == 0 && lives == 3) {
                    board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) 
                board[i][j] >>= 1;  // Get the 2nd state.
        }
    }
    
    public int liveNeighbors(int[][] board, int m, int n, int i, int j) {
        int lives = 0;
        for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) {
            for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) {
                lives += board[x][y] & 1;
            }
        }
        lives -= board[i][j] & 1;
        return lives;
    }
}

def gameOfLife(board):
    """
    Do not return anything, modify board in-place instead.
    """
    # Neighbors array to find 8 neighboring cells for a given cell
    neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

    rows = len(board)
    cols = len(board[0])

    # Create a copy of the board list to perform game of life operations on
    copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]

    # Loop through board cells
    for row in range(rows):
        for col in range(cols):

            # For each cell count the number of live neighbors
            live_neighbors = 0
            for neighbor in neighbors:
                r = row + neighbor[0]
                c = col + neighbor[1]

                # Check that the cell is within the bounds of the board
                if (r >= 0 and r < rows) and (c >= 0 and c < cols):
                    if copy_board[r][c] == 1:
                        live_neighbors += 1

            # Apply the rules of the game of life
            if copy_board[row][col] == 1:
                if live_neighbors < 2 or live_neighbors > 3:
                    board[row][col] = 0
            else:
                if live_neighbors == 3:
                    board[row][col] = 1

// game-of-life problem

// given a 2D array representing a game of life board,

// determine the next state of the board

// (i.e. which cells will be alive or dead)

// according to the rules of the game

//

// rules:

// 1. any live cell with fewer than two live neighbors dies

// 2. any live cell with two or three live neighbors lives

// 3. any live cell with more than three live neighbors dies

// 4. any dead cell with exactly three live neighbors becomes a live cell

//

// input: 2D array

// output: 2D array (next state of the board)

//

// example:

// 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]

// ]

//

// hint: use a 2nd 2D array to keep track of the next state of the board

// as you iterate through each cell

function gameOfLife(board) {

// create a 2nd 2D array to store the next state of the board

let nextState = [];

// iterate through each cell in the board

for (let i = 0; i < board.length; i++) {

for (let j = 0; j < board[i].length; j++) {

// count the number of live neighbors for each cell

let liveNeighbors = countLiveNeighbors(board, i, j);

// apply the rules of the game to determine if the cell

// will be alive or dead in the next state

if (board[i][j] === 1) {

// rule 1: any live cell with fewer than two live neighbors dies

if (liveNeighbors < 2) {

nextState[i][j] = 0;

}

// rule 2: any live cell with two or three live neighbors lives

else if (liveNeighbors === 2 || liveNeighbors === 3) {

nextState[i][j] = 1;

}

// rule 3: any live cell with more than three live neighbors dies

else if (liveNeighbors > 3) {

nextState[i][j] = 0;

}

} else {

// rule 4: any dead cell with exactly three live neighbors becomes a live cell

if (liveNeighbors === 3) {

nextState[i][j] = 1;

}

}

}

}

// return the next state of the board

return nextState;

}

// helper function to count the number of live neighbors for a given cell

function countLiveNeighbors(board, i, j) {

let liveNeighbors = 0;

// iterate through the 8 neighbors of the given cell

for (let x = -1; x <= 1; x++) {

for (let y = -1; y <= 1; y++) {

// make sure we're not counting the given cell itself

if (x === 0 && y === 0) {

continue;

}

// if the indices are valid and the cell is alive, increment the count

if (i + x >= 0 && i + x < board.length &&

j + y >= 0 && j + y < board[i].length &&

board[i + x][j + y] === 1) {

liveNeighbors++;

}

}

}

return liveNeighbors;

}

class Solution {
public:
    void gameOfLife(vector>& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        for (int i=0; i>= 1;
    }
};

using System; 

public class Solution {
    public void GameOfLife(int[][] board) {
        if (board == null || board.Length == 0) return;
        int m = board.Length, n = board[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int lives = LiveNeighbors(board, m, n, i, j);
                
                // In the beginning, every 2nd bit is 0;
                // So we only need to care about when the 2nd bit will become 1.
                if (board[i][j] == 1 && lives >= 2 && lives <= 3) {  
                    board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
                }
                if (board[i][j] == 0 && lives == 3) {
                    board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;  // Get the 2nd state.
            }
        }
    }
    
    public int LiveNeighbors(int[][] board, int m, int n, int i, int j) {
        int lives = 0;
        for (int x = Math.Max(i - 1, 0); x <= Math.Min(i + 1, m - 1); x++) {
            for (int y = Math.Max(j - 1, 0); y <= Math.Min(j + 1, n - 1); y++) {
                lives += board[x][y] & 1;
            }
        }
        lives -= board[i][j] & 1;
        return lives;
    }
}