Game of Life

For the rule of Game of Life see its Wikipedia page.

Cells in the grid are either alive or dead in their origin state. They will evolve based on the number of their neighbors (8 neighbors) that are alive (and hence dead). The evolution to the next state is done simultaneously for every cell.

The algorithm just check for every cell the number of its neighbors that are alivee. Given the input rules, if the cell should evolve in next state, we store the cell index. As the evolution is done simultaneously for every cell we should wait until the end of the check of every cell before modifying the states of the cells (otherwise one modification on a cell at the begining of the loop would impact the next cells and it would no longer be a simultaneous evolution).

def gameOfLife(board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """

    # to_modify keeps cells  to modify, do not modify in the loop as it would impact other cells and the change of state should be simualtenous
    to_modify = set()
    for i in range(len(board)):
        for j in range(len(board[0])):
            curr_sum = 0

            # upper row
            if i >= 1:
                curr_sum += board[i-1][j] # upper middle 
                if j >= 1:
                    curr_sum += board[i-1][j-1] # upper left
                if j < len(board[0]) - 1:
                    curr_sum += board[i-1][j+1] # upper right

            # middle row
            if j >= 1:
                curr_sum += board[i][j-1] # middle left
            if j < len(board[0]) - 1:
                curr_sum += board[i][j+1] # middle right

            # lower row
            if i < len(board) - 1:
                curr_sum += board[i+1][j] # lower middle
                if j >= 1:
                    curr_sum += board[i+1][j-1] # lower left
                if j < len(board[0]) - 1:
                    curr_sum += board[i+1][j+1] # lower right

            # check sum of neighbors and given the rules add this cell to 'to_modify'
            match board[i][j]:
                case 0:
                    if curr_sum == 3:
                        to_modify.add((i, j))
                case 1:
                    if curr_sum < 2 or curr_sum > 3:
                        to_modify.add((i, j))

    for (i, j) in to_modify:
        board[i][j] = 1 - board[i][j]