Game of Life — the Infinite world!
Thats the first thing which came to my mind when I heard of the game “Game of Life”. It was our first day of the bootcamp at GoJek and we were told to make the Game Of Life (GOF)in Java in Ruby.
Follow this wikipedia link to know the rules of GOF. Pretty simple rules! But its not that easy to make as it sounds. I will tell you how I came up with my solution.
The first thing that comes to our mind is — breaking the problem into parts.
Classes I made
- Board
- Cell
- Display
- InputReader
Board Class maintains the state of the board and is made of Cell objects.
Cell is an independent entity with coordinate and its state (ALIVE/DEAD).
Display class is the helper class which displays anything we want.
InputReader is the helper class to help us take the input and validate it.
There can be many more classes but lets go with this now.
The Major thing which confused me was the Infinite Grid.
Infinite Grid
Now if the Grid was of limited size and the input for this can be taken by the user, the best solution is the 2-d array. If our game goes out of the boundary, we make those cells DEAD as our Grid is limited. We could use 2-d integer array (or anything) in the board class and initialize them with 0 or 1.
But with Infinite Grid we cannot use this 2-d array indexing.
Another try to this is to assume that the display screen is curved like a sphere. So if our game goes out of bounds, we transport it to the other end. But this is just a hack and not a solution.
In my first approach to the solution, I came up with a List of cells in the Board class.
- Initialize this list with user defined grid dimensions.
- Add the dead neighbors cells of active cells in this list as some of them can grow.
- On every member cell in this list, advance it to the next state. (Next state is derived from the rules. Also make sure you have done a deep copy of the initial board cells while checking for these rules. This is one of the most common mistakes.)
- Replace the old cells with these new cells in Board Class.
Analysis of List of Cells
- Initialize — O(N)
- Adding the dead neighbours — For every active cell I had to first check for its neighbour(if it already exists) and then add it. Here checking is O(N) as its list. Hence its O(N*N).
- Similarly the advancement of cells to next state is also O(N*N). As there were functions like
checkCellExist(x,y)
getNeighboursCount(x,y)
As these cells were all in a list, there was no way to check if a cell exists at particular coordinate. We had to traverse the list and then find out. Thus this was working for infinite grid as we can have no problem with negative indices. And it will work as long as we will have space in the memory.
Solution Accepted like this!
But this is not a good solution! Accepted solution but not a good code. We could use hash map instead of lists and improve the performance of our code.
HashMap<Pair, Cell> cells = new HashMap<>();
We use a hash with key as the pair(int,int) and the value will be our cell object.
So functions like checkCellExist(x,y) will be amortized O(1) because of hashing.
This process takes O(N) time per iteration. (N is the number of elements in the grid to print).
Will add any more better solution if I get. You can contact the author at me@abhinavrai.com.