leetCode Question: Game of Life

Game of Life

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):

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.

Follow up:
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.
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?

Analysis:

At the first glance, the solution is pretty straightforward without considering the "in-place" requirement. For each element in the array, we could compute the accumulated sum of its 8 neightbours. Check out the rules required in the question, set the corresponding value in a new array. Done.

Now let's handle the "in-place". Firstly, let's take a look at the rules and all possible values for each element:

  • If cell $x_t$ in time $t$ is alive ($x_t = 1$):
    • If sum of neighbour $s{x_t}$ = 2 or 3, then $x{t+1} = 1$
    • If $s{x_t} = 0, 1, 4, 5,6, 7, 8$, then $x{t+1} = 0$
  • If cell $x_t = 0$,
    • If $s{x_t} = 3$, then $x{t+1} = 1$
    • otherwise, $x_{t+1} = 0$

Now considering the case that, everytime after we compute one cell $xt$, and then write the value $x{t+1}$ back to the position, we lost the value in time $t$ so that it's impossible to compute the next cell in the same state.

Here note that the matrix doesn't have to be binary (0 or 1 only). What if we write the sum $s_t$ back to the position instead of the value of next state? Therefore, to obtain the next state, we just need to reset the values according to the rules. It looks like a good idea, however, how can we keep the original state of each cell at the same time is still a problem. So we have to figure out a way to "compute" the $x_t$ from $s_t$.

Note that, when cell is dead, there is only one case it will be alive in the next state. In other words, when $xt = 0$, unless $s_t = 3$, we could set the write 0 back to the array, since $x_t = x{t+1} = 0$. For the special case, we could simply write a negative value to distinguish the alive cells. To compute the current sum, we no longer have only binary values in the array, but also integers. But it is still easy to tell whether it was a 1 or 0, before we set the sum to it, by comparing the value with 0. Finally we want:

  • No matter the value in current cell indicates the state (alive or dead), or sum of its neighbour, it must be alive if it's greater than zero, and dead less than or equal to zero.

So when the cell is alive, the state value is 1. The sum value are positive integers except one special case 0. The good thing is the rule in the probelm treat sum 0 and 1 the same when state value is 1. So we could just set 0 to 1 since it will not effect the next state, while keep our criteria well.

Now with the criteria (comparison with 0) and two special cases (x=0, s=3, and x=1, s=0 ), we could compute and set the cells one by one in place, finally just reset the value according to the rules will result in the next state.

Code (C++):

class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int r = board.size();
if (r==0){return;}
int c = board[0].size();
for (int i=0;i<r;++i){
for (int j=0; j<c;++j){
int tmp = 0;
if (i-1 >=0 && j-1>=0){ tmp += (board[i-1][j-1] >0);}
if (i-1 >=0){ tmp += (board[i-1][j] >0);}
if (i-1 >=0 && j+1<c){ tmp += (board[i-1][j+1] >0);}
if (j+1<c){ tmp += (board[i][j+1] >0);}
if (i+1 <r && j+1<c){ tmp += (board[i+1][j+1] >0);}
if (i+1 <r ){ tmp += (board[i+1][j] >0);}
if (i+1 <r && j-1>=0){ tmp += (board[i+1][j-1] >0);}
if ( j-1>=0 ) { tmp += (board[i][j-1] >0);}
//cout << "tmp[" << i << "][" << j << "]=" << tmp << endl;
if (board[i][j]==0){
if (tmp == 3){
board[i][j] = -3;
}
}else{
if (tmp == 0){
board[i][j] = 1;
}else{
board[i][j] = tmp;
}
}
}
}
// for (int i=0;i<r;++i){
// for (int j=0; j<c;++j){
// cout << board[i][j] << ", ";
// }
// cout << endl;
// }
for (int i=0;i<r;++i){
for (int j=0; j<c;++j){
if (board[i][j] == -3){
board[i][j] = 1;
}else if (board[i][j] == 2 || board[i][j] == 3){
board[i][j] = 1;
}else{
board[i][j] = 0;
}
}
}
}
};

Code (Python):

class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
r = len(board)
if r == 0:
return
c = len(board[0])
for i in range(r):
for j in range(c):
tmp = 0
if i-1 >= 0 and j-1 >= 0:
tmp += (board[i-1][j-1] > 0)
if i-1 >=0:
tmp += (board[i-1][j] > 0)
if i-1 >=0 and j+1 < c:
tmp += (board[i-1][j+1] > 0)
if j+1 < c:
tmp += (board[i][j+1] > 0)
if i+1 < r and j+1 < c:
tmp += (board[i+1][j+1] > 0)
if j-1 >= 0 :
tmp += (board[i][j-1] > 0)
if i+1 < r :
tmp += (board[i+1][j] > 0)
if i+1 < r and j-1 >= 0 :
tmp += (board[i+1][j-1] > 0)
#print "tmp[", i, "][", j, "]=", tmp
if board[i][j] == 0:
if tmp == 3:
board[i][j] = -3
else:
if tmp == 0:
board[i][j] = 1
else:
board[i][j] = tmp
for i in range(r):
for j in range(c):
if board[i][j] == -3:
board[i][j] = 1
elif board[i][j] == 2 or board[i][j] == 3:
board[i][j] = 1
else:
board[i][j] = 0
Labels:

1 comment:

Subscribe to: Post Comments (Atom)