cartesian product … stuff about computing mostly

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.

Related articles
Advertisement

Adrian McMenamin

, , , ,

2 responses to “Life and polyominoes”

  1. Hugh Avatar
    Hugh

    Actually, the sequence A094169 is “rooted 2-dimensional polyominoes with n octagonal cells, with no symmetries removed”. Those are not ordinary (square-celled) polyominoes. All the states of the glider gun in the animation (from Wikipedia?) would be proper octagonal cell polyominoes.

    “Octagonal” is meant to convey the idea that connections can be along the diagonals.

    There are only 63 conventional fixed polyominoes with 5 (square) cells. See A001168.

    Jargon: “fixed” means the same as “with no symmetries removed”.

    I had hoped “rooted” meant “treating all translations as one” but clearly it doesn’t since A094169[2] is 8 rather than 4. That means we really want to use the sequence A094169[i]/i (justification: for each fixed polyomino of size i, there are i cells to pick as a root and thus i rooted fixed polyominoes). The value at 5 of this new sequence is 30720 / 5 = 6144 — even fewer to check.

    If you could easily generate the free polyominoes (treating all reflections and rotations as one), that would be even fewer, but generating just those is hard. It is easier to generate the fixed ones and filter out the duplicates (from a free viewpoint).

    For each asymmetric free polyomino with octagonal cells, I think that there are 16 corresponding fixed polyominoes (8 for rotations * 2 for mirroring). As the number of cells gets large, almost all polyominoes are asymmetric.

    If you want to consider configurations that are disconnected by a small amount, the fixed polyomino generator can do that: all you have to do is adjust its idea of “neighbour”.

    1. Adrian McMenamin Avatar
      Adrian McMenamin

      Do you mean 3230/5? And then we have to factor in that 5 of the patterns are isomorphic – ie form the glider – and then that we would expect, on average, to hit a working solution half way through, meaning, if it took a minute to test each potential solution on average we would hit paydirt after an average of 3230/50 = 65 minutes.
      Just an hour’s work. The children’s failure doesn’t seem quite so heroic now 🙂
      Or have I got this wrong again?

%d bloggers like this: