Conway's Game of Life | Algorithm Notes

Conway's Game of Life | Algorithm Notes

Any live cells with fewer than two neighbours dies in the next generation

Any live or empty cell with more or equal to two neighbours become live cell in the next generation.

Stage 1: small board - time and space cost O(N2)

    void nextGeneration(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] newboard = new int[m][n];
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int neighbours = countNeighbours(board, i, j);
                if (neighbours >= 2) newboard[i][j] = 1;
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = newboard[i][j];
    }

    int countNeighbours(int[][] board, int i, int j) {
        int count = 0;
        int m = board.length;
        int n = board[0].length;
        for (int x = -1; x <= 1; x++) {
            for (int y = -1; y <= 1; y++) {
                if (x == 0 && y == 0) continue;
                int px = i + x;
                int py = j + y;
                if (px >= 0 && px < m && py >= 0 && py < n) {
                    if (board[px][py] == 1) count++;
                }
            }
        }
        return count;
    }

Step 2: in place generation
We can come up an in place algorithm by modifying the cell by plus 2 to avoid the repeadly allocation. Thus we can distinguish the original positions of live cell and the positions should be live cell next generation

class GameOfLife {
    void nextGeneration(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int neighbours = countNeighbours(board, i, j);
                if (neighbours >= 2) board[i][j] += 2;
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] >= 2) board[i][j] = 1;
                else board[i][j] = 0;
    }

    int countNeighbours(int[][] board, int i, int j) {
        int count = 0;
        int m = board.length;
        int n = board[0].length;
        for (int x = -1; x <= 1; x++) {
            for (int y = -1; y <= 1; y++) {
                if (x == 0 && y == 0) continue;
                int px = i + x;
                int py = j + y;
                if (px >= 0 && px < m && py >= 0 && py < n) {
                    if (board[px][py] == 1 || board[px][py] == 3) count++;
                }
            }
        }
        return count;
    }

Note that we will count the neighbours when the value is 1 or 3, which means there is a life cell originally at that position. A position has value 2 means it originally empty but will has a live cell the next generation. At last, both 2 and 3 means that position will has a live cell, so at last we traverse around all positions and marks these positions as 1.

Step 3: large or infinite board -- time and space O(n) where N is the number of live cells on the board currently.
The program above is also not good enough if the live cells on the board is very sparse. A better way is to change the representation of board.
Data structures decide everything!

void nextGeneration(HashSet<Pair> liveCells) {
    HashMap<Pair, Integer> map = new HashMap<Pair, Integer>();
    for (Pair p : liveCells) {
        for (int i = -1; i <= 1; i++)
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                Pair newp = new Pair(p.left + i, p.right + j);
                if (map.containsKey(newp)) {
                    map.put(newp, map.get(newp) + 1);
                } else {
                    map.put(newp, 1);
                }
            }
    }
    liveCells.clear();
    for (Pair p : map.keySet()) {
        if (map.get(p) >= 2) liveCells.add(p);
    }
}

The last solution is usually the best one if you can use self-defined data structures. It is also good to mention the first two solutions as references.

Related: http://massivealgorithms.blogspot.com/2015/10/leetcodegame-of-life.html
Read full article from Conway's Game of Life | Algorithm Notes