Algorithms: The Game of Life

The Game of Life, or Life for short, is a cellular automaton invented by British mathematician John Holden Conway in 1970.

Given a panel of m by N cells, each cell can be thought of as a cell. Each cell has an initial state: 1 is live, or 0 is dead. Each cell and its eight adjacent cells (horizontal, vertical, and diagonal) follow the following four rules of survival:

• If there are less than two living cells at eight sites around a living cell, the living cells at that site die;
• If there are two or three living cells in eight locations around a living cell, that location is still alive;
• If there are more than three living cells in eight locations around a living cell, the living cells in that location die;
• If there are three living cells around the dead cell, the dead cell revives at that location;

The next state is formed by applying the above rules simultaneously to each cell in the current state, where cell birth and death occur simultaneously. Give you the current state of the m x N grid panel board, return to the next state.

Example 1:

Input: board = [[0, 0], [0, 1],,1,1 [1], [0, 0]] output: [[0, 0], [1, 1], [0,1,1], [0, 0]]Copy the code

Example 2:

Input: board = [1,1],[1,0]] output: [[1,1],[1,1]]Copy the code

Tip:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• Board [I][j] is 0 or 1

Advanced:

• Can you use the in situ algorithm to solve this problem? Note that all cells on the panel need to be updated at the same time: you cannot update some cells and then use their updated values to update others.
• In this case, we use a two-dimensional array to represent the panel. In principle, panels are infinite, but this can cause problems when living cells encroach on panel boundaries. How would you solve these problems?

To calculate the next state of the cell, it is necessary to obtain the state around each cell and calculate the next state of the cell in combination with the strategic conditions. The whole calculation process can be divided into three steps:

• To obtain the related (surrounding) cells of the current cell, a total of 8 cells, but the edge cells have to be considered, there is no special label can be used to represent
• According to the current cell state and the acquired surrounding cell state, the next state is calculated in combination with the update strategy
• Traverse all cells and repeat the first two steps

Define getNearCells to retrieve the cells around curRow and curCol. Those that do not exist are represented by an empty array []. For extensibility, each of the calculated nearby cells stores the index and the current state [rowIndex, colIndex, status].

@param {*} rowIndex @param {*} colIndex @param {*} board * @returns */ function GetNearCells (curRow, curCol, board) {// Count 8 positions clockwise from the top left, null array [] const nears = [] for (let startRow = currow-1; startRow <= curRow + 1; startRow++) { for (let startCol = curCol - 1; startCol <= curCol + 1; startCol++) { if (curRow === startRow && curCol === startCol) { continue } if (board[startRow] === undefined) { Nears.push ([])} else if (board[startRow][startCol] === undefined) {nears.push([])} else {// Store status and index, Nears. Push ([startRow, startCol, board[startRow][startCol]])}}} return nears}Copy the code

When traversing the surrounding cells, pay attention to the judgment condition, need to use undefined to determine whether the array is out of range, not not! , because the value of no is true even when the state is 0.

The calcNextStatus function is defined to obtain the next state of the cell. The parameters include the function getNearCells to calculate the list of surrounding cells. The strategy mainly determines the number of living cells, so the number of surrounding living cells is calculated first. Strategies can be divided into dead cell judgment and living cell judgment according to cell state.

@param {*} curCell * @param {peripheral cells} nearCells * @returns */ function calcNextStatus(curCell, nearCells) { const activeCellCount = nearCells.reduce((preVal, CurVal) => {if (curval. length === 3) {return preVal + curVal[2]} return preVal}, 0) const next = {// () => {const isEqualThree = activeCellCount === 3 return isEqualThree? 1: 0}, // The current cell state is 1, hit the live cell judgment strategy 1: () => { if (activeCellCount < 2) { return 0 } else if (activeCellCount === 2 || activeCellCount === 3) { return 1 } else  if (3 < activeCellCount) { return 0 } } } return next[curCell[2]]() }Copy the code

The code defines the next function, which contains two processing functions, 0 and 1, respectively representing the dead cell calculation strategy and the living cell calculation strategy. The judgment condition is relatively simple, which is directly realized by if/else. If the judgment is complicated, decision tree can be considered.

In the end, gameOfLife is defined to iterate over each cell, and the next state is obtained by combining getNearCells and calcNextStatus. It should be noted that the title requires that no result is returned, and the previous state set can be directly modified on the original array. You can copy the previous state set.

/** * @param {number[][]} board * @return {void} Do not return anything, modify board in-place instead. */ var gameOfLife = function(board) { if (! board.length || ! Board [0].length) {throw new Error(' grid format Error.')} // Copy const preBoard = json.parse (json.stringify (board)) const rowLen = board.length, colLen = board[0].length for (let rowIndex = 0; rowIndex < rowLen; rowIndex++) { preBoard[rowIndex] = preBoard[rowIndex] || [] for (let colIndex = 0; colIndex < colLen; colIndex++) { board[rowIndex][colIndex] = calcNextStatus([rowIndex, colIndex, preBoard[rowIndex][colIndex]], getNearCells(rowIndex, colIndex, preBoard)) } } }Copy the code

, by means of copy and traversal time complexity is O (m * n), and space complexity is O (m * n), when the cell number is larger copy way will take up a lot of memory, can consider to use a special status at the same time to identify the next state, a state, state from dead cells into living cells, for example, can be said that cell with 2 from death to life, This allows us to calculate the original state of the cell when we traverse other cells. But there are two things to consider:

• Finally, you need to traverse the cell again, setting the special marker 2 to 1
• The space complexity becomes O(1), but the time complexity also increases

Another idea is to change the way in which the surrounding cells influence the current cell from the original way in which the current cell influences the current cell to the way in which the current cell actively influences the surrounding cells. For example, if the current cell is a living cell, 10 can be added to the surrounding cells. For example, 41 means that there are four living cells around. But if you have a lot of cell states, it’s a little easier to write.