Return to Question

birth(): iterates over a HashMap containing a key-value pair of all alive cells along with its neighbors. If the key-value pair follows the game of life’s rules above, the key (an integer value that represents the location of a cell) is then pushed onto a stack that contains the next generation of alive cells. After each iteration, the value of the grid is reset to 0, and the key-value pair is removed from the HashMap.

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive). All of the neighbors and alive cells are then put into a HashMap so that birth() can run properly

printBoard() (should be named boardToString): uses a stringbuilder to format the grid into a string.

Note: most comments have been taken out because they don't add much to the readability of the code

CellularAutomaton.java

GameOfLife.java

package first; 
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class GameOfLife extends CellularAutomaton {

    int board[][];
    int dim;
    Stack<Integer> stackCells;
    HashMap<Integer, Integer> hmapCells;

    public gameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        stackCells = s;
        hmapCells = new HashMap<>();
    }

    public boolean rules(int num){
        return num == 3 || num == 12 || num == 13;
    }

    private void birth() {
        Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer,Integer> pair = it.next();
            int key = pair.getKey();

            if(rules(pair.getValue())){
              stackCells.add(key);
            }

            board[key/dim][key%dim] = 0;
            it.remove();
        }
    }

    private void insertAlive() {
        while(!stackCells.isEmpty()) {
            int cell = stackCells.pop();

            int x = cell / dim;
            int y = cell % dim;
            int startX = (x <= 0) ? 0 : x - 1;
            int startY = (y <= 0) ? 0 : y - 1;
            int endX = (x >= dim - 1) ? x + 1 : x + 2;
            int endY = (y >= dim - 1) ? y + 1 : y + 2;
    
            for(int i = startX; i < endX; ++i) {
                for(int j = startY; j < endY; ++j) {
                    hmapCells.put(i * dim + j, ++board[i][j]);
                }
            }
            hmapCells.put(cell, board[x][y] += 9);
        }
    }

    private String printBoard() {
        StringBuilder s = new StringBuilder();
        
        for(int elements[] : board) {
            for(int element : elements) {
                if(element >= 10){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }
        
        return s.toString();
    }

    public String lifeCycle() {
        birth();
        insertAlive();
        return printBoard();
    }
}

Simulation.java

birth(): iterates over a HashMap containing a key-value pair of all alive cells along with its neighbors. If the key-value pair follows the game of life’s rules above, the key (an integer value that represents the location of a cell) is then pushed onto a stack that contains the next generation of alive cells. After each iteration, the value of the grid is reset to 0, and the key-value pair is removed from the HashMap.

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive). All of the neighbors and alive cells are then put into a HashMap so that birth() can run properly.

printBoard() (should be named boardToString()): uses a StringBuilder to format the grid into a string.

Note: Most comments have been taken out because they don't add much to the readability of the code.

CellularAutomaton.java

GameOfLife.java

package first; 
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class GameOfLife extends CellularAutomaton {

    int board[][];
    int dim;
    Stack<Integer> stackCells;
    HashMap<Integer, Integer> hmapCells;

    public gameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        stackCells = s;
        hmapCells = new HashMap<>();
    }

    public boolean rules(int num){
        return num == 3 || num == 12 || num == 13;
    }

    private void birth() {
        Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer,Integer> pair = it.next();
            int key = pair.getKey();

            if(rules(pair.getValue())){
              stackCells.add(key);
            }

            board[key/dim][key%dim] = 0;
            it.remove();
        }
    }

    private void insertAlive() {
        while(!stackCells.isEmpty()) {
            int cell = stackCells.pop();

            int x = cell / dim;
            int y = cell % dim;
            int startX = (x <= 0) ? 0 : x - 1;
            int startY = (y <= 0) ? 0 : y - 1;
            int endX = (x >= dim - 1) ? x + 1 : x + 2;
            int endY = (y >= dim - 1) ? y + 1 : y + 2;
    
            for(int i = startX; i < endX; ++i) {
                for(int j = startY; j < endY; ++j) {
                    hmapCells.put(i * dim + j, ++board[i][j]);
                }
            }
            hmapCells.put(cell, board[x][y] += 9);
        }
    }

    private String printBoard() {
        StringBuilder s = new StringBuilder();
        
        for(int elements[] : board) {
            for(int element : elements) {
                if(element >= 10){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }
        
        return s.toString();
    }

    public String lifeCycle() {
        birth();
        insertAlive();
        return printBoard();
    }
}

Simulation.java

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive).

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive). All of the neighbors and alive cells are then put into a HashMap so that birth() can run properly

Note: most comments have been taken out because they don't add much to the readability of the code

package first; 
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class GameOfLife extends CellularAutomaton {

    int board[][];
    int dim;
    Stack<Integer> stackCells;
    HashMap<Integer, Integer> hmapCells;

    public gameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        stackCells = s;
        hmapCells = new HashMap<>();
    }

    public boolean rules(int num){
        return num == 3 || num == 12 || num == 13;
    }

    private void birth() {
        Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer,Integer> pair = it.next();
            int key = pair.getKey();

            if(rules(pair.getValue()))
            stackCells.add(key);

            board[key/dim][key%dim] = 0;
            it.remove();
        }
    }

    private void insertAlive() {
        while(!stackCells.isEmpty()) {
            int cell = stackCells.pop();

            int x = cell / dim;
            int y = cell % dim;
            int startX = (x <= 0) ? 0 : x - 1;
            int startY = (y <= 0) ? 0 : y - 1;
            int endX = (x >= dim - 1) ? x + 1 : x + 2;
            int endY = (y >= dim - 1) ? y + 1 : y + 2;
    
            for(int i = startX; i < endX; ++i) {
                for(int j = startY; j < endY; ++j) {
                    hmapCells.put(i * dim + j, ++board[i][j]);
                }
            }
            hmapCells.put(cell, board[x][y] += 9);
        }
    }

    private String printBoard() {
        StringBuilder s = new StringBuilder();
        
        for(int elements[] : board) {
            for(int element : elements) {
                if(element >= 10){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }
        
        return s.toString();
    }

    public String lifeCycle() {
        birth();
        insertAlive();
        return printBoard();
    }
}

EDIT:

In hopes of receiving more feedback, here is the theory behind my implementation:

For reference, here are the rules for Conway's game of life (taken from wikipedia):

1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
2. Any live cell with tow or three live neighbors live on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overpopulation
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Overview:

1. A different outlook on Conway's Game of Life
2. Unspoken rules
3. Explanation of important methods (and data structures used)

A different outlook on Conway's Game of Life

Let us first imagine the Game of Life as a n x n grid (we will also assume that this grid has coordinates such that the bottom left hand corner is denoted as (0,0) and the top right hand corner is denoted as (n,n) where n is a positive integer). This 2-Dimensional grid represents a group of n*n number of cells. Each grid block can be thought of as a cell, which not only stores a Boolean value (dead or alive) to describe the cell’s status, but also details its location via its coordinates. In addition, the current state of all cells determines which cells will die, continue to live, or be born in the next generation in accordance to the rules found above.

In a different perspective, however, Conway’s game of life is very similar to the game minesweeper. We can think of an alive cell as a mine, and its neighbors storing the number of mines that are closest to it. In this way, we are able to easily use the rules above to determine the future generation (particularly which cells will die, and which cells will be born).

What about the cells that are currently alive you might ask? Well, we can easily represent these as an integer greater than 10, where the one’s place indicates how many alive neighbors the currently alive cell has, and the ten’s places indicates that the cell is alive.

Unspoken rules

One observation that occurred to me is that the game of life is only concerned about alive cells. Only cells that are alive can die, cells that continue to live have to already be living, and cells can only be born if they have neighbors that are alive. As a result, checking the entire grid (time complexity: O(n^2)) to determine the future generation of cells would be a complete waste. It would be a lot faster if I stored all the currently alive cells and checked each alive cell along with their neighbors to determine the next generation (which is exactly what I did).

Explanation of important methods (and data structures used)

birth(): iterates over a HashMap containing a key-value pair of all alive cells along with its neighbors. If the key-value pair follows the game of life’s rules above, the key (an integer value that represents the location of a cell) is then pushed onto a stack that contains the next generation of alive cells. After each iteration, the value of the grid is reset to 0, and the key-value pair is removed from the HashMap.

insertAlive(): pops the stack and inserts the alive cell into the grid. Inserting a live cell follows the structure of minesweeper (neighbors of a live cell will be incremented by 1 and the alive cell will be incremented by 10 to denote that it is alive).

printBoard() (should be named boardToString): uses a stringbuilder to format the grid into a string.

Note: most comments have been taken out because they don't add much to the readability of the code

package first; 
import java.util.Stack;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class GameOfLife extends CellularAutomaton {

    int board[][];
    int dim;
    Stack<Integer> stackCells;
    HashMap<Integer, Integer> hmapCells;

    public gameOfLife(int d, Stack<Integer> s){
        board = new int[d][d];
        dim = d;
        stackCells = s;
        hmapCells = new HashMap<>();
    }

    public boolean rules(int num){
        return num == 3 || num == 12 || num == 13;
    }

    private void birth() {
        Iterator<Map.Entry<Integer,Integer>> it=hmapCells.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer,Integer> pair = it.next();
            int key = pair.getKey();

            if(rules(pair.getValue())){
              stackCells.add(key);
            }

            board[key/dim][key%dim] = 0;
            it.remove();
        }
    }

    private void insertAlive() {
        while(!stackCells.isEmpty()) {
            int cell = stackCells.pop();

            int x = cell / dim;
            int y = cell % dim;
            int startX = (x <= 0) ? 0 : x - 1;
            int startY = (y <= 0) ? 0 : y - 1;
            int endX = (x >= dim - 1) ? x + 1 : x + 2;
            int endY = (y >= dim - 1) ? y + 1 : y + 2;
    
            for(int i = startX; i < endX; ++i) {
                for(int j = startY; j < endY; ++j) {
                    hmapCells.put(i * dim + j, ++board[i][j]);
                }
            }
            hmapCells.put(cell, board[x][y] += 9);
        }
    }

    private String printBoard() {
        StringBuilder s = new StringBuilder();
        
        for(int elements[] : board) {
            for(int element : elements) {
                if(element >= 10){
                    s.append("* ");
                }
                else {
                    s.append("  ");
                }
            }
            s.append("\n");
        }
        
        return s.toString();
    }

    public String lifeCycle() {
        birth();
        insertAlive();
        return printBoard();
    }
}