Last Updated: 25 Feb, 2021
Game Of Life
Moderate
Asked in companies
You’re given a board of N * M size. Each element of this board is represented by either 0 or 1, where 0 means ‘dead’ and 1 means ‘live’. Each element can interact with all of its eight neighbors using the following four rules.
If any live cell has less than two live neighbors, then it dies.
If any live cell has two or three live neighbors, then it lives onto the next generation.
If any live cell has more than three live neighbors, then it dies.
A dead element with exactly three live neighbors becomes a live element.
Your task is to print the next state of this board using these four rules.
Input Format :
The first line of the input contains an integer T denoting the number of test cases.
The first line of every test case contains two space-separated integers N and M, denoting the number of rows and columns, respectively.
The next N lines of each test case contain M space-separated integers denoting the elements of the board.
Output Format :
For every test case, print the next state of the board using the four rules described in the problem statement.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= M, N <= 1000
Time limit: 1 sec
Approaches
1. Start by creating two arrays, “xDirections” and “yDirections,” containing all the neighbors’ possible directions.
“xDirections” = {0, 0, 1, 1 ,1, -1, -1, -1}
“yDirections” = {1, -1, 1, -1, 0, 0, 1, -1}
2. Run a loop(loop variable ‘i’) from 0 till N.
3. Run another loop inside the above loop(loop variable ‘j’) from 0 till M.
- Make an integer variable “liveCount” to keep track of the live elements, i.e., elements with the value ‘1’.
- Now run a loop(loop variable ‘k’) from 0 till 8 to visit all the neighbors.
- Make a variable “currentX” = i + xDirections[k], which will store the x coordinate of the current neighborhood element. Similarly, make another variable “currentY” = j + yDirections[k],which will store the y coordinate of the current neighborhood element.
- Increment “liveCount” by one only when it satisfies the following two conditions:
- The current element is a live element, i.e., the current element’s absolute value is ‘1’.
- “currentX” and “currentY” are within the board, i.e., the current element lies inside the board.
- Now, check if the current element satisfies Rule 4, i.e if board[i][j] = 0(dead) and it has exactly three neighbours(“liveCount” = 3). If this condition is true, update board[i][j] = 2. Hence, board[i][j] = 2 will indicate a element that is now live but was dead earlier.
- Similarly, check if the current element satisfies Rule 1 and 3, i.e., board[i][j] = 1, the number of live neighbors(“liveCount”) is either less than 2 or greater than 3. If this condition is true then update board[i][j] = -1. Hence, board[i][j] = -1 will indicate a element which is now dead but was live earlier.
- We do not need to check if the current element satisfies Rule 2 since it will be automatically taken care of after checking Rule 1 and Rule 3.
4. After exiting all the above loops, we’ll now perform the following operations to get the board’s next state.
5. Run a loop(loop variable ‘i’) from 0 till N.
- Run a nested loop inside the above loop(loop variable ‘j’) from 0 till M.
- If board[i][j] >= 1, update board[i][j] = 1 , which means this element will be live in the next state.
- Else update board[i][j] = 0, which means that this element will be dead in the next state.
6. Return “board,” the next state of the board.