Conway’s Game of Life is a popular coding exercise, often used as a way to explore a new language, or a new facet of a language. I’ll give a brief history (though it’s a fun topic, and I’ve provided links at the bottom if you’d like to learn more).
|Fig 1. John Conway. by Thane Plambeck|
The Game stems from the writings of physicist (and polymath) John von Neumann in the 1940s. We know it as it was refined by mathematician John Conway, in the late 1960s. It was intended as a model of single-celled population growth and decline, played out on a two-dimensional grid.
- Each cell has eight neighbors.
- The number of neighbors each cell has determines its life or death into the next turn.
- If the cell has: fewer than two neighbors, it will die of loneliness.
- - two or three neighbors, it will live on.
- - four or more, it will die of overcrowding.
- If an empty space has exactly three neighbors, it will become a living cell.
Under these rules, it’s possible to create structures that move, grow, self-replicate, and sustain indefinitely. This little guy is one of the first "discovered" self-replicating structures, called a Glider.
|Fig 2. A small and rather adorable glider. Wikipedia|
You can create massively complex and interactive groups with these rules, including (but not limited to) a Turing-complete programming language. After creating your version in Ruby, you’ll be able to simulate these yourself!
Life, Meet Ruby
This is such a fun exercise because it can be created in a wide variety of ways. Ruby is a very good example of an OOPL, so I’ll cover two options: Cells as Objects, and Board as Object.
Cells as Objects
In an object-oriented language, it’s natural to think of each component as its own class. In pseudocode, you could describe the Cell class like this:
class Cell @position = [x, y] def self.count_neighbors Cell.all.each |cell.position| if cell.position is next to any other cell.position create_cell / destroy_cell
Each cell knows where it is in your grid, and how to check how many other cells are around it. This is a valid solution, but you can imagine that it quickly gets inefficient. Each cell must iterate through every other cell, every time it wants to count its neighbors! This is known as big O(N²) computational time, meaning the number of calculations required for one "turn" is the square of the number of cells in your array. Also, creating cells gets tricky; since we aren’t making objects for empty cells, measuring the right conditions for a new cell isn’t trivial. In boards with millions of cells, our poor, non-quantum computers will become sad.
|Fig 3. Very sad|
Board as Object
Here’s an option that allows you to only iterate over each cell once, and then each square of the board once. The board is an object, storing an array of positions (cells), with two main methods: get_board_size, and check_board.
class Board @cells = [(x1, y1), (x2, y2), (x3, y3), ...] def get_board_size @cells.each find min(x, y) and max(x, y) end def check_board from board min(x, y) to board max(x, y) check_neighbors if neighbors create_cell / destroy_cell
This allows you to only go over each cell once, to get the size of the board. Then you iterate over the whole board to create and destroy cells. This puts you in the realm of O(N) computational time, meaning the number of calculations your program makes will increase linearly with the number of cells on your board.
There’s good reason Game of Life shows up a lot on lists of coding “katas” and exercises; the rules are simple, but the implementation can vary wildly. The two examples I covered here are only two of the object-oriented possibilities — can you think of ways to make the game in a functional programming environment, for example? There are solutions with finite boards; with hexagons instead of squares; or even with their grids on three-dimensional objects. Check out the gnarly Trefoil Knot life below.
You can find my functional-ish Python solution below, which adds simple ASCII visualization, and a small list of preset patterns.