Archive

Archive for February, 2009

Counting Lakes

February 6th, 2009

In Conway’s Game of Life, a lake is a pattern that is a simple closed loop made up of diagonally-adjacent dominoes. It is a fact that lakes are always still lifes and that their number of cells is always a multiple of eight, but no one seems to have calculated the number of distinct (ie. not the same under rotation or reflection) lakes that exist on 8n cells; possibly because it’s not a particularly interesting problem (blasphemy!) or possibly because it’s a rather difficult problem (or most likely a combination of the two).

Indeed, computing an explicit formula for the number of lakes on 8n cells seems to be nigh intractable (although some people disagree). In place of an explicit formula I have simply gone the computer science route and coded a little C program to do the counting. The program’s running time is somewhere in the area of O(4n) since it basically brute-forces the solution by noting that lakes are in 1-1 correspondence with walks on a 2D lattice that have three properties: 1) they turn 90 degrees after each step of length one, 2) they eventually return to the starting position, and 3) they never cross a grid point that they’d previously visited (except on the last step when they return to the start).

The sequence (as far as I have computed it) of the number of lakes on 8n cells for n = 1, 2, 3, … is 1, 0, 1, 1, 4, 7, 31, 98, 446, 1894, 9049, 43151 … (Sloane’s A156228). The C source code is provided below in case you’re interested.

Download:

The two smallest lakes, pond and lake 2: