Game of Life

Leave a comment

December 17, 2016 by oneOokay

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.


Easy个毛线=。= in-place的没想出来。

所以既然要in-place的话,那么一定需要一个新的rule apply在原来的板子上(也就是原来的板子上的值不可能只有0,1了),使得[i][j]这个值既可以表示现在的值也可以表示变换之前的值。最后一步根据这个新的rule复原回原来的板子。重点是想出来这个新的rule,然后就简单了。

目前的变换有

1->1:这个可以保持为1

0->0 : 这个可以保持为0.

1->0:这个要找出一个新的值来表示a.之前是1;b.现在是0;c.最终要能够变回0:所以选择2为新的值,最终结果用%2可以变回0. (1和0 %2 本身不变,所以1->1用1 和0->0用0符合要求)

0->1:这个要找出一个新的值来表示a.之前是0;b.现在是1;c.最终要能够变回1:所以选择3为新的值,最终结果用%2可以变回1。

技巧方面有一个厉害的来找周围的8个点:用8个“向量”来“走”到周围的八个点。

第一个为i对应的row,第二个为j对应的col
int[][] dir ={{1,-1}左下,{1,0}下,{1,1}右下,
{0,-1}左,{0,1右},
{-1,-1}左上,{-1,0}上,{-1,1}右上};

if(d[0]+i<0 (向上走出界)|| d[0]+i>=board.length(向下走出界)
|| d[1]+j<0 (向左走出界)|| d[1]+j>=board[0].length(向右走出界))
 continue;
if(board[d[0]+i][d[1]+j]==1 || board[d[0]+i][d[1]+j]==2) live++;

贴两个解法,不同之处在于如何找到当前cell的周围的8个cell:

  • 解法一是通过找到valid的上下左右,然后两个for-lopp
  • 解法二是通过向量
解法一:
public void gameOfLife(int[][] board) {
if (board == null){
return;
}

for (int i = 0; i < board.length; i ++){
for (int j = 0; j < board[0].length; j ++){
int sum = getLiveCells(board, i, j);
if (board[i][j] == 0 && sum == 3){//之前是死的,现在可以变成活的了,=3
board[i][j] = 3;
}else if (board[i][j] == 1 && (sum < 2 || sum > 3)){
//之前是活的,现在依旧保持活的,=2
board[i][j] = 2;
}else {//其他所有情况,值不变。
board[i][j] = board[i][j];
}}}
//恢复板子
for (int i = 0; i < board.length; i ++){
for (int j = 0; j < board[0].length; j ++){
board[i][j] %= 2;
}}}

private int getLiveCells(int[][] board, int row, int col){
int up = Math.max(row - 1, 0);
int down = Math.min(row + 1, board.length - 1);
int left = Math.max(col - 1, 0);
int right = Math.min(col + 1, board[0].length - 1);
int sum = 0;
for (int x = up; x <= down; x ++){
for (int y = left; y <= right; y ++){
if (x == row && y == col) //遇到自己跳过
continue;
if (board[x][y] == 1 || board[x][y] == 2){
//==1:之前活着现在也活着;==2:之前活着现在死了;总之都是之前或者的cell
sum ++;
}}}
return sum;
}
解法二:用向量来找到周围的8个cell:
public void gameOfLife(int[][] board) {
 if(board == null) return;
 
 int[][] dir = new int[][]{
{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1,1}};
 
 for( int i= 0; i < board.length; i ++){
 for (int j = 0; j < board[0].length; j ++){
 int live = 0;
 for (int[] d : dir){
 if (d[0] + i >= board.length || d[0] + i < 0 || 
d[1] + j >= board[0].length || d[1] + j < 0)
 continue;
 
 if (board[d[0] + i][d[1] + j] == 1 || board[d[0] + i][d[1] + j] == 2)
 live ++;
 }
 
 if (board[i][j] == 0 && live == 3)
 board[i][j] = 3;
 if (board[i][j] == 1 && (live < 2 || live > 3))
 board[i][j] = 2;
 }
 }
 
 for(int i = 0; i < board.length; i ++){
 for (int j = 0; j < board[0].length; j ++){
 board[i][j] %= 2;
 }
 }
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: