[LeetCode] 289. Game of Life

 Problem : https://leetcode.com/problems/game-of-life/

Use bit mask to save the next-state on high-order bits.

Time Complexity = O ( M * N )

Space Complexity = O ( 1 )

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        ROW = len(board)
        if ROW == 0: return 
        
        COLUMN = len(board[0])
        if COLUMN == 0: return
        
        def alive(y,x):
            return 0 <= y < ROW and 0 <= x < COLUMN and board[y][x] & 1 == 1
        
        def nextState(y,x):
            aliveCount = 0
            
            for dy in [-1, 0, 1]:
                for dx in [-1, 0, 1]:
                    if dy == 0 and dx == 0:
                        continue
                    
                    if alive(y+dy, x+dx):
                        aliveCount += 1
            
            """
            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.
            """
            
            # dead
            nextState = 0
            
            if board[y][x] == 1:
                if aliveCount < 2:
                    # dead
                    pass
                elif 2 <= aliveCount <= 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            else:
                if aliveCount == 3:
                    # alive
                    nextState = 1 << 3
                else:
                    # dead
                    pass
            
            board[y][x] |= nextState
                    
        
        def normalizeState(y,x):
            board[y][x] = 1 if board[y][x] & (1<<3) else 0
        
        for y in range(ROW):
            for x in range(COLUMN):
                nextState(y, x)
        
        for y in range(ROW):
            for x in range(COLUMN):
                normalizeState(y, x)