Game of Life
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."
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.
Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int tmp=0,n=board.size(),m=board[0].size();
for(int i=0;i<board.size();++i)
{
for(int j=0;j<board[0].size();++j)
{
tmp=0;
if(i>0&&(board[i-1][j]==1||board[i-1][j]==2))++tmp;
if(i+1<n&&(board[i+1][j]==1||board[i+1][j]==2))++tmp;
if(j>0&&(board[i][j-1]==1||board[i][j-1]==2))++tmp;
if(j+1<m&&(board[i][j+1]==1||board[i][j+1]==2))++tmp;
if(i>0&&j>0&&(board[i-1][j-1]==1||board[i-1][j-1]==2))++tmp;
if(i>0&&j+1<m&&(board[i-1][j+1]==1||board[i-1][j+1]==2))++tmp;
if(i+1<n&&j+1<m&&(board[i+1][j+1]==1||board[i+1][j+1]==2))++tmp;
if(i+1<n&&j>0&&(board[i+1][j-1]==1||board[i+1][j-1]==2))++tmp;
if(board[i][j]==1)
{
if(tmp<2||tmp>3)
board[i][j]=2;
}else{
if(tmp==3)
board[i][j]=3;
}
}
}
for(int i=0;i<board.size();++i)
{
for(int j=0;j<board[i].size();++j)
{
if(board[i][j]==2)
board[i][j]=0;
else if(board[i][j]==3)
board[i][j]=1;
}
}
}
};
----------------------------------------------------------------------------------------------------------------
To solve it in place, we use 2 bits to store 2 states:
[2nd bit, 1st bit] = [next state, current state]
- 00 dead (next) <- dead (current)
- 01 dead (next) <- live (current)
- 10 live (next) <- dead (current)
- 11 live (next) <- live (current)
In the beginning, every cell is either 00 or 01.Notice that 1st state is independent of 2nd state.Imagine all cells are instantly changing from the 1st to the 2nd state, at the same time.
Let's count # of neighbors from 1st state and set 2nd state bit. Since every 2nd state is by default dead, no need to consider transition 01 -> 00.
In the end, delete every cell's 1st state by doing >> 1.
For each cell's 1st bit, check the 8 pixels around
itself, and set the cell's 2nd bit.
Transition 01 -> 11: when board == 1 and lives >= 2
&& lives <= 3.
Transition 00 -> 10: when board == 0 and lives == 3.
To get the current state, simply do
board[i][j] & 1
To get the next state, simply do
board[i][j] >> 1
Hope this helps!
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;
}
-----------------------------------------------------------------------------------------------------------------
Since the board has ints but only the 1-bit is used, I use the 2-bit to store the new state. In the end, replace the old state with the new state by shifting all values one bit to the right.
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = m ? board[0].size() : 0;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
int count = 0;
for (int I=max(i-1, 0); I<min(i+2, m); ++I)
for (int J=max(j-1, 0); J<min(j+2, n); ++J)
count += board[I][J] & 1;
if (count == 3 || count - board[i][j] == 3)
board[i][j] |= 2;
}
}
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
board[i][j] >>= 1;
}
Note that the above count counts the live ones among a cell's neighbors and the cell itself. Starting with int count = -board[i][j] counts only the live
neighbors and allows the neat
if ((count | board[i][j]) == 3)
------------------------------------------------------------------------------------------------------------------
# Create a copy of the original board
copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]
# Iterate through board cell by cell.
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 the validity of the neighboring cell and if it was originally a live cell.
# The evaluation is done against the copy, since that is never updated.
if (r < rows and r >= 0) and (c < cols and c >= 0) and (copy_board[r][c] == 1):
live_neighbors += 1
# Rule 1 or Rule 3
if copy_board[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
board[row][col] = 0
# Rule 4
if copy_board[row][col] == 0 and live_neighbors == 3:
board[row][col] = 1
def gameOfLifeInfinite(self, live):
ctr = collections.Counter((I, J)
for i, j in live
for I in range(i-1, i+2)
for J in range(j-1, j+2)
if I != i or J != j)
return {ij
for ij in ctr
if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}
------------------------------------------------------------------------------------------------------------------------
def gameOfLife(self, board):
live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
live = self.gameOfLifeInfinite(live)
for i, row in enumerate(board):
for j in range(len(row)):
row[j] = int((i, j) in live)
