Java: How to implement Conway's Game of Life?

Question

I'm studying the Conway's Game of Life to implement it on my own, and came across the following implementation with the rules:

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

• Any live cell with fewer than two live neighbors dies, as if caused by under-population.
• Any live cell with two or three live neighbors lives on to the next generation.
• Any live cell with more than three live neighbors dies, as if by over-population..
• Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

And implementation (https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation):

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 will the 2nd bit 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;
}

And driver:

public static void main(String args[]) {
    GameOfLife gl = new GameOfLife();

    int[][] board = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0}
            };

    gl.gameOfLife(board);
}

And my question is, what do the x and y in liveNeighbors() represent? Do not understand why the need for Math.min() and Math.max(). And also, does lives represent the amount of initialized lives on the board?

Answer 1

The given code is using the min and max functions to limit the search to valid entries in the array. If this is not done, the code will return an ArrayOutOfBoundsException when trying to use -1, m, or n as array indexes. (The loop doesn't "know" that given a square at the right edge of the map, it shouldn't search for living neighbors further to the right; these functions encode that fact.) x and y are simply the loop control variables which are used to iterate over valid squares surrounding the target square.

As for the lives variable, that's the placeholder to keep count of how many live neighbors have been found by the loops below. You might have guessed this by the fact that it's the return value of the liveNeighbors function.

Let's do an example. We'll call liveNeighbors(board,9,9,0,2), where board is the board given in the driver. Your board has dimensions 9x9, so those are the m and n we pass, and for our example we're investigating the square at 0,2, which is the first entry in the third row (which has a 1 to its right). Great, let's begin.

i=0, so x = Math.max(i - 1, 0) = Math.max(-1, 0) = 0 (this shows the reason for the max function: if we just said int x=i-1, we would end up with x = -1 which is out of the bounds of the array. Next we evaluate x <= Math.min(i + 1, m - 1) = Math.min(1, 8) = 1. If we were investigating a cell in the final column, this condition would have enforced the right edge of the array.

I'll leave the similar logic involving y and j to you.

The loop simplifies to:

for (int x = 0; x <= 1; x++) {
    for (int y = 1; y <= 3; y++) {
        lives += board[x][y] & 1;
    }
}

The inner loop will run six times, with the following (x,y) pairs: (0,1),(0,2),(0,3),(1,1),(1,2),(1,3). Convince yourself that these are the neighbors of the square we're investigating, as well as the square itself.

Five of these six squares will return 0, with the one at (1,2) returning 1, so at the end of this loop, lives will equal 1. The final thing to do is lives -= board[i][j] & 1;, which reduces lives by 1 if the square we're investigating has a 1 in it. In our case it doesn't (board[i][j] = 0) so we subtract 0, leaving us with 1, which we return. liveNeighbors(board,9,9,0,2) = 1

I may have gotten x and y backwards once or twice, but hopefully that's enough so you can understand what's going on.