289. Game of Life

  • 36.5%

https://leetcode.com/problems/game-of-life/#/description

According to the 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):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. 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.

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

https://discuss.leetcode.com/topic/26112/c-o-1-space-o-mn-time

C++ O(1) space, O(mn) time

Since the board has ints but only the 1-bit is used, I use the 2-bit to store the new state. At the end, replace the old state with the new state by shifting all values one bit to the right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
if ((count | board[i][j]) == 3)

test. Thanks to aileenbai for showing that one in the comments.


https://discuss.leetcode.com/topic/26176/c-ac-code-o-1-space-o-mn-time

C++ AC Code O(1) space, O(mn) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Game of Life
/*
状态: 前一位表示下一代的状态,后一位表示当前的状态
00: 死->死
10: 死->活
01: 活->死
11: 活->活
*/
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int d[][2] = {{1,-1},{1,0},{1,1},{0,-1},{0,1},{-1,-1},{-1,0},{-1,1}};
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
int live = 0;
for(int k = 0; k < 8; k++){
int x = d[k][0] + i;
int y = d[k][1] + j;
if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
continue;
}
if(board[x][y] & 1) {
live++;
}
}
// 死的
if(board[i][j] == 0) {
if(live == 3){
board[i][j] = 2; // 2 : (10)
}
}
// 活的
else {
if(live < 2 || live > 3){
board[i][j] = 1; // 1 : (01)
}else{
board[i][j] = 3; // 3 : (11)
}
}
}
}
for(int i = 0; i < board.size(); i++){
for(int j=0; j < board[0].size(); j++){
board[i][j] >>=1;
}
}
}
};enter code here

https://discuss.leetcode.com/topic/26236/infinite-board-solution

Infinite board solution

For the second follow-up question, here’s a solution for an infinite board. Instead of a two-dimensional array of ones and zeros, I represent the board as a set of live cell coordinates.

1
2
3
4
5
6
7
8
9
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}

And here’s a wrapper that uses the above infinite board solution to solve the problem we have here at the OJ (submitted together, this gets accepted):

1
2
3
4
5
6
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)

https://discuss.leetcode.com/topic/27167/c-o-mn-time-o-1-space-sol

C++ O(mn)-time, O(1)-space sol

First this solution does not involve bit-manipulation and only involves addition of integers.

The idea is to go through the matrix from top-left corner to the bottom-right corner, and check only 4 cells (“accumulate” scores “for both cells” if the other cell is originally a 1). Graphically speaking, it is like this:

1
2
3
O O O 
O @ X
X X X

where the @ cell is the one that you are working on, 0 cells are those you have gone through (don’t work on them again!), and the X cells are those you have not gone through and should work on. For example, if one X cell is originally a 1, you should add C (a constant) to @ cell, and simultaneously if @ cell is originally a 1, you add C to that X cell.

The constant C can be 2. If it is 2 then when you will find that after done working on the current cell if it’s value is 5 or 7 (cell @ is originally a 1 and have 2 or 3 neighbours) or 6 (cell @ is originally a 0 and have 3 neighbours), then you should reset it to be 1 (live), otherwise reset it to be zero (dead). And when accumulating scores, you know a cell is originally a 1 if it has odd-numbered score, and it is originally a 0 if it has even-numbered score. The code is

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
if(board.empty()) return;
const int m = board.size();
const int n = board[0].size();
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
check(board,i,j,i+1,j-1);
check(board,i,j,i+1,j);
check(board,i,j,i+1,j+1);
check(board,i,j,i,j+1);
if(board[i][j]>=5 && board[i][j]<=7) board[i][j]=1;
else board[i][j]=0;
}
}
}
private:
void check(vector<vector<int>>& board, int i, int j, int a, int b) {
const int m = board.size();
const int n = board[0].size();
if(a>=m || b<0 || b>=n) return;
if(board[i][j]%2!=0) board[a][b]+=2;
if(board[a][b]%2!=0) board[i][j]+=2;
}
};

https://discuss.leetcode.com/topic/27098/python-solution-easy-to-understand

Python solution, easy to understand..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0,2 are "dead", and "dead->live"
1,3 are "live", and "live->dead"

def gameOfLife(self, board):
m,n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == 0 or board[i][j] == 2:
if self.nnb(board,i,j) == 3:
board[i][j] = 2
else:
if self.nnb(board,i,j) < 2 or self.nnb(board,i,j) >3:
board[i][j] = 3
for i in range(m):
for j in range(n):
if board[i][j] == 2: board[i][j] = 1
if board[i][j] == 3: board[i][j] = 0

def nnb(self, board, i, j):
m,n = len(board), len(board[0])
count = 0
if i-1 >= 0 and j-1 >= 0: count += board[i-1][j-1]%2
if i-1 >= 0: count += board[i-1][j]%2
if i-1 >= 0 and j+1 < n: count += board[i-1][j+1]%2
if j-1 >= 0: count += board[i][j-1]%2
if j+1 < n: count += board[i][j+1]%2
if i+1 < m and j-1 >= 0: count += board[i+1][j-1]%2
if i+1 < m: count += board[i+1][j]%2
if i+1 < m and j+1 < n: count += board[i+1][j+1]%2
return count

https://discuss.leetcode.com/topic/26117/ac-python-40-ms-solution-o-mn-time-o-1-extra-space

AC Python 40 ms solution O(mn) time O(1) extra space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def update(self, board, m, n, i, j):
live = 0
for p in xrange(max(i - 1, 0), min(i + 2, m)):
for q in xrange(max(j - 1, 0), min(j + 2, n)):
live += board[p][q] & 1
if live == 3 or live == board[i][j] + 3:
board[i][j] += 2

def gameOfLife(self, board):
if not board or not board[0]:
return
m = len(board)
n = len(board[0])
for i in xrange(m):
for j in xrange(n):
self.update(board, m, n, i, j)
for i in xrange(m):
for j in xrange(n):
board[i][j] >>= 1


# 22 / 22 test cases passed.
# Status: Accepted
# Runtime: 40 ms

Everyone knows how to update this board if another m * n array is allowed. The O(1) space solution is just using the wasted bits in the original array. Instead of only 0 and 1 we now need the second bit for the updated value. The living condition is just by definition.

Of course, writing everything together will save several lines of code. However, implement things like this, readability and expandability counts.

As of the follow up question.
For example your 3 * 3 initial board is the following:

1
2
3
1 1 1
1 0 1
1 1 1

In the case of only 3 * 3 the next generation is:

1
2
3
1 0 1
0 0 0
1 0 1

However in the case of a infinite board the next generation is:

1
2
3
4
5
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0

Question is how to you implement this expandable board. One solution of the infinity situation is using a upper level grid, a grid of grids, instead of only one grid of cells. Note that we can be lazy. We only initialize (allocate the memory for real) a certain grid if any cell in it is activated. The rest of the unused grid can be pointer only.


1ms, 11.45%, October 18, 2016

https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
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);
if(board[i][j] == 1 && lives>=2 && lives <= 3)
board[i][j] = 3;
if(board[i][j] == 0 && lives == 3)
board[i][j] = 2;
}

for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
board[i][j] >>= 1;
}

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;
}
}
谢谢你,可爱的朋友。