Tagged: conways game of life

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

Why I love Metapost


I am writing some stuff about Conway’s Game of Life (and Scratch) – thinking about whether it is possible to explain to adults the basics of programming a computer using the Scratch Life script an an example: Life is more suitable for adults than say the Code Club fish chasing game and anyway it gives me an opportunity to indulge my fascination with the game.

To write the text I need to draw diagrams that explain how the rules work and I tried in both Xfig and Dia to do this. But it was a nightmare.

In contrast I could manage it very quickly in Metapost, even though the natural inclination is to steer clear of that and stick with the “point and drool” GUI based alternatives.

beginfig(1);
prologues:=3;

for i=0 upto 4:
draw (0, i*20 + 10) — (100, i*20 + 10);
draw (10 + i*20, 0) — (10 + i*20, 100);
draw (200, i*20 + 10) — (300, i*20 + 10);
draw (210 + i*20, 0) — (210 + i*20, 100);
endfor;

pickup pencircle scaled 12;
draw (140, 40) — (150, 50)–(140, 60) withcolor red;
linejoin:=mitered;

path a, b, c, d, e, f, g, h, j, k, l, m;
a = fullcircle scaled 10 shifted (40,40);
draw a;
fill a withcolor green;
b = fullcircle scaled 10 shifted (40,60);
draw b;
fill b withcolor green;
c = fullcircle scaled 10 shifted (60,60);
draw c;
fill c withcolor green;
h = fullcircle scaled 10 shifted (60,40);
draw h;
fill h withcolor green;
j = fullcircle scaled 10 shifted (40,20);
draw j;
fill j withcolor green;
k = fullcircle scaled 10 shifted (60,20);
draw k;
fill k withcolor green;

d = fullcircle scaled 10 shifted (220,40);
draw d;
fill d withcolor green;
e = fullcircle scaled 10 shifted (240,60);
draw e;
fill e withcolor green;
f = fullcircle scaled 10 shifted (260,60);
draw f;
fill f withcolor green;
g = fullcircle scaled 10 shifted (280,40);
draw g;
fill g withcolor green;
l = fullcircle scaled 10 shifted (240,20);
draw l;
fill l withcolor green;
m = fullcircle scaled 10 shifted (260,20);
draw m;
fill m withcolor green;
endfig;

Gives me this: (actually the original EPS is better as it is a vector format and the PNG won’t scale in the same way)

Conway's Game of Life patternMetapost is not widely known and under-appreciated.

The Art of Scratch, Code Club and the ICT curriculum


Scratch Project

Regular readers will know I have something of a small obsession with Conway’s Game of Life – the classic “game for no players” based on cellular automata, and so, naturally enough, when I decided that I really had to write my own Scratch program from, err, scratch to sharpen up my skills for teaching children via Code Club, that is what I chose to write – the (not very sophisticated) results can be seen above.

My first conclusion is that Scratch is a truly awful tool for most programming tasks. I know it is not meant to be a general programming tool, but I quickly discovered that it is hobbled even when it comes to doing those things that one assumes, at first glance, it is set up to do – like drawing on the screen. Scratch actually has very, very limited functionality/expressive power when it comes to drawing graphics – being only able to handle pre-provided sprites (as first class objects) and using a pen which marks out one pixel at a time – thus one cannot (at least easily) find a way to draw anything beyond dots and lines on the screen in response to events.

If you run the above program using the Flash player provided by the Scratch site you will probably see one of the big downsides of that as outlines of the old crosses are left on the screen (the Java player does not have this problem but it is very slow in comparison).

From a teaching point of view I also find Scratch’s message-based system less helpful than an imperative GOSUB like approach: the children I work with, after many weeks, are still struggling with the idea that messages should drive actions (probably we should blame their instructor!) – I know this event-based style is more common in the real world, but I think teaching the idea of problem decomposition via subroutines or functions is probably more important educationally.

Yesterday I went to the first London Hackntalk and gave an impromptu (and so unprepared) and brief talk on my thoughts about teaching children to program – my experience with Code Club makes me rather less starry-eyed about mass programming education. There were a few responses from the audience which suggested I had not really got my point – that we would struggle to fully replace an ICT curriculum based on usage skills with one based on programming – as the audience continually suggested ways to get motivated and engaged kids into programming (rather than make it a mass participation thing), but one point that was made by a member of the audience was very acute – given what our children see computers do in games that cost many millions to develop, how realistic is it to expect all or many of them to put lots of effort into toy programs that chug out the sort of graphics you can see above? I think that is a really difficult issue we have to consider when overhauling the curriculum and I am not sure the enthusiasts of radical change (of which I was and still am one) have thought it through fully.

