Tuesday, April 16, 2013

My attempt in solving Conway's game of life - a post mortem


Recently, I'd applied for a Senior Developer position in Thoughtworks. Like they usually do, I was asked to solve any one of the problems from this list
- Merchant's guide to Galaxy
- Conference track management
- Conway's Game of Life

I chose Conway's Game of Life. One of my friends had applied for Thoughtworks a few months ago and I remember discussing at length with him about the problem. To begin with, I had a fair idea of what to do. The problem looks fairly simple. You'll be given a cell pattern (comprising of live and dead cell). The cell pattern would grow/shrink based on the neighbouring cell's state. There are rules to govern that.

For instance, any live cell with more than 3 live neighbours will die due to over crowding.
Any live cell with less than 2 live neighbours will die of loneliness. Etc
Check out this wiki link for more details about the game. 

My approach
I wanted to decouple the way in which the rules are applied to the cells so that one rule need not know what the other one does and can be executed exclusively. I came up with this approach of listing down the rules in a properties file in this manner and load them at run time to a list.


1
2
3
#Add Rules this way
#Rule_Name = Rule_Implementation_Class
TestRule = com.java.tw.gol.rules.handlers.TestRuleHandler

Each cell in the universe will be subjected to the rules from the list all at once. 

I was asked to come down to their office for the pair programming round. Two other employees sat with me to analyze the code. I was asked to explain my design and I was asked questions on the rationale/logic behind my design. They gave an extension to the problem and my design handled it #likeABoss without much code change.

YET, I FAILED TO CLEAR THE PAIR PROGRAMMING ROUND. It lasted for about 1.5 hrs after which the HR told me this (verbatim)

They were impressed with your design and the way in which you have thought through the problem. But you must concentrate on finer nuances of OOPS.

Pain points in my design

They asked me why I'd added an attribute private String cellValue. I told them that I added it purely to represent a cell(x for a live cell and - for a dead cell).
The actual problem lies not in having an attribute for display purpose but in the way I'd handled the attribute.

Now, imagine we create a cell using this constructor.


1
2
3
4
5
6
7
public Cell(int x, int y, boolean cellState, String value)
{
 this.xPos = x;
 this.yPos = y;
 this.isAlive = cellState;
 this.cellValue = value;
}


Cell c = new Cell(0,0,true,"-"); 

See what I'd done there? We are setting the isAlive attribute to true and representing the cell using '-'. This kind of breaks the whole thing right?


public Cell(int x, int y, boolean cellState)
{
  this.xPos = x;
  this.yPos = y;
  this.isAlive = cellState;
  //Fix
  if(cellState)
   this.cellValue = "X";
  else
   this.cellValue = "-";
} 

My GolUtils class had methods like getNeighbouringLiveCellCount and checkIfCellIsAlive which do the chunk of the business logic. Placing them in Util class was really bad in their perspective. 

CellPatter.java has getters and setters which are exposed publicly. As in, anybody can change the cell state. By exposing the setters we are running into the danger of raw data being tampered. 

Nice to have feature: The user should be able to run the game for n no of times. 

Over all, its was 90 mins well spent. I have learnt to look things the way, which I would have not even bothered earlier. 

Game of Life - Github URL

Do let me know if you see any basic flaws/any improvements that can be done. Please feel free to fork it on Github.

Happy Coding :)
~ cheers.!

4 comments:

  1. [offtopic] I always wondered about your Git project structure. For example, in this repo (https://github.com/karthikch53/GameOfLife), instead of having projects files at the root folder, you have a project folder at root level and then inside of that folder you place all your files. Any specific reason for this? Because the general practice I have seen was to have project files at root level.

    ReplyDelete
  2. the reason is, i create projects first in github and then add projects from my local to remote. thats why you'll see two folders with same name. :)
    will make a note to get it right the next time.
    ~ cheers.!

    ReplyDelete
  3. hey karthick,

    Thanks for the article. Can you also provide the input file? I am not able to generate the right output. I either get an invalid character exception or wrong output.

    Thanks

    ReplyDelete
  4. hi,
    there is no input file as such. if you run the program, it will prompt you to enter the file path.
    the file can have any one of these inputs. Current version accepts X,x or - separated by a space. You can modify the code to use any other character.

    Block pattern i/p
    X X
    X X
    Block Pattern o/p
    X X
    X X

    Boat pattern i/p
    X X -
    X - X
    - X -

    Boat pattern o/p
    X X -
    X - X
    - X -

    Blinker pattern i/p
    - X -
    - X -
    - X -

    Blinker pattern o/p
    - - -
    X X X
    - - -

    Toad pattern i/p
    - X X X
    X X X -

    Toad pattern o/p
    - - X -
    X - - X
    X - - X
    - X - -

    ReplyDelete