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

• Implement the Conway Game of Life.

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-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

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();
}``````

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