What
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
It belongs to cellular automata model class.
The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 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.
The next state is created (at each tick) by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.
Implications
Game of life shows all four possible outcomes: equilibrium, cycle, complexity, randomness.
- Logic Right: We can see now with The Game of Life how simple things following simple rules can aggregate to form complex patterns, complex macro level phenomena.
- Self Organization: Patterns appear without a designer.
- Emergence. Functionalities apper (patterns can be interpreted as having functions): gliders, glider guns, counters, computers.
Application
Human brain has neurons that follow simple rules and can create novel patterns that produce things like memory, thought, cognition, personality, etc.
Problem
Given the current state of the m x n grid board, return the next state.
Examples
Example 1:
$$ grid = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} \Longrightarrow \begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} $$
Input: board = [ [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] ]
Example 2:
$$ grid = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \Longrightarrow \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $$
Input: board = [ [1,1],[1,0] ]
Output: [ [1,1],[1,1] ]
Solution
If we were to solve with extra space, this problem was easy, just iterate over the matrix and genrate a new one. But when we have to do in place, it becomes a bit tricky. For eg. if we change 1 state from 0 to 1, remaining neighbours still need to use old state 0 to calculate there current state. This is similar to Set Matrix Zeros Problem.
Method 1 - Modify Array with Higher Bits
Because we need to solve the problem in place, we can use the higher bit to record the next state. And at the end, shift right a bit to get the next state for each cell.
private static final int DIE = 2;
private static final int LIVE = 3;
private static final int[][] DIRS = {{-1, -1}, // north west
{-1, 0}, // north
{-1, 1}, // north east
{0, -1}, // west
{0, 1}, // east
{1, -1}, // south west
{1, 0}, // south
{1, 1}}; // south east
// just use two vars and we can get it done by flipping the value
public void gameOfLife(int[][] board) {
// we only flip the 1 to die and 0 to live
// so when we find a die around, it must be a previous 1 // then we can count the 1s without being affected int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int livesAround = countLives(i, j, board);
// if cell is dead
if (board[i][j] == 0 && livesAround == 3) {
board[i][j] = LIVE;
} else if (board[i][j] == 1) { // if cell is alive
if (livesAround == 2 || livesAround == 3) {
continue;
}
board[i][j] = DIE;
}
}
}
// fix the board again
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == DIE)
board[i][j] = 0;
if (board[i][j] == LIVE)
board[i][j] = 1;
}
}
}
private int countLives(int i, int j, int[][] board) {
int count = 0;
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && y >= 0 && x < board.length && y < board[0].length) {
if (board[x][y] == 1 || board[x][y] == DIE) {
count++;
}
}
}
return count;
}