289. Game of Life - cocoder39/coco39_LC GitHub Wiki

289. Game of Life

Notes 2022:

Follow up: infinite board

  1. 假设我们能吧整个sparse matrix 读进memory where sparse matrix 只存live cells

    • challenge: how to derive next state from merely live cells
    • solution:
      • for every live cell, count live cells from it's 8 neighbor cells
      • if live neighbors is 2 and current cell is live -> next state is live
      • if live neighbors is 3 -> next state is live no matter current state is live or not
        • if current is live, yes it is correct according to the rule
        • if current is dead, yes it is correct according to the rule
        • question: would this miss some dead cells which were surrounded by 3 live cells?
          • if such case exists, it means the dead cell is a neighbor of a live cell so we have taken care of it at step 1 where we check the 8 neighbors of every live cell

  2. what if the sparse matrix can not fit into memory?

    • read 3 lines so the line in middles has its 8 neighbors available

Originally the board use 0 to represent dead and 1 to represent dead. We need represent next state of each cell while doesn't hide current state. Besides, we are asked to do it in place.
Be aware that each cell occupies only 1-bit to represent its state while an int is given. Thus we can use int to represent more than one state since 1-bit is enough for a state

[high bit, low bit] = [next state <- current state] where 0 is dead and 1 is live
[0 0] = [dead <- dead](default)    [0 1] = [dead <- live](default)
[1 0] = [live <- dead]             [1 1] = [live <- live]
  • By default, every cell is eight in [0 0] or [0 1]. In other words, either live or dead now, default next state is dead
  • The goal is setting high bit based on low bit. In other words, determine next state based on current state.
  • default transition for dead cell is 0 -> 0, thus we only care about 0 -> 1. Meanwhile default transition for live cell is 1 -> 0, therefore we only care about 1 -> 1
  • get cur state by & 1, get next state by >> 1 
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int lives = neighbor(board, m, n, i, j);
                if (board[i][j] == 1 && lives >= 2 && lives <= 3) //cur state is live
                    board[i][j] = 3;
                else if (board[i][j] == 0 && lives == 3) //cur state is dead
                    board[i][j] = 2;
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] >>= 1;
            }
        }
    }
private:
    int neighbor(vector<vector<int>>& board, int m, int n, int row, int col) {
        int lives = 0;
        for (auto dir : dirs) {
            int i = row + dir.first;
            int j = col + dir.second;
            if (i >= 0 && i < m && j >= 0 && j < n)
                lives += board[i][j] & 1;
        }
        return lives;
    }
    const vector<pair<int, int>> dirs{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
};

what is bool matrix is given? well, we can use roll vector, 3 rows of memory are used to store neighbor's state

⚠️ **GitHub.com Fallback** ⚠️