Life and polyominoes

Update: It seems I got all this wrong (again!). See Hugh’s comment here

A little while ago I wrote of how I had challenged the children I work with in a Code Club to find the glider pattern in Conway’s Game of Life.

I suggested that, if they adopted an essentially random approach to putting down counters within one cell of existing counters they would need about three weeks of continuous work to find the solution as there are about 30,000 such patterns and I estimated it would take a minute, on average, to check the solution for longevity. (In fact I over estimated the average time by 50%, because, of course we should expect to trip over the correct solution, on average, at the half way point – if we adopted a truly random approach to this of course.)

Hugh who is a regular and learned commentator here then drew my attention to sequence A094169 in the “Online Encyclopedia of Integer Sequences” to suggest that there were only, in fact 3,230 possible solutions to be checked – as that is the number of five cell polyominoes (to be fair to Hugh he suggested that polyominoes were not the only potential solutions of interest).

Glider patternIn fact if we looked at polyominoes we would never find the solution – as the glider is not a polyomino – none of the five configurations has every counter/cell joined edge to edge.

But I am again forced to reduce the time – because there are essentially five glider patterns (or if you like any one glider pattern is isomorphic to four others) – and any one of them would do – so we are left with an expectation that we’d find the pattern in about 3,000 random tests – more or less the same number as the count for the pentominoes.

How many solutions to check?

I asked the year 6 (10- and 11-year-olds) children I teach through Code Club if they could find the five cell pattern that kept a Game of Life board going indefinitely (ie., could they find the “glider” pattern?).

Their prize if they manage it in the next week is chocolate. Of course they could look it up on the Internet – and I won’t object if they do, because they will still have shown intelligence in piecing together the clues.

But what if they search for solution in some algorithmic way? (Actually one of them already sent me an answer which was quite close to correct but was actually a sort of “Methuselah” pattern which filled the screen with living cells before reaching a stasis after about 115 generations.)

Well the first thing they could do is just plonk down 5 counters at random on the board and see if one of these patterns was the correct one. Let’s say they approach this totally randomly and – on average – it takes a minute to determine if the solution is correct or not.

There are obviously {400 \choose 5} possible solutions (this is the binomial coefficient/expansion – we are picking 5 spots at random from 400 possible spots as the board has a 20 x 20 grid) – this is \frac{400!}{(400 - 5)!5!} which is approximately 10^{13} – so using this method would take around the known age of the universe, give an order or two, to find the solution.

So, if we did this by checking cells which were, at most, one cell away from a previous cell? (The work below is my own, I think it’s right!)

Well the first cell could be anywhere, the location does not matter : 1

The second cell could then be in one of eight positions: 1 x 8

The third cell could then be in one of twelve positions: 1 x 8 x 12

The fourth could then be in one of sixteen positions: 1 x 8 x 12 x 16

And the fifth could then be in one of twenty positions: 1 x 8 x 12 x 16 x 20

This would take a mere 30,000 minutes or so to check: a good three weeks or so of continuous work.

More than a game: the Game of Life

English: Diagram from the Game of Life
English: Diagram from the Game of Life (Photo credit: Wikipedia)

Conway’s Game of Life has long fascinated me. Thirty years ago I wrote some Z80 machine code to run it on a Sinclair ZX80 and when I wrote BINSIC, my reimplentation of Sinclair ZX81 BASIC, Life was the obvious choice for a demonstration piece of BASIC (and I had to rewrite it from scratch when I discovered that the version in Basic Computer Games was banjaxed).

But Life is much more than a game – it continues to be the foundation of ongoing research into computability and geometry – as the linked article in the New Scientist reports.

For me, it’s just fun though. When I wrote my first version of it back in 1981 I merely used the rubric in Basic Computer Games – there was no description of gliders or any of the other fascinating patterns that the game throws up – so in a sense I “discovered” them independently, with all the excitement that implies: it is certainly possible to spend hours typing in patterns to see what results they produce and to keep coming back for more.

  • “Life.bas” should run on any system that will support the Java SDK – for instance it will run on a Raspberry Pi – follow the instructions on the BINSIC page. A more up to date version may be available in the Github repository at any given time (for instance, at the time of writing, the version in Git supports graphics plotting, the version in the JAR file on the server only supports text plotting). On the other hand, at any given time the version in Git may not work at all: thems the breaks. If you need assistance then just comment here or email me adrianmcmenamin at gmail.