0289. Game of Life (Medium)

Question

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. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input:
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output:
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

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?

分析/解題

這題是典型的生命遊戲 題目。生命遊戲一般是透過2D的棋盤式的格子，
上面以1代表活著的細胞，0代表死去的細胞，
透過設定好的規則來觀察其演化的狀況。
設定這些東西的目的最初應該是為了要產生模擬圖靈機，
後來發現一些有趣的現象，比如能穩定周期性的圖案像是滑翔機、
機關槍等等，也有的看似是有周期的但最後會消滅的狀況，
總之某種層面上有點像是可以拿來模擬族群聚落的演進等狀態就是了，
有興趣的讀者可以再看看相關的資料。

回到題目，基本上生命遊戲裡面的每個單位，
在下一個時間點要嘛是1(活著)，不然就是0(死去)。
典型的規則是看其九宮格的周圍：

1. 如果原本自己是1(活著) 的話，只有周圍有2~3個 鄰居(活著的細胞)，
   下一刻自己才會繼續存活，否則就會死去。
   (只有1個鄰居以下會因人口過少而死，
   而超過3個鄰居會因人口過多而死)

2. 如果原本自己是0(死去) 的話，只有周圍恰好有3個鄰居 ，
   下一刻自己會變成1(活著) (視作被繁衍出來的後代)

Follow up有兩點，1是詢問是否能in-place解題，
2是棋盤是無窮大的話該怎麼描述問題。

這個題目其實看懂定義的話並不困難，只是繁瑣而已。
首先有一個重點是：更新的時候必須要一口氣一起更新，
因為每個細胞的變化都需要看周圍的細胞，不同時改變的話，
結果就有可能會出錯。這邊有兩種考慮方式：

1. 開一個跟board一樣大的二維陣列(串列)，
   記錄下一刻的狀態，最後再進行替換。
2. 想辦法用原有的board 來進行記錄。
   我們這邊因為希望達成in-place，所以自然選擇2。
   還記得之前我們提過的word search嗎？
   我們利用了沒有被用到的位元做為遮罩進行XOR，
   使得visited的資訊用原先的棋盤就可以做記錄了；
   這邊比之前還要簡單，我們只要拿2的1次方位 來記錄即可，
   因為board一開始只用到1和0而已 ，所以判斷完以後，
   如果它會變成存活的狀態，則將該值加上2，
   死去的話則不用額外動作。
   這樣一來，最後我們只要將整個board除以2取整數 ，
   就可以得到新的棋盤狀態了！
   中間在進行周圍八格的判斷時，不要忘記要除以2取餘數 。

所以總體會像這樣：

1. 遍歷整個棋盤做check
2. check 函式中:
    a. 依次檢查是否存活(alive)，並加總 周圍八格的存活細胞數量
    b. 若本身當前存活 -> 檢查** 周圍存活數是 2或3時， 將自己加上2**
    c. 否則(本身死亡 )，若周圍存活數 是3 ，將自己加上2
3. alive 函式中:
    a. 若超出邊界則回傳0
    b. 否則回傳該格數值除以2的餘數
4. 全數檢查完後呼叫next 函式更新狀態
5. next 函式: 遍歷整個棋盤，將值除以2取整數 。

一般典型的話理論上邊界應該要互相連接，
(走到最底會通往最上面，走到最右邊會連通最左邊)
但我們這邊就不考慮這個問題了。

Java

Java的部分，計算八方向我們使用了一個d(direction)的二維陣列來記錄，
除了邊界條件以外沒有特別需要注意的地方。

Python

Python的部分，d的方面我們可以用list comprehension ，
扣掉自身(0, 0)來建構。除了留意子函式的定義，
要在拿來做為global的部分後面(才能拿來用) ，
在呼叫之前(因為是腳本執行) 以外，
其他沒有什麼特別的地方XD

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(m * n), O(1))

「如果棋盤無限大？」
(那應該要找出一個pattern來表示它才對，
不可能真的開出一個無限大的棋盤)

「首尾相接的話？」
(Python直接按照負數index會發生的事情處理，
Java要自己計算過界的狀況)

「還能簡化嗎？」
(理論上相鄰的兩個點會共用到4個鄰居點 ，
應該可以再節省一點計算時間，但時間複雜度是一樣的 )

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
第二階段Medium優惠(額滿即截止)： https://hiskio.com/courses/319?promo_code=VEQZV7E