(I did also encourage them to be Code Club instructors and was a bit disappointed to see that I appeared to be the only one – we urgently need to teach more programming and so these problems of the early days of the overhaul should not obscure the need for change.)

Related articles

The wheels of Aristotle


Sometimes you come across a thing where beauty matches simplicity, and Aristotle’s Wheel Paradox is just such a thing.

I came across it this afternoon after I returned to London from two too-short weeks away and a second-hand book I’d ordered, Wheels, Life and Other Mathematical Amusements, based on Martin Gardner‘s columns for the Scientific American.

I bought it because it has three chapters on Conway’s Game of Life – but the very first pages introduced me to Artistotle’s Wheel Paradox – which I’ll now explain…

Aristotle's Wheel Paradox

Imagine, as in the diagram above a small wheel that runs in parallel (eg., because it is attached) to a larger wheel. The large wheel runs on the line A to B, the smaller runs on C to D.

At every point the large wheel touches the line AB, an equivalent point on the small wheel touches CD: so there is a fixed and unique equivalent point on the small wheel for every point on the large wheel.

So that means when the large wheel has completed a revolution then so will the small wheel.

But if there is a fixed and unique equivalent point on the small wheel to every point on the large wheel that must surely imply their circumference is the same?

This is the paradox. And it’s one that puzzled many of the mathematical greats of past ages.

The solution is down to Georg Cantor and his formulation of the continuum. For there are an uncountable infinity of points on the rim of the two wheels. (Gardner describes this as Cantor’s Aleph-One – \aleph_1 – and indeed Cantor thought it so – this is his continuum hypothesis – but it remains unproven that the continuum is indeed \aleph_1 as opposed to a higher \aleph .)

One final note – the book I bought is stamped “University Library Hull Withdrawn” and an online search suggests that this book is indeed no longer available to students at Hull. But how can it be justified that a major university gets rid of books in this way? Their loss, my gain though, of course.

Related articles

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.
Related articles

BINSIC plotting working


At the risk of being attacked as an enemy of all that is good, I have to confess to being less than riveted by the Olympics, so far. So I have made far more productive use of my time in seeking to recreate the computing experience of 30 years ago – by working some more on BINSIC – Binsic Is Not Sinclair Instruction Code, my reimplementation of Sinclair ZX81 BASIC.

I have finally got PLOT and UNPLOT to work – not on the same screen as ordinary output, but on a separate graphics console.

Game of Life on BINSIC graphics consoleAs the above – from Conway’s Game of Life –  shows, this has all the sophistication and élan of the original ZX81 experience!

It’s just in the Git repo now (at Github under mcmenaminadrian) but an executable JAR will follow shortly.

 

Related articles

Relive the ZX81 experience on your desktop


BINSIC – my reimplementation of ZX80 or ZX81 (Timex Sinclair 1000 or 1500 for US readers) BASIC is now available for download in binary form – look at the page on the site: Binsic Is Not Sinclair Instruction Code.

It comes with Conway’s Game of Life for the authentic black and white text based feel too.

(Source code is also available here)

Life: rewritten


Well, what else was I going to do? This works and that means I think BINSIC does too. It’s not quite a fully functional BASIC – try as I might I cannot get GOTO or even GOSUB to work inside loops (though I might do better if plough on with the GOSUB stuff), but I’ll hopefully launch it all tomorrow evening.

