The Conway Game of Life - using Hashtable in JAVA !! Fast solution which only check alive cell and its neighbors !!!


  • 0
    J

    Implement the Conway Game of Life.

    More Information about game rules, please visit:
    http://www.bitstorm.org/gameoflife/


    Conway Game of Life Rules:

    For a space that is 'populated':

    • Each cell with one or no neighbors dies, as if by solitude.
    • Each cell with four or more neighbors dies, as if by overpopulation.
    • Each cell with two or three neighbors survives.

    For a space that is 'empty' or 'unpopulated'

    • Each cell with three neighbors becomes populated.

    Solution Approach:

    Solution-1:

    O(n) - By iterating over all the grid cells and for each one counting the neighbors.

    Solution Link: https://leetcode.com/discuss/64053/my-java-solution-for-game-of-life

    Solution-2:
    O(m) - By iterating over all the alive cell and its neighbors.

    package interview.java;
    import java.util.*;
    
    public class GameOfLife {
    
    	byte [][]cell =  { 
    		   //    0 1 2 3 4 5 6 7 8
    			{0,0,0,0,0,0,0,0,0}, // 0
    			{0,0,0,0,0,0,0,0,0}, // 1
    			{0,0,0,0,1,0,0,0,0}, // 2
    			{0,0,0,0,1,0,0,0,0}, // 3
    			{0,0,0,0,1,0,0,0,0}, // 4
    			{0,0,0,0,0,0,0,0,0} , // 5
    			{0,0,0,0,0,0,0,0,0}  // 6
    	};
    	
    	public GameOfLife(byte cellArray[][]){
    	     cell= cellArray;     
    	}
    
        public GameOfLife(){ }
    
    // Create a hash map, which contain Alive cell and its neighbors 
    Hashtable<String, CELL> ht = new Hashtable<String, CELL>();
    
        public  void playGOL() {
    	if(cell==null) 
    	{
    		System.out.println("Error: zero cell exist !!!"); 
    		return; 
    	}
    	
    	// 1. Check for alive cell.
    	// 2. Add alive cell and its neighbors in Hashtable
    	initializeHashTable();
    	
    	// 1. Print Game Cells 
    	// 2. Execute game rule on cells
    	// 3. Assign updated cell value in Game cellay.
    	
    	do{
    		printGOL();
    		nextStep();
    		if(setCellValues() == 0) // if setCellValues() return zero means, All cell dead by now. Game is Over.
    			break;
    	}while(true);
    }
    void initializeHashTable(){
    	// Put elements to the map
    	for(int i=0; i<cell.length; i++){
    		for(int j=0; j<cell[i].length; j++){
    			if(cell[i][j] == 1)  {
    				ht.put(getKey(i,j), new CELL (i, j, (byte) 1));
    				insertNeighbours(i,j);
    			}
    		}
    	}
    }
    
    void nextStep(){
           Enumeration<String> htElements = ht.keys();		    
    
    	while(htElements.hasMoreElements()) {
    		final String key = (String) htElements.nextElement();   
    		final CELL c = (CELL)ht.get(key);	         
    		
    		// count cell neighbors 
    		final int count = countCellNeghbours (c.r, c.c);
    
    		/* check for Game Of Life rules
    		For a space that is 'populated':
    		- Each cell with one or no neighbors dies, as if by solitude.
    		- Each cell with four or more neighbors dies, as if by overpopulation.
    		- Each cell with two or three neighbors survives.
    		
    		For a space that is 'empty' or 'unpopulated':
    		- Each cell with three neighbors becomes populated.
    		 */
    		if(c.cell == 1){
    			switch(count){
    			case 2:
    			case 3:
    				// Do nothing, cell is safe.
    				break;
    			case 0:
    			case 1:
    			default:
    				//kill cell
    				c.cell = 0;
    				break;				
    			}
    		} else{
    			if(count == 3){
    				//activate cell
    				c.cell = 1;
    				insertNeighbours(c.r, c.c);
    			} else if(count==0)
    				//Remove entry from Hashtable, no more needed.
    				ht.remove((String)key);
    		}
    	}
    }
    
    int setCellValues(){
    	Enumeration<String> htElements = ht.keys();
    	int count = 0; // count value to check if we have all dead cell.
    	while(htElements.hasMoreElements()) { // Finally initialize with updated cell values.
    		final String key = (String) htElements.nextElement();
    		final CELL c = (CELL)ht.get(key);
    		cell[c.r][c.c] = c.cell;
    		count += c.cell;
    	}
    	return count;
    }
    
    void printGOL(){
    	System.out.println();
    	// Display elements
    	for(int i=0; i<cell.length; i++){
    		for(int j=0; j<cell[i].length; j++){
    			if(cell[i][j] ==0)
    				System.out.print("0"); // 0 Indicate dead cell.
    			else
    				System.out.print("X"); // X indicate Alive cell
    		}
    		System.out.println();
    	}
    }
    
    public static String getKey(final int idx, final int jdx) {
    	String key;
    
    	if(idx<10 && jdx<10){
    		key = "0"+ idx + "0" + jdx;	        
    	}else if(idx<10){
    		key = "0"+ idx  + jdx;	        
    	}else if(jdx<10){
    		key = idx  + "0" + jdx;	        
    	}else{
    		key = Integer.toString(idx)  + Integer.toString(jdx);	        
    	}
    	//	    System.out.print( " key: " +  key);
    	return key;
    }
    
    void insertNeighbours(final int i, int j){
    	if(ht.get(getKey(i,j-1)) == null) // do not insert if cell already exist in Hashtable 
    		ht.put(getKey(i,j-1), new CELL (i, j-1, (byte) cell[i][j-1]));
    
    	if(ht.get(getKey(i,j+1) )== null) // do not insert if cell already exist in Hashtable 
    		ht.put(getKey(i,j+1), new CELL (i, j+1, (byte) cell[i][j+1]));
    
    	j--;
    
    	for(int n=0; n<3; n++){
    		if(ht.get(getKey(i-1,j) )== null) // do not insert if cell already exist in Hashtable 
    			ht.put(getKey(i-1,j), new CELL (i-1, j, (byte) cell[i-1][j]));
    		if(ht.get(getKey(i+1,j) )== null) // do not insert if cell already exist in Hashtable 
    			ht.put(getKey(i+1,j), new CELL (i+1, j, (byte) cell[i+1][j]));
    		j++;
    	}
    }
    
    byte countCellNeghbours( final int i,final int j){
    	if(i<1 || j<1 || (i >=cell.length-1) ||  (j>=cell[0].length-1) ) // cellay Index out of bound check
    		return 0;
    
    	return (byte) (cell[i][j-1] + cell[i][j+1]  +  
    			cell[i-1][j-1] + cell[i-1][j]  + cell[i-1][j+1] + 
    			cell[i+1][j-1] + cell[i+1][j]  + cell[i+1][j+1]) ; 	
      }	
    }
    

    Execution:

        import java.util.Enumeration;
        import java.util.Hashtable;
    
        public class InterviewMain {
    	public static void main(String[] args) {
            GameOfLife gol = new GameOfLife();
           gol.playGOL();
        }

Log in to reply
 

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