The Game of Life Kata

Rules of Evolution

The Game of Life is a cellular automaton, meaning that it's a grid of cells that will change state based on the other cells in their neighborhood with no interaction from the user. In the Game of Life, cells are either "alive" or "dead." Three rules govern whether a cell will live, die, or be revived in the next "generation:"

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial state of the grid is irrelevant to the operation of the automaton; it will simply follow these above rules. Some states are "still life," meaning that there is no evolution; all cells that are alive will persist to the next generation and no dead cells will be revived. One example of this is a 2x2 block. Other states will cause a persistent loop of animation, like three horizontal squares becoming three vertical squares, thus creating a spinner effect. Other states will multiple frames of animation until eventually resting with a few still lifes. For more detailed exploration of common patterns generated by the Game of Life, see the Wikipedia page.

A Surprisingly Small Amount of Code

While it took me a while to figure out my approach, I was very surprised that I ended up with a total of 15 lines of code. The nice thing about this kata is that the rules apply to individual cells, so once the code is in place to determine whether a cell will live, die, or be revived, putting the full grid together is a relatively simple affair.

I have three functions total: get-neighbors-of, evolve-cell, and evolve.

evolve-cell is the function that decides if one single cell will live, die, or be revived. It takes the grid (which is a set of only the live cells) and the cell in question as arguments. It uses get-neighbors-of to look at all the eight surrounding cells of the given cell. Those neighbors are then filtered against the grid of live cells to determine how many of the cell's neighbors are alive. If it has two live neighbors and the cell itself is already alive, the cell is returned. If it has three neighbors, the cell is returned without any extra conditions, as three neighbors will both keep a cell alive and revive a dead cell. In all other cases, the function returns nil to signify the cell has died.

evolve takes the grid, which, as stated above, is a set of only the live cells. However, we need the dead cells, too, in order to know if they need to be revived. To create the full grid, each live cell is mapped over using the get-neighbors-of function, and all of those neighbor cells are concatenated together and turned into a set to remove duplicates. Then, every cell in the full grid gets mapped over using evolve-cell to determine the next generation, then filters out any dead cells (nil values) and then converted back to a set and returned.

Cool Tricks

I used two features that stuck out to me in my implementation: using sets in filter, and mapcat.

When using filter, I typically think of it as only taking a predicate function followed by a collection. However, in Clojure, sets can also be used as predicates. This made it very easy to check if the neighbors of a cell were live neighbors by using the set of live neighbors as the predicate for filtering the neighbors. Any cell that is in the set of live cells and also in the set of neighbors will be returned as the result of filter.

When getting the neighbors of every live cell in order to construct the full grid, the eight neighbors are returned as a set, so the result is a bunch of subsets in the resulting list equal to the number of live cells. I could then wrap the whole thing in apply concat, but mapcat does it all for us in one go!

Everything is Tic-Tac-Toe

When developing this with TDD, it was very helpful to know which shapes would result from certain combinations of live cells. Therefore, I set about drawing a cell and it's neighbors to figure out things like "three horizontal squares will become three vertical squares" and "three squares shaped like an L will become a block of 2x2." Since there are eight neighbors for one cell, everything I was drawing was ... a tic-tac-toe board. I can't get away from it!