10 REM Game of Life
20 PRINT "Conway's Game of Life"
30 PRINT "Copyright Adrian McMenamin, 2012"
35 PRINT "adrianmcmenamin@gmail.com"
40 PRINT "Licensed under the GPL version 3"
50 DIM A(48, 70)
60 DIM B$(24)
70 PRINT "Please enter your pattern"
75 PRINT " - up to 24 lines of 70 characters"
80 FOR I = 1 TO 24
90 INPUT B$(I)
95 LET T = 0
97 IF B$(I) = "DONE" THEN LET T = 1
98 IF T = 1 THEN LET B$(I) = ""
100 IF T = 1  THEN GOTO 150
110 PRINT B$(I)
120 NEXT I
150 REM Parse Input
160 LET P = 0
170 LET G = 0
175 LET Y = 0
177 LET Q = 0
180 FOR Y = 1 TO 24
190 LET Z = LEN B$(Y)
210 IF Z = 0 THEN NEXT Y
220 FOR Q = 1 TO Z
222 LET A(Y, Q) = 0
225 IF MID$(B$(Y), Q, 1) = " " THEN LET A(Y + 24, Q) = 0
230 IF MID$(B$(Y), Q, 1) <> " " THEN LET A(Y, Q) = 1
232 IF MID$(B$(Y), Q, 1) <> " " THEN LET A(Y + 24, Q) = 1
234 IF MID$(B$(Y), Q, 1) <> " " THEN LET P = P + 1
240 NEXT Q
250 FOR Q = Z + 1 TO 70
260 LET A(Y, Q) = 0
265 LET A(Y + 24, Q) = 0
270 NEXT Q
280 NEXT Y
300 REM Display Map
310 PRINT
320 PRINT
330 PRINT
340 PRINT "Generation ", G, " Population is ", P
350 FOR M = 1 TO 24
355 PRINT
360 FOR N = 1 TO 70
370 IF A(M + 24, N) = 1 THEN PRINT "*";
375 IF A(M + 24, N) <> 1 THEN PRINT " ";
380 NEXT N
390 NEXT M
400 REM Map next generation
410 FOR M = 1 TO 24
420 FOR N = 1 TO 70
430 LET A(M, N) = 0
440 IF M + 1 < 25 AND A(M + 25, N) = 1 THEN LET A(M, N) = A(M, N) + 1
450 IF M - 1 > 0 AND A(M + 23, N) = 1 THEN LET A(M, N) = A(M, N) + 1
460 IF N + 1 < 71 AND A(M + 24, N + 1) = 1 THEN LET A(M, N) = A(M, N) + 1
470 IF N - 1 > 0 AND A(M + 24, N - 1) = 1 THEN LET A(M, N) = A(M, N) + 1
480 IF M - 1 > 0 AND N - 1 > 0 AND A(M + 23, N - 1) = 1 THEN LET A(M, N) = A(M, N) + 1
490 IF M - 1 > 0 AND N + 1 < 71 AND A(M + 23, N + 1) = 1 THEN LET A(M, N) = A(M, N) + 1
500 IF M + 1 < 25 AND N - 1 > 0 AND A(M + 25, N - 1) = 1 THEN LET A(M, N) = A(M, N) + 1
510 IF M + 1 < 25 AND N + 1 < 71 AND A(M + 25, N + 1) = 1 THEN LET A(M, N) = A(M, N) + 1
520 NEXT N
530 NEXT M
540 LET P = 0
600 FOR M = 1 TO 24
610 FOR N = 1 TO 70
611 LET ZZ = 0
612 LET SC = A(M, N)
612 IF A(M + 24, N) = 1 THEN LET ZZ = 1
613 LET RES = 0
614 IF ZZ = 0 AND SC = 3 THEN LET RES = 1
615 IF ZZ = 1 AND (SC = 2 OR SC = 3) THEN LET RES = 1
616 LET A(M + 24, N) = RES
617 LET P = P + RES
650 NEXT N
660 NEXT M
700 PAUSE 50000
800 LET G = G + 1
900 GOTO 310

A problem with Life


Bill Gosper's Glider Gun in action—a variation...

Bill Gosper’s Glider Gun in action—a variation of Conway’s Game of Life. This image was made by using Life32 v2.15 beta, by Johan G. Bontes. (Photo credit: Wikipedia)

I had hoped to “launch” BINSIC – Binsic Is Not Sinclair Instruction Code – my BASIC-as-a-DSL project built using Groovy, this weekend. For the launch I wanted to publish a jar file (so usable by everyone with Java) that ran the version of Conway’s Game of Life (seemed very appropriate for both general – Life being the ultimate hacker meme – and personal – I once wrote a version of Life in Z80 machine code for the ZX80 – reasons) found in Basic Computer Games – but I don’t think I am going to manage it now

The problem is that the code in the book is totally banjaxxed. It uses variables before they are declared and in general looks as though either some lines have been transposed or some code has been omitted altogether. It is certainly plain that the printout of the running program in the book does not reflect the code found on its pages. In any case hacking at this code reveals the full horror of BASIC and how difficult it is to maintain code that is not even in blocks, never mind any other sort of order.

So I have two choices – refactor the BASIC I have in quite a big way to get it to run, or find some new code instead.

But the exercise has not been completely wasted. While hunting down the bugs in David H Ahl’s code I have found more than a few in BINSIC itself.

Related articles