Game of Life - C Solution

1. Introduction

This post delves into the fascinating "Game of Life", a cellular automaton devised by John Horton Conway. This zero-player game simulates a life-like system based on simple rules applied to a grid of cells. The challenge in programming the Game of Life lies in efficiently computing the next state of the grid based on the current state.

Problem

Given an m x n grid of cells, each cell is in one of two states: live (1) or dead (0). The next state of each cell is determined by its current state and the number of live neighbors based on four rules. The task is to update the grid to its next state by applying these rules simultaneously to every cell.

2. Solution Steps

1. Iterate through each cell in the grid.

2. For each cell, count the number of live neighbors.

3. Apply the Game of Life rules to determine the next state of each cell.

4. Update the cell states simultaneously after computing the next state for all cells.

5. Do this in place without using additional space for another grid.

3. Code Program

#include <stdio.h>

// Function to count live neighbors
int liveNeighbors(int** board, int boardSize, int* boardColSize, int row, int col) {
    int lives = 0;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            int r = row + i, c = col + j;
            if ((r >= 0 && r < boardSize) && (c >= 0 && c < boardColSize[0]) && (board[r][c] == 1)) {
                lives++;
            }
        }
    }
    return lives - board[row][col]; // Subtract the cell itself if it's live
}

// Function to update the board to its next state
void gameOfLife(int** board, int boardSize, int* boardColSize) {
    int neighbors;
    // First pass: update the board with an intermediate state
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            neighbors = liveNeighbors(board, boardSize, boardColSize, i, j);
            if (board[i][j] == 1 && (neighbors < 2 || neighbors > 3)) {
                board[i][j] = 3; // From live to dead
            }
            if (board[i][j] == 0 && neighbors == 3) {
                board[i][j] = 2; // From dead to live
            }
        }
    }

    // Second pass: finalize the state
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            board[i][j] %= 2;
        }
    }
}

// Main function to test the gameOfLife function
int main() {
    int board[4][3] = {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {0, 0, 0}};
    int boardColSize[] = {3, 3, 3, 3};
    gameOfLife((int**)board, 4, boardColSize);

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Output:

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

Explanation:

1. Implement a helper function liveNeighbors to count live neighbors for each cell.

2. In the first pass, mark cells with intermediate states (3 for live to dead, 2 for dead to live) based on the Game of Life rules.

3. In the second pass, finalize the states by converting 2 and 3 back to 1 and 0 respectively.

4. This approach updates the board in place without using extra space.

5. The main function tests the gameOfLife function with a sample board and prints the next state of the board.