Java not in place but much faster solution


  • 0
    E

    Thanks to Ilmari Karonen in this post http://codereview.stackexchange.com/questions/42718/optimize-conways-game-of-life

    I tested it against multiple in place versions from discussion and this version only spends half of their time. The key idea is using a lookup table to map each specific environment to a result state. To calculate environment value, we use each bit in 9-bit integer to represent all neighbors and the point itself. For example, if we are calculating environment value for n4:

    n8  n5  n2
    n7  n4  n1
    n6  n3  n0
    

    In this case, the value is

    environment = n8 * 256 + n7 * 128 + n6 * 64 + n5 * 32 + n4 * 16 + n3 * 8 + n2 * 4 + n1 * 2 + n0 * 1
    

    And for each point, we only need to read three times instead of nine times from memory by a little trick in the code.

    public class Solution {
    public void gameOfLife(int[][] board) {
        // the table used to map environment to next round state
    	int[] lookupTable = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    			0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0,
    			0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1,
    			0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0,
    			0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0,
    			0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    			0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
    			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1,
    			1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0,
    			0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0,
    			0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    			0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    			1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
    			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    	int m = board.length, n = board[0].length;
    	if(n == 0) return;
    	int[][] buffer = new int[m][n];
    	for(int i = 0; i < m; i++){
              //  for each row, calculate its initial environment value
    		int environment = (i - 1 >= 0 && board[i - 1][0] == 1? 4 : 0) + (board[i][0] == 1 ? 2 : 0) + (i + 1 < m && board[i + 1][0] == 1 ? 1 : 0);
    		// for each point in the row, calculate their environment value by counting right 3 columns 
    		for(int j = 0; j < n; j++){
    		    // we can reuse last environment value by mod 64 first than times 8
                // after reusing old environment value, we need to read right 3 columns to get new environment value
                environment = (environment % 64) * 8 + (i - 1 >= 0 && j + 1 < n && board[i - 1][j + 1] == 1 ? 4 : 0) 
                    		+ (j + 1 < n && board[i][j + 1] == 1 ? 2 : 0) 
                    				+ (i + 1 < m && j + 1 < n && board[i + 1][j + 1] == 1 ? 1 : 0);
                // get corresponding state
                buffer[i][j] = lookupTable[environment];
    		}
    	}
    
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = buffer[i][j];
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.