Game of life

It’s a game invented by the British mathematician John Horton Conway and the game goes like this.

Most people know this game because you might be asked during any technical interview to design Game of Life on a whiteboard. But for me, when I first learn how to program I was asked to code Game of Life and it was actually kinda fun. Especially, if you do it in TDD.

Why this post then?

I know there’s a lot of posts out there solving Game of Life in any possible known computer languages, but I feel like all of them are too hard to understand or use advanced library like numpy to solve the problem which makes it really hard to understand for me. Also, if I would like to understand how to solve the problem and if I can’t explain this simply that means I don’t understand at all.

Algorithm

The simplest algorithm goes like this.

1. Count all the live cells around 8x8 matrix of a cell.
2. Determine if the next state, the cell lives or dies based on the rules.

So, if you can count all the live cells around a cell, you’re pretty much there.

Naive approach

The naive approach is really simple and stupid. There’s a method to count all the cells and put that to a temp board so it can be used to determined the next cycle of the game.

The complexity would be O(m * n) but the space would be O(m * n) as well

First refactor

The first refactoring would be to just loop through the surrounding cell with the check for boundaries.

It’s a bit better don’t you think?

Second refactor

Now the first two approaches, we have to have a temp board to calculate the next state. Let’s see if we can do better than that by manipulating the board in-place instead of having a temp board.

Someone on the leetcode discussion suggested bit manipulation to store the state of the cell which I think it’s a brilliant idea. However, I feel like there’s not much explanation so I’m going to try to explain it here.

The problem with the second approach is that we have to have a temp board to store the number of surrounding cells so that we can flip it after the whole board has been counted. The problem with this approach is space complexity if the board is really large we need to double the size of memory to store the state of the board.

For example:

We have this board

If we look at the coordinate (1,1) the cell is live and only has 1 surrounding living cell which according to the rule the cell dies because of under-population in the next state. So we can represent that cell as 0 1. The right-most bit represent the first state and the left-most bit represent the next state. So in the case, the cell has value 1 which after we shift it to the right with cell[i][j] >>= 1. It’s going to be 0 which means the cell dies in the next state.

So to refactor the code we will get something like this.

To sum up we will get the code which looks something like this

You might notice about this line.

This is because we want to just loop through the board once and if we change the number of the current cell to be ready for the next state, the later cell will get the wrong count. To & 1 means we just want to get the current state of the cell whether it’s dead or alive regardless of the total count of the surrounding cells.

Nov 11th, 2016