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.

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.)

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.

More work on Life.groovy

According to “Groovy in Action” lists of lists are the correct way to do multidimensional arrays in Groovy, so I reckon I will try that now – as well as making some better use of some of the other language features, such as better use of ranges, that I noticed could be done.