6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ My $0.02 - 1) You could have tried to cut down long methods into separate private methods so that they read better. 2) Create multiple classes instead of one big class \$\endgroup\$ – user7 Jan 5 '18 at 18:51
  • 1
    \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 5 '18 at 19:20
  • \$\begingroup\$ Thanks @user7, Yes that's true, in the whole project there are more classes, so this code is specific to the 'engine' part of it. I disagree on making these particular methods split, for two reasons. 1) They work they do are very related and it can be plainly seen, dealing with walking around the neighbor cells. 2) Performance. However, yes I agree that any code can be improved. My question was given the context of doing all this work in 4 days, what was so bad as to get the kind of scathing review I got. Would you rate the code this bad in those circumstances? Please advise. \$\endgroup\$ – Kevin Guerra Jan 6 '18 at 1:01
5
\$\begingroup\$

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. i or j is acceptable in a loop because people know what they stand for, I feel r and c are not, in a loop or outside.
  • The naming of Cell and Cells for 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 an I before the name if it's an interface, like ICell for interface and Cell for 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 function recalculate(), 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!

\$\endgroup\$
  • \$\begingroup\$ Julien, I wanted to thank you for the thorough review. I agree with you on most points. However, the point about interfaces having a "I" prefix, has been debated and some prefer one and some the other. I prefer without because the other somewhat remind me of Hungarian notation. I'm from that era. Cells is a container for Cell. I see the error in the recalculate function. As for the refactoring, yes nice example code you posted. I like that much better. I was not comfortable with my code being that, but I had to choose to add more features. I was trying to impress. \$\endgroup\$ – Kevin Guerra Jan 8 '18 at 5:48
  • 1
    \$\begingroup\$ I understand for the 'I' for interface, I don't like it eithger but I find it less confusing. I guess it's a matter of taste. And it's good to try to impress,, but in my experience, recruiter like it better if you do a bit less that the objectives, but what you've done is really good, than doing everything and having things not pretty. Still I think you did pretty good for the time you had \$\endgroup\$ – Julien Rousé Jan 8 '18 at 7:53
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Timothy, thanks also for the thorough review. I agree about the comments, I also think that less is more, and code should tell a story. You examples are very nicely presented. I had very little time and opted to put more features and for performance. My gripe with the prospective employer scathing review was that he seemed to have overlooked the timing consideration and the amount of features I added way over what was requested. However, yes, I do see the point that the code needs improvement. \$\endgroup\$ – Kevin Guerra Jan 8 '18 at 5:58
  • \$\begingroup\$ Very nice review, I really like your refactoring of recalculate! And also I need to take some times to better understand what you did in your general approach section, seems very interesting. \$\endgroup\$ – Julien Rousé Jan 8 '18 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.