289.Game of Life
Tags: [implementation], [matrix], [board], [encode], [in_place]
Com: {g}
Link: https://leetcode.com/problems/game-of-life/#/description
According to the[Wikipedia's article]([[https://en.wikipedia.org/wiki/Conway's_Game_of_Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life)](https://en.wikipedia.org/wiki/Conway's_Game_of_Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life))\): "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.
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?
Better Solution: Encoding, Iterate Eight Neighbors
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
# encoding:
# (1) Die => Die: -3
# (2) Die => Live: -300
# (3) Live => Live: 300
# (4) Live => Die: 3
# so if board[][] <= 0 means the current state is Die
# if board[][] >= 1 means the current state is Live
# so if abs(board[][]) == 3 means the next state is Die
# if abs(board[][]) == 300 means the next state is Live
DIE_TO_DIE = -3
DIE_TO_LIVE = -300
LIVE_TO_LIVE = 300
LIVE_TO_DIE = 3
num_of_rows = len(board)
num_of_cols = len(board[0])
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
num_of_live_neighbors = self.get_num_of_live_neighbors(board, num_of_rows, num_of_cols, row, col)
if board[row][col] == 1:
if num_of_live_neighbors < 2 or num_of_live_neighbors > 3:
board[row][col] = LIVE_TO_DIE
else:
# num_of_live_neighbors == 2 or 3.
board[row][col] = LIVE_TO_LIVE
else:
# board[row][col] == 0
if num_of_live_neighbors == 3:
board[row][col] = DIE_TO_LIVE
else:
board[row][col] = DIE_TO_DIE
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
board[row][col] = 0 if abs(board[row][col]) == 3 else 1
def get_num_of_live_neighbors(self, board, num_of_rows, num_of_cols, start_row, start_col):
counter = 0
# iterate eight directions.
row = max(0, start_row - 1)
while row <= min(num_of_rows - 1, start_row + 1):
col = max(0, start_col - 1)
while col <= min(num_of_cols - 1, start_col + 1):
if not (row == start_row and col == start_col) and board[row][col] >= 1:
counter += 1
col += 1
row += 1
return counter
Revelation:
- Be careful of 'not (row == start_row and col == start_col) and board[row][col] >= 1'.
Better Solution: Encoding
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
# encoding:
# (1) Die => Die: -3
# (2) Die => Live: -300
# (3) Live => Live: 300
# (4) Live => Die: 3
# so if board[][] <= 0 means the current state is Die
# if board[][] >= 1 means the current state is Live
# so if abs(board[][]) == 3 means the next state is Die
# if abs(board[][]) == 300 means the next state is Live
DIE_TO_DIE = -3
DIE_TO_LIVE = -300
LIVE_TO_LIVE = 300
LIVE_TO_DIE = 3
num_of_rows = len(board)
num_of_cols = len(board[0])
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
num_of_live_neighbors = self.get_num_of_live_neighbors(board, num_of_rows, num_of_cols, row, col)
if board[row][col] == 1:
if num_of_live_neighbors < 2 or num_of_live_neighbors > 3:
board[row][col] = LIVE_TO_DIE
else:
# num_of_live_neighbors == 2 or 3.
board[row][col] = LIVE_TO_LIVE
else:
# board[row][col] == 0
if num_of_live_neighbors == 3:
board[row][col] = DIE_TO_LIVE
else:
board[row][col] = DIE_TO_DIE
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
board[row][col] = 0 if abs(board[row][col]) == 3 else 1
def get_num_of_live_neighbors(self, board, num_of_rows, num_of_cols, row, col):
counter = 0
# top
if row - 1 >= 0 and board[row - 1][col] >= 1:
counter += 1
# left
if col - 1 >= 0 and board[row][col - 1] >= 1:
counter += 1
# bottom
if row + 1 < num_of_rows and board[row + 1][col] >= 1:
counter += 1
# right
if col + 1 < num_of_cols and board[row][col + 1] >= 1:
counter += 1
# top-left
if row - 1 >= 0 and col - 1 >= 0 and board[row - 1][col - 1] >= 1:
counter += 1
# top-right
if row - 1 >= 0 and col + 1 < num_of_cols and board[row - 1][col + 1] >= 1:
counter += 1
# bottom-left
if row + 1 < num_of_rows and col - 1 >= 0 and board[row + 1][col - 1] >= 1:
counter += 1
# bottom-right
if row + 1 < num_of_rows and col + 1 < num_of_cols and board[row + 1][col + 1] >= 1:
counter += 1
return counter
Revelation:
- Choose a good way to encode the states.
Note:
- Time complexity = O(n), n is the total number of elements in the given board.
Solution:
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
num_of_rows = len(board)
num_of_cols = len(board[0])
next_gen_board = [[0 for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
num_of_live_neighbors = self.count_live_neighbors(board, row, col, num_of_rows, num_of_cols)
if not board[row][col]:
if num_of_live_neighbors == 3:
next_gen_board[row][col] = 1
else:
if 2 <= num_of_live_neighbors <= 3:
next_gen_board[row][col] = 1
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
board[row][col] = next_gen_board[row][col]
def count_live_neighbors(self, board, row, col, num_of_rows, num_of_cols):
counter = 0
if row - 1 >= 0:
if board[row - 1][col]:
counter += 1
if col - 1 >= 0 and board[row - 1][col - 1]:
counter += 1
if col + 1 < num_of_cols and board[row - 1][col + 1]:
counter += 1
if row + 1 < num_of_rows:
if board[row + 1][col]:
counter += 1
if col - 1 >= 0 and board[row + 1][col - 1]:
counter += 1
if col + 1 < num_of_cols and board[row + 1][col + 1]:
counter += 1
if col - 1 >= 0 and board[row][col - 1]:
counter += 1
if col + 1 < num_of_cols and board[row][col + 1]:
counter += 1
return counter
Note:
- Time complexity = O(m*n), m is the number of rows and n is the number of cols of the given board.
Solution: In-place, Encode
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
num_of_rows = len(board)
num_of_cols = len(board[0])
# 0 means: current state is die.
# 1 means: current state is live.
# 2 means: die -> live.
# 3 means: live -> die.
# 4 means: die -> die.
# 5 means: live -> live.
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
cell = board[row][col]
if cell <= 1:
# this cell has not been updated
num_of_curr_gen_live_neighbors = self.count_curr_gen_live_neighbors(board,
num_of_rows,
num_of_cols,
row, col)
if num_of_curr_gen_live_neighbors < 2 or num_of_curr_gen_live_neighbors > 3:
if cell:
board[row][col] = 3
else:
board[row][col] = 4
elif not cell and num_of_curr_gen_live_neighbors == 3:
board[row][col] = 2
else:
board[row][col] = cell + 4
for row in xrange(num_of_rows):
for col in xrange(num_of_cols):
cell = board[row][col]
if cell == 3 or cell == 4:
board[row][col] = 0
else:
board[row][col] = 1
def count_curr_gen_live_neighbors(self, board, num_of_rows, num_of_cols, row, col):
counter = 0
if row - 1 >= 0:
if board[row - 1][col] == 1 or board[row - 1][col] == 3 or board[row - 1][col] == 5:
counter += 1
if col - 1 >= 0:
if board[row - 1][col - 1] == 1 or board[row - 1][col - 1] == 3 or board[row - 1][col - 1] == 5:
counter += 1
if col + 1 < num_of_cols:
if board[row - 1][col + 1] == 1 or board[row - 1][col + 1] == 3 or board[row - 1][col + 1] == 5:
counter += 1
if row + 1 < num_of_rows:
if board[row + 1][col] == 1 or board[row + 1][col] == 3 or board[row + 1][col] == 5:
counter += 1
if col - 1 >= 0:
if board[row + 1][col - 1] == 1 or board[row + 1][col - 1] == 3 or board[row + 1][col - 1] == 5:
counter += 1
if col + 1 < num_of_cols:
if board[row + 1][col + 1] == 1 or board[row + 1][col + 1] == 3 or board[row + 1][col + 1] == 5:
counter += 1
if col - 1 >= 0:
if board[row][col - 1] == 1 or board[row][col - 1] == 3 or board[row][col - 1] == 5:
counter += 1
if col + 1 < num_of_cols:
if board[row][col + 1] == 1 or board[row][col + 1] == 3 or board[row][col + 1] == 5:
counter += 1
return counter
Revelation:
- Encode all states changes.
Note:
- Time complexity = O(m * n), m is the number of rows, and n is the number of cols.