未分類

Game of Life

Array, Go, LeetCode

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

  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?
提示 解題應用
Array Array/Slice

Default:

1
2
3
func gameOfLife(board [][]int) {
}

解答思路:

首先要先知道Game of Life(康威生命遊戲)的定義是什麼，找維基百科來描述的話:

  1. 當前細胞為存活狀態時，當周圍低於2個（不包含2個）存活細胞時， 該細胞變成死亡狀態。（模擬生命數量稀少）
  2. 當前細胞為存活狀態時，當周圍有2個或3個存活細胞時， 該細胞保持原樣。
  3. 當前細胞為存活狀態時，當周圍有3個以上的存活細胞時，該細胞變成死亡狀態。（模擬生命數量過多）
  4. 當前細胞為死亡狀態時，當周圍有3個存活細胞時，該細胞變成存活狀態。 （模擬繁殖）

而且題目有要求要直接在原本的資料陣列中做修改，但修改前面的資料後面在做判斷又可能會受到影響，因此需要一個可以修改資料，後面的資料又能得知原始資料的方法，這邊就需要重新定義原本儲存資料的格式如下:

1
2
3
4
die  → die    0  (0與原本相符代表死亡)
live → live   1  (1與原本相符代表存活)
die  → live   2
live → die    3

這邊我想得到的格式是如果細胞從頭到尾都是死亡為0，而從頭到尾都是存活則為1，至於從死亡變成存活及從存活變為死亡則分別為2與3，有了新的格式之後便能從頭開始遍歷，並藉由周圍狀況判斷細胞的下一個狀態來修改資料，又不會影響後續其它細胞的結果，最後只要再重新遍歷一次將2與3的情況改為1與0，整個生命遊戲便順利完成到了下一個階段。

程式碼解說:

如思路所述，我們重新定義原本儲存資料的格式，而如果剛好狀態是0(死亡→死亡)與1(存活→存活)便不需要做修改(因為本來的0與1就是分別代表死亡與存活)，所以我們只要針對2(死亡→存活)與3(存活→死亡)的情況就好，一開始便從頭開始遍歷，並藉由周圍狀況(這邊帶入一個自訂函數來回傳周圍的存活總數，其中後兩個代入的參數為該細胞的位置)判斷細胞的下一個狀態來修改資料，如果周圍的存活總數小於2或大於3表示該細胞會死亡，原本又是存活狀態的話便將該位置的值改成3(存活→死亡)，而如果周圍的存活總數為3又剛好原本是死亡的狀態，便將該位置的值改成2(死亡→存活)，最後只要再重新遍歷一次將2與3的情況改為1與0，整個生命遊戲便順利完成到了下一個階段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func gameOfLife(board [][]int) {
	var lives int
	for i, m := range board {
		for j, n := range m {
			lives = neighborsLives(board, i, j)
			if lives < 2 || lives > 3 {
				if n == 1 {
					board[i][j] = 3
				}
			} else if n == 0 && lives == 3 {
				board[i][j] = 2
			}
		}
	}
	for i, m := range board {
		for j, n := range m {
			if n == 2 {
				board[i][j] = 1
			} else if n == 3 {
				board[i][j] = 0
			}
		}
	}
}

這邊的函數就是檢查該細胞周圍的存活狀況，8個位置的檢查順序分別是左上、中上、右上、左邊、右邊、左下、中下、右下，並且每次都要確定檢查的位置是否在二元陣列的範圍之內(也就是是否存在)，如果該位置存在而且細胞是處於存活的狀態，便將存活的總計數器+1，唯一要注意的是資料有可能經過修改變成我們自己定義的情況，所以除了1不論是原始資料(存活)還是修改過的格式(存活→存活)都肯定是存活沒有問題，另外3(存活→死亡)因為是依原始資料來判斷，所以也要記得當作存活的細胞來計算，最後待全數檢查完畢便向上回傳該細胞周圍的存活總數

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
func neighborsLives(board [][]int, i int, j int) int {
	var lives int
	if i > 0 {
		if j > 0 && (board[i-1][j-1] == 1 || board[i-1][j-1] == 3) {
			lives++
		}
		if board[i-1][j] == 1 || board[i-1][j] == 3 {
			lives++
		}
		if j < len(board[0])-1 && (board[i-1][j+1] == 1 || board[i-1][j+1] == 3) {
			lives++
		}
	}
	if j > 0 && (board[i][j-1] == 1 || board[i][j-1] == 3) {
		lives++
	}
	if j < len(board[0])-1 && (board[i][j+1] == 1 || board[i][j+1] == 3) {
		lives++
	}
	if i < len(board)-1 {
		if j > 0 && (board[i+1][j-1] == 1 || board[i+1][j-1] == 3) {
			lives++
		}
		if board[i+1][j] == 1 || board[i+1][j] == 3 {
			lives++
		}
		if j < len(board[0])-1 && (board[i+1][j+1] == 1 || board[i+1][j+1] == 3) {
			lives++
		}
	}
	return lives
}

完整程式碼:

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
49
50
51
52
53
54
55
56
func gameOfLife(board [][]int) {
	var lives int
	for i, m := range board {
		for j, n := range m {
			lives = neighborsLives(board, i, j)
			if lives < 2 || lives > 3 {
				if n == 1 {
					board[i][j] = 3
				}
			} else if n == 0 && lives == 3 {
				board[i][j] = 2
			}
		}
	}
	for i, m := range board {
		for j, n := range m {
			if n == 2 {
				board[i][j] = 1
			} else if n == 3 {
				board[i][j] = 0
			}
		}
	}
}
func neighborsLives(board [][]int, i int, j int) int {
	var lives int
	if i > 0 {
		if j > 0 && (board[i-1][j-1] == 1 || board[i-1][j-1] == 3) {
			lives++
		}
		if board[i-1][j] == 1 || board[i-1][j] == 3 {
			lives++
		}
		if j < len(board[0])-1 && (board[i-1][j+1] == 1 || board[i-1][j+1] == 3) {
			lives++
		}
	}
	if j > 0 && (board[i][j-1] == 1 || board[i][j-1] == 3) {
		lives++
	}
	if j < len(board[0])-1 && (board[i][j+1] == 1 || board[i][j+1] == 3) {
		lives++
	}
	if i < len(board)-1 {
		if j > 0 && (board[i+1][j-1] == 1 || board[i+1][j-1] == 3) {
			lives++
		}
		if board[i+1][j] == 1 || board[i+1][j] == 3 {
			lives++
		}
		if j < len(board[0])-1 && (board[i+1][j+1] == 1 || board[i+1][j+1] == 3) {
			lives++
		}
	}
	return lives
}

總結:

如果要將Game of Life(康威生命遊戲)的二元陣列資料推往下一個階段，又要求只能直接在原本的資料陣列中做修改，有可能會因為修改前面的資料而導致後面的判斷受到影響，因此需要重新定義原本儲存資料的格式，從原本的0與1代表細胞的死亡與存活，變成用4個數字來代表細胞的變化過程(死亡→死亡、存活→存活、死亡→存活、存活→死亡)，最後待全數細胞的狀況都已修改至下一個狀態，接下來只要再重新遍歷一次將4個數字對應過程的最終情況改回0(死亡)與1(存活)，整個生命遊戲便順利完成到了下一個階段。

分享到