Problem
I created a program in Java that showcases Conway’s Game of Life, in 4 days. Created the algorithm from scratch. However I got a scathing review and left me scratching my head. This was for a job application, the guy didn’t say anything more, other than: “Kevin – we are going to pass. He has good documentation and coding hygiene, but his algorithms and design choices are questionable. It really does not make sense based on his background.” I submitted it to Codacity and got a B based on style and such, I mean given the short time I had, I chose having more features, than elegant code. Could someone help me to understand what I did that was so bad.
You can see the whole bit here
/* (non-Javadoc)
* @see Cells#step()
* Calculate next generation of cells
* Algorithm:
* - get both cells from the two buffers, both have the exact same location
* - count live neighbors, regardless of state, somewhat optimal depending on state
* - apply game rules: liveCell (2 or 3 liveNeighbors) = live, deadCell (3 liveNeighbors) = live
* - clear cell buffer, by killing all cells
* - swap buffers, readying for next step
*/
@Override
public void step() {
for (int i = 0; i < this.cells.size(); ++i) {
Cell cp = this.cells.get(i);
Cell bcp = this.cellsBuffer.get(i);
// count neighbor states, location is cached as adjacent cells contain references
int liveNeighborsCount = getNeighborCount(cp);
if (cp.isAlive()) {
if (liveNeighborsCount == 2 || liveNeighborsCount == 3) {
bcp.revive();
}
} else if (cp.isDead()) {
if (liveNeighborsCount == 3) {
bcp.revive();
}
}
}
// clear grid = kill all cells
// we don't kill them before, since it would cause neighbor miscalculations
for (Cell cp : this.cells) {
cp.kill();
}
// swap arrays for next iteration
ArrayList<Cell> tmp = this.cellsBuffer;
this.cellsBuffer = this.cells;
this.cells = tmp;
}
/**
* Recalculate engine cell grid
* use double buffer, so as to avoid unnecessary memory allocation and deallocation
* Algorithm:
* - save current alive cells into array
* - resize cell buffer and add cells set to dead initially
* - for each cell save neighbor locations
* - clone array, both contain only dead cells
* - copy saved alive cells into cell array
* - save current dimensions
* - restored saved cells into resized array
*/
private void recalculate() {
// save alive cells
ArrayList<Cell> alive = new ArrayList<>(0);
for (Cell nc : this.cells) {
if (nc.isAlive()) {
alive.add(nc);
}
}
int c = this.dimensions.width;
int r = this.dimensions.height;
this.cellsBuffer = new ArrayList<>(c * r);
// initialize array, identity is set to dead, so first step is recalculated
Cell cp = null;
Point p = null;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
p = new Point(i, j);
cp = new Cell(p);
this.cellsBuffer.add(cp);
}
}
// calculate and set neighbors
if (this.teleport) {
calculateNeighborsStiched();
} else {
calculateNeighbors();
}
//clone cell array
this.cells = new ArrayList<>(c * r);
for (Cell bcp : this.cellsBuffer) {
this.cells.add(new Cell(bcp));
}
this.columns = c;
this.rows = r;
// copy old to current
for (Cell ocp : alive) {
Point op = ocp.getLocation();
cp = this.cells.get((op.x * this.columns) + op.y);
cp.revive();
}
}
//cells are confined to the grid without teleporting capability
private void calculateNeighbors() {
int c = this.dimensions.width;
int r = this.dimensions.height;
int col = 0;
int row = 0;
for (Cell ncp : this.cellsBuffer) {
Point np = ncp.getLocation();
int i = np.x;
int j = np.y;
ArrayList<Point> neighbors = new ArrayList<>(8);
// go around the cell...
// top
row = i - 1;
col = j;
if (row >= 0) {
addNeighbor(ncp, row, col, c, neighbors);
}
// bottom
row = i + 1;
col = j;
if (row < r) {
addNeighbor(ncp, row, col, c, neighbors);
}
// top left
row = i - 1;
col = j - 1;
if (col >= 0 && row >= 0) {
addNeighbor(ncp, row, col, c, neighbors);
}
// top right
row = i - 1;
col = j + 1;
if (col < c && row >= 0) {
addNeighbor(ncp, row, col, c, neighbors);
}
// bottom left
row = i + 1;
col = j - 1;
if (col >= 0 && row < r) {
addNeighbor(ncp, row, col, c, neighbors);
}
// bottom right
row = i + 1;
col = j + 1;
if (col < c && row < r) {
addNeighbor(ncp, row, col, c, neighbors);
}
// left
row = i;
col = j - 1;
if (col >= 0) {
addNeighbor(ncp, row, col, c, neighbors);
}
// right
row = i;
col = j + 1;
if (col < c) {
addNeighbor(ncp, row, col, c, neighbors);
}
ncp.setNeighbors(neighbors);
}
}
Solution
What I like:
- There is documentation, for nearly everything, which is great! Just for my curiosity’s sake, what’s the point of writing
(non-Javadoc)at the beginning of your commentaries? Is it for human or for automatized tools? First time I see it, I’m genuinely curious. - While looking quickly at your Github repo, I see you have tests, HOWTO, a README etc, I can tell you took a bit of extra time helping people wanting to look at your code and this is marvelous! Really I mean it.
What I liked less:
- Naming. I really don’t like reading one letter variables.
iorjis acceptable in a loop because people know what they stand for, I feelrandcare not, in a loop or outside. - The naming of
CellandCellsfor the class and the interface, that might be just personal taste but I find it confusing. One convention I learned a while ago is to put anIbefore the name if it’s an interface, likeICellfor interface andCellfor the class. I don’t like this convention either but I find it less confusing. As always, naming is a hard thing. ArrayList<Cell> alive = new ArrayList<>(0);in the functionrecalculate(), maybe I’m missing the point but you initialize a 0 sized ArrayList, and then you try to put stuff in it, not a big deal but why not giving it no argument or an argument > 0 to initialize it with some room at first? That might be just a personal thing.-
Very long methods like
calculateNeighbors(), which can be refactored easily. This is your code//cells are confined to the grid without teleporting capability private void calculateNeighbors() { int c = this.dimensions.width; int r = this.dimensions.height; int col = 0; int row = 0; for (Cell ncp : this.cellsBuffer) { Point np = ncp.getLocation(); int i = np.x; int j = np.y; ArrayList<Point> neighbors = new ArrayList<>(8); // go around the cell... // top row = i - 1; col = j; if (row >= 0) { addNeighbor(ncp, row, col, c, neighbors); } // bottom row = i + 1; col = j; if (row < r) { addNeighbor(ncp, row, col, c, neighbors); } // top left row = i - 1; col = j - 1; if (col >= 0 && row >= 0) { addNeighbor(ncp, row, col, c, neighbors); } // top right row = i - 1; col = j + 1; if (col < c && row >= 0) { addNeighbor(ncp, row, col, c, neighbors); } // bottom left row = i + 1; col = j - 1; if (col >= 0 && row < r) { addNeighbor(ncp, row, col, c, neighbors); } // bottom right row = i + 1; col = j + 1; if (col < c && row < r) { addNeighbor(ncp, row, col, c, neighbors); } // left row = i; col = j - 1; if (col >= 0) { addNeighbor(ncp, row, col, c, neighbors); } // right row = i; col = j + 1; if (col < c) { addNeighbor(ncp, row, col, c, neighbors); } ncp.setNeighbors(neighbors); } }
That you could have written like:
//cells are confined to the grid without teleporting capability
private void calculateNeighbors() {
int c = this.dimensions.width; //name it height or gridHeight?
int r = this.dimensions.height; /name it width or gridWidth?
int col = 0;
int row = 0;
for (Cell ncp : this.cellsBuffer) {
Point np = ncp.getLocation();
ArrayList<Point> neighbors = new ArrayList<>(8);
// go around the cell...
for(int col=np.x-1; col<=np.x+1; col++)
{
for(int row=np.y-1; row<=np.y+1; row++)
{
if(row!=np.y and col!=np.x and isInsideGrid(col,row))
addNeighbor(ncp, row, col, c, neighbors);
}
}
ncp.setNeighbors(neighbors);
}
}
/*
* function to test if a position is inside the grid
* Documentation...
*/
private bool isInsideGrid(int x, int y)
{
return (x>=0 and x<this.dimension.width and y>=0 and y<this.dimension.height);
}
Which in my opinion is shorter, clearer and less error prone.
Of course you had little time for this project, and quite frankly this is really impressive. Good luck for your future interviews!
Thanks for sharing your code.
I generally agree with the answer of @JulienRousé. I’d like to add some points:
Comments
I disagree that so much comments are something good.
Comments should explain why the code is like it is. You comment almost all only repeat what the code should express itself by proper naming and smaller methods.
E.g.: you have comments that “split” bigger methods into logical sections. This logical sections should live in their own methods names after the comments you used to separate them:
private void recalculate() {
ArrayList<Cell> alive = saveAliveCells();
initializeArrayWithDeadCells();
calculateAndSetNeighbors();
cloneCellArray();
copyOldToCurrent(alive);
}
–
private ArrayList<Cell> saveAliveCells() {
// save alive cells
ArrayList<Cell> alive = new ArrayList<>(0);
for (Cell nc : this.cells) {
if (nc.isAlive()) {
alive.add(nc);
}
}
return alife;
}
–
private void initializeArrayWithDeadCells() {
int c = this.dimensions.width;
int r = this.dimensions.height;
this.cellsBuffer = new ArrayList<>(c * r);
// initialize array, identity is set to dead, so first step is recalculated
Cell cp = null;
Point p = null;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
p = new Point(i, j);
cp = new Cell(p);
this.cellsBuffer.add(cp);
}
}
}
–
private void calculateAndSetNeighbors() {
// calculate and set neighbors
if (this.teleport) {
calculateNeighborsStiched();
} else {
calculateNeighbors();
}
}
–
private void cloneCellArray() {
//clone cell array
this.cells = new ArrayList<>(c * r);
for (Cell bcp : this.cellsBuffer) {
this.cells.add(new Cell(bcp));
}
}
–
private void copyOldToCurrent(ArrayList<Cell> alive) {
this.columns = c;
this.rows = r;
// copy old to current
for (Cell ocp : alive) {
Point op = ocp.getLocation();
cp = this.cells.get((op.x * this.columns) + op.y);
cp.revive();
}
}
Now your recalculate() method “tells a story” and no extra comment is needed to understand what it does.
general approach
Your code is a procedural approach to the problem.
There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.
What I mean is:
what if a cell is not just an element in an array or a dump data object but knows its neighbors?
Why could this be important?
Because the fastest way to do something is not to do it.
How many of the cells do change from one iteration to another? Wouldn’t it be clever to recalculate only for those cells that might change because any of its neighbors changed and skip calculation for all the rest?
If Cells had knowledge about their neighbors and how to calculate the next state we could collect all the neighbors of changed cells and do calculation only for those few cells instead of all the cells of the complete field.
// Game class, main loop
List<Cell> allCells = initializeGameFieldAndSetCellNeigbours();
Set<Cell> affectedCells = new HashSet<>(allCells); // removes duplicates
do {
Set<Cell> affectedCellsNextGen = new HashSet<>();
for(Cell currentCell : affectedCells)
currentCell.changeState(affectedCellsNextGen);
displayGame();
affectedCells.clear();
affectedCells.addAll(affectedCellsNextGen);
} while(isGameRunning());
–
class Cell {
Map<Cell,Boolean> currentGenerationNeighborStates = new HashMap<>();
private boolean state;
public void addNeighbor(Cell neighbor){
currentGenerationNeighborStates.put(neighbor, neighbor.getState());
}
public boolean getState(){
return state;
}
private saveOldState(Cell neighbor){
currentGenerationNeighborStates.put(neighbor, neighbor.getState());
}
public calculate nextState(Set<Cell> affectedCellsNextGen){
pushOldStateToNeigbours();
if(calculateNewState()) {
reportNeighborsAsPossibleChangingInNexGeneration(affectedCellsNextGen)
}
}
private void reportNeighborsAsPossibleChangingInNexGeneration(Set<Cell> affectedCellsNextGen){
affectedCellsNextGen.addAll(neighbors);
}
private void pushPoldStateToNeigbours(){
for(Cell neighbor : currentGenerationNeighborStates.keySet())
neighbor.saveOldState(this);
}
private boolean calculateNewState(){
boolean oldState = state;
int alifeNeigborsCount = countAlifeNeigbours();
state = state
? isAlifeCellSurviving(alifeNeigborsCount)
: isDeadCellBorn(alifeNeigborsCount);
return oldState ^ state;
}
private boolean isAlifeCellSurviving(int alifeNeigborsCount){
return 3 == alifeNeigborsCount || 2 == alifeNeigborsCount;
}
private boolean isDeadCellBorn(int alifeNeigborsCount){
return 3 == alifeNeigborsCount;
}
private int countAlifeNeigbours();
int alifeNeighborsCount =
currentGenerationNeighborStates
.stream()
.map(mapEntry-> mapEntry.value())
.filter(isAlife->isAlife)
.count();
return alifeNeighborsCount;
}
}
This is the complete algorithm.
Please notice that there is no reference to the actual geometry of the game field. It is completely moved to the initialization phase (not shown) and during runtime no corner check or edge check is needed. I don’t even need to create a 2-dimensional array to find neighbors (Of cause this will help for display…). I could do this with a simple logic on a list of cells (but not on a Set since it does not keep order of elements).