Game of Life
Problem
Each cell is live (1) or dead (0). All cells update at the same time: a live cell with 2 or 3 live neighbours (out of 8) survives, otherwise it dies; a dead cell with exactly 3 live neighbours becomes live. Compute the next state in place.
Example 1
Input: [[0,1,0], [0,0,1], [1,1,1], [0,0,0]] Output: [[0,0,0], [1,0,1], [0,1,1], [0,1,0]]
Test cases
Case 1
Input: [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] Expected: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Case 2
Input: [[1,1],[1,0]] Expected: [[1,1],[1,1]]
Case 3
Input: [[1]] Expected: [[0]]
View solutionHide solution1 approach
1. In place with bit encoding
Time O(R·C)Space O(1)
Bit 0 holds the current state, bit 1 the next. Count live neighbours using (v & 1), write the next state into bit 1, then shift every cell right.
function gameOfLife(b) { const R = b.length, C = b[0].length; for (let r = 0; r < R; r++) { for (let c = 0; c < C; c++) { let live = 0; for (let dr = -1; dr <= 1; dr++) for (let dc = -1; dc <= 1; dc++) { if (!dr && !dc) continue; const nr = r + dr, nc = c + dc; if (nr >= 0 && nc >= 0 && nr < R && nc < C) live += b[nr][nc] & 1; } if (live === 3 || (live === 2 && (b[r][c] & 1))) b[r][c] |= 2; } } for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) b[r][c] >>= 1;}