Today is the 102nd day of xiaohao algorithm “365 brush question plan”. Everyone starts and ends at the same place, but the process is different. We can’t control life and death but we can choose what makes life meaningful. How do we use algorithms to play a game of life?
01. Examples of topics
The Game of Life is a cellular automaton invented by British mathematician John Holden Conway in 1970.
| Question 289: The Game of life |
|---|
| 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;
Write a function to calculate the next (after an update) state of all cells on the panel based on the current state. 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.
The topic is a bit complicated, for example:
Note: 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.
02, Solution analysis
The key point of this problem is that all the panels need to be updated at the same time
The complexity of this problem mainly lies in the four update rules, so we need to master the four rules first (we only illustrate the elements highlighted in green below).
- R1: If the number of cells is less than two, the living cells at this location die
- R2: If there are two or three living cells, the site is still alive
- R3: If there are more than three living cells, the living cells in that location die
- R4: If there are three living cells, the dead cells at that location are resurrected
The four rules are not complicated to understand. Now consider how to solve the problem. The most natural idea is to update the cellular state one by one.
But here we run into a problem: suppose that every time you update, you fill the array with the updated result. Updates to other cells in the current round will refer to the results you have already updated. What does that mean?
For example, the above is incorrect: we first update the status of the green box according to rule 4, and then the color around the blue box also satisfies rule 4. The state of the updated cell will affect the calculation of the state of other surrounding cells that have not been updated. This is clearly not what we want!
The simplest way to think about it is: as long as we can always get the original array data, we can guarantee that the update is always correct! It’s ok to copy an array or store values in a HashMap.
Because this idea is relatively simple, I will directly on the leetcode official solution of the code:
class Solution {
public void gameOfLife(int[][] board) {
int[] neighbors = {0.1, -1};
int rows = board.length;
int cols = board[0].length;
// Create a copy array copyBoard
int[][] copyBoard = new int[rows][cols];
// Copy a copy from the original array to the copyBoard
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
copyBoard[row][col] = board[row][col];
}
}
// Walk through the cells in each cell of the panel
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// For each cell count the number of living cells in its eight adjacent locations
int liveNeighbors = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(! (neighbors[i] ==0 && neighbors[j] == 0)) {
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
// Check whether adjacent cells are alive
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1)) {
liveNeighbors += 1;
}
}
}
}
// Rule 1 or Rule 3
if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[row][col] = 0;
}
/ / rule 4
if (copyBoard[row][col] == 0 && liveNeighbors == 3) {
board[row][col] = 1;
}
}
}
}
}
Copy the codeThen an interesting thing happened. The reason why a great god is a great god is that the great god’s thinking is different from ordinary people. Big god says, you this kind of method can be ok, but take up new space.
You can save the state of the original array and update the new state. All of this can be done on top of the original array. So how do we do that?
- Didn’t the original 0 and 1 stand for death and life? But if you want to update a new status, it is from birth -> death, from death -> life. So let’s add a state 2, which means alive > dead, and a state 3, which means dead > alive.
- For a node, if the point around it is 1 or 2, that point was alive in the previous round.
- The overall strategy is the process of completing the original -> transition -> real state.
- Transitioning to the real state, the code is just changing 0 and 2 back to 0, 1 and 3 back to 1. Using modules is just a code trick.
- The first step in policy implementation is to find the number of surviving nodes around the current node.
The code looks something like this:
//JAVA
public class Solution {
public void gameOfLife(int[][] board) {
int m = board.length, n = board[0].length;
// Original state -> Transition state
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int liveNeighbors = 0;
// Check above
if(i > 0) {
liveNeighbors += board[i - 1][j] == 1 || board[i - 1][j] == 2 ? 1 : 0;
}
// Determine the left side
if(j > 0) {
liveNeighbors += board[i][j - 1] = =1 || board[i][j - 1] = =2 ? 1 : 0;
}
// Check below
if(i < m - 1) {
liveNeighbors += board[i + 1][j] == 1 || board[i + 1][j] == 2 ? 1 : 0;
}
// Check the right side
if(j < n - 1) {
liveNeighbors += board[i][j + 1] = =1 || board[i][j + 1] = =2 ? 1 : 0;
}
// Determine the upper left corner
if(i > 0 && j > 0) {
liveNeighbors += board[i - 1][j - 1] = =1 || board[i - 1][j - 1] = =2 ? 1 : 0;
}
// Determine the lower right corner
if(i < m - 1 && j < n - 1) {
liveNeighbors += board[i + 1][j + 1] = =1 || board[i + 1][j + 1] = =2 ? 1 : 0;
}
// Determine the upper right corner
if(i > 0 && j < n - 1) {
liveNeighbors += board[i - 1][j + 1] = =1 || board[i - 1][j + 1] = =2 ? 1 : 0;
}
// Determine the lower left corner
if(i < m - 1 && j > 0) {
liveNeighbors += board[i + 1][j - 1] = =1 || board[i + 1][j - 1] = =2 ? 1 : 0;
}
// The current point is updated according to the number of surrounding lives, and the result is 0 and 1
if(board[i][j] == 0 && liveNeighbors == 3) {
board[i][j] = 3;
} else if(board[i][j] == 1) {
if(liveNeighbors < 2 || liveNeighbors > 3) board[i][j] = 2;
}
}
}
// Transition status -> Real status
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
board[i][j] = board[i][j] % 2;
}
}
}
}
Copy the codeExecution Result:
Careful readers might think, isn’t that the Carnot diagram? Yes. In most matrix state change problems, kano diagrams, state machines, etc., are some commonly used techniques.
The general general solution is:
1. Most of them traverse the matrix twice, introducing intermediate values (intermediate states) in the first pass and storing some additional information not contained in the original matrix.
2. Set the intermediate state to the real state at the end using the strategy of original matrix -> transition matrix -> real matrix.
3. When traversing a certain position, it is necessary to check the position around it. At this time, if every position around it is handwritten, and then judge whether it is out of bounds, it is very troublesome. An array is usually used to hold the offset values of the coordinates that change to the surrounding positions.
4, If it is a state permutation of 0 and 1, we can use the bit operation to show the operation. If there are too many states involved, consider whether you can simplify the states.
Anyway: this is a relatively classic problem, if you are interested, you can practice the 73 matrix zero, is also a similar solution.
03. Daily algorithms
Width-first search algorithm (also known as breadth first search) is one of the simplest search algorithms for graphs, and it is also the prototype of many important graph algorithms. Dijkstra’s single-source shortest path algorithm and Prim’s minimum spanning tree algorithm both use a similar idea to width-first search. BFS, also known as BFS, is a blind search method that systematically unrolls and examines all nodes in a graph for results. In other words, it does not consider the possible location of the result and thoroughly searches the whole graph until it finds the result.
That’s the end of today’s topic, have you learned? Leave your thoughts in the comments section!
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download
