New Problem Solution - "Game of Life"

haoel · haoel · commit 054e4268593e · 2019-03-20T19:40:43.000+08:00
diff --git a/README.md b/README.md
@@ -148,6 +148,7 @@ LeetCode
 |295|[Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/) | [C++](./algorithms/cpp/findMedianFromDataStream/FindMedianFromDataStream.cpp)|Hard|
 |292|[Nim Game](https://leetcode.com/problems/nim-game/)  | [C++](./algorithms/cpp/nimGame/nimGame.cpp)|Easy|
 |290|[Word Pattern](https://leetcode.com/problems/word-pattern/) | [C++](./algorithms/cpp/wordPattern/WordPattern.cpp)|Easy|
+|289|[Game of Life](https://leetcode.com/problems/game-of-life/) | [C++](./algorithms/cpp/gameOfLife/GameOfLife.cpp)|Medium|
 |287|[Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)  | [C++](./algorithms/cpp/findTheDuplicateNumber/findTheDuplicateNumber.cpp), [Python](./algorithms/python/FindTheDuplicateNumber/findDuplicate.py)|Hard|
 |285|[Inorder Successor in BST](https://leetcode.com/problems/inorder-successor-in-bst/) &hearts; | [Java](./algorithms/java/src/inorderSuccessorInBST/inorderSuccessorInBST.java)|Medium|
 |284|[Peeking Iterator](https://leetcode.com/problems/peeking-iterator/)  | [C++](./algorithms/cpp/peekingIterator/PeekingIterator.cpp)|Medium|
@@ -408,3 +409,4 @@ LeetCode
 |---| ----- | -------- | ---------- |
 |1|[Search in a big sorted array](http://www.lintcode.com/en/problem/search-in-a-big-sorted-array/)|[Java](./algorithms/java/src/searchInABigSortedArray/searchInABigSortedArray.java)|Medium|
 |2|[Search Range in Binary Search Tree](http://www.lintcode.com/en/problem/search-range-in-binary-search-tree/) | [Java](./algorithms/java/src/searchRangeInBinarySearchTree/searchRangeInBinarySearchTree.java)|Medium|
+
diff --git a/algorithms/cpp/gameOfLife/GameOfLife.cpp b/algorithms/cpp/gameOfLife/GameOfLife.cpp
@@ -0,0 +1,94 @@
+// Source : https://leetcode.com/problems/game-of-life/
+// Author : Hao Chen
+// Date   : 2019-03-20
+
+/***************************************************************************************************** 
+ *
+ * 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. 
+ * 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:
+ * 
+ * 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:
+ * 
+ * 	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?
+ * 
+ ******************************************************************************************************/
+
+
+class Solution {
+public:
+    // the problem here is we need store two states in one cell,
+    // one is the original state, another is the new state
+    // So, we could store the state into the bit.
+    //  - Old State: the first  bit from the right
+    //  - New State: the second bit from the right
+    void liveCheck(vector<vector<int>>& board, int r, int c) {
+        int cnt = 0;
+        for (int i=r-1; i<=r+1; i++) {
+            if (i < 0 || i>=board.size()) continue;
+            for (int j=c-1; j<=c+1; j++) {
+                if (j<0 || j>=board[0].size() || (i==r && j==c)) continue;
+                if ( board[i][j] & 1 ) cnt++;
+            }
+        }
+
+        //live -> die
+        //if (board[r][c]==1 && (cnt < 2 || cnt > 3)) board[r][c] = 1;
+
+        //live -> live
+        if ( board[r][c] == 1 && (cnt == 2 || cnt == 3) ) board[r][c] = 3;
+
+        //die -> live
+        if ( board[r][c] == 0 && cnt == 3 ) board[r][c] = 2;
+
+    }
+
+    void gameOfLife(vector<vector<int>>& board) {
+        for (int i=0; i<board.size(); i++) {
+            for (int j=0; j<board[0].size(); j++) {
+                liveCheck(board, i, j);
+            }
+        }
+
+        for (int i=0; i<board.size(); i++) {
+            for (int j=0; j<board[0].size(); j++) {
+                board[i][j] >>= 1;
+            }
+
+        }
+
+    }
+};
