289. Game of Life

The board is made up of an m x n grid of cells

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.

Notice: We need to assign decode[0] and decode[1] manually.

We need this in counting how many alive around a cell

and for the cells that are still holding original value

     we still need to decode them. So 0->0 and 1->1

def gameOfLife(self, board: List[List[int]]):        

    m, n = len(board), len(board[0])        

    encode = {

        (0,0): 2, # Nothing happening to dead

        (0,1): 3, # Rule-4: Comes alive

        (1,1): 4, # Rule-2: lives

        (1,0): 5  # Rule-1 and 3: dies due to under/over population

    }    

   

    decode = {v:k for k,v in encode.items()}

    decode[0] = (0, 99) # 99 doesn't matter

    decode[1] = (1, 99)

   

    def countAliveNeighbors(x, y, m, n):

               

        vectors = [0,1,-1]

        vectors = set(itertools.product(vectors, vectors))

        vectors.remove((0,0))

       

        def valid(i,j):

            return i>=0 and i < m and j >=0 and j <n

       

        count = 0

        for dx, dy in vectors:

            if valid(x+dx, y+dy):

                prev, _ = decode[board[x+dx][y+dy]]

                count += prev    

        return count

   

    for r in range(m):

        for c in range(n):

            alive_n = countAliveNeighbors(r, c, m, n)

            if board[r][c]==1:

                if alive_n < 2:

                    board[r][c] = encode[(1,0)]

                elif alive_n == 2 or alive_n == 3:

                    board[r][c] = encode[(1,1)]

                else:

                    board[r][c] = encode[(1,0)]

            else:

                if alive_n == 3:

                    board[r][c] = encode[(0,1)]

                else:

                    board[r][c] = encode[(0,0)]

                   

    for r in range(m):

        for c in range(n):

            _, board[r][c] = decode[board[r][c]]