@@ -0,0 +1,2566 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * According to the Wikipedia's article: %22The Game of Life, also known simply as Life, is a cellular automaton devised%0A * by the British mathematician John Horton Conway in 1970.%22%0A * %3Cp%3E%0A * Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its%0A * eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia%0A * article):%0A * %3Cp%3E%0A * Any live cell with fewer than two live neighbors dies, as if caused by under-population.%0A * Any live cell with two or three live neighbors lives on to the next generation.%0A * Any live cell with more than three live neighbors dies, as if by over-population..%0A * Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.%0A * Write a function to compute the next state (after one update) of the board given its current state.%0A * %3Cp%3E%0A * Follow up:%0A * Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some%0A * cells first and then use their updated values to update other cells.%0A * In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause%0A * problems when the active area encroaches the border of the array. How would you address these problems?%0A * %3Cp%3E%0A * Tags: Array%0A * Similar Problems: (M) Set Matrix Zeroes%0A */%0Apublic class GameOfLife %7B%0A%0A    /**%0A     * Bit-manipulation.%0A     * Use 2 bit for each cell to represent both current and next states.%0A     * 00, 01, 10, 11.%0A     * Then scan the matrix again to generate result.%0A     */%0A    public void gameOfLife(int%5B%5D%5B%5D board) %7B%0A        int m = board.length;%0A        int n = board%5B0%5D.length;%0A        for (int i = 0; i %3C m; i++) %7B%0A            for (int j = 0; j %3C n; j++) %7B%0A                int lives = -board%5Bi%5D%5Bj%5D; // If the current cell is live, it will be deducted from result%0A                for (int k = Math.max(i - 1, 0); k %3C Math.min(i + 2, m); k++) %7B%0A                    for (int l = Math.max(j - 1, 0); l %3C Math.min(j + 2, n); l++) %7B%0A                        lives += board%5Bk%5D%5Bl%5D & 1;%0A                    %7D%0A                %7D%0A                if ((lives %7C board%5Bi%5D%5Bj%5D) == 3) %7B // lives = 2 or 3, board%5Bi%5D%5Bj%5D = 1, or lives = 3, board%5Bi%5D%5Bj%5D = 0%0A                    board%5Bi%5D%5Bj%5D %7C= 2;%0A                %7D%0A            %7D%0A        %7D%0A        for (int i = 0; i %3C m; i++) %7B%0A            for (int j = 0; j %3C n; j++) %7B%0A                board%5Bi%5D%5Bj%5D %3E%3E= 1;%0A            %7D%0A        %7D%0A    %7D%0A%7D

add Game of Life