Archive

Posts Tagged ‘Coding’

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:

My New Project: Conway’s Game of Life

January 16th, 2009

Sometime around the start of December I was reminded of Conway’s Game of Life – a mathematical “game” that I was first introduced to in my grade 12 programming class. Unfortunately for me and my research, I found the game much more interesting this time around and have proceeded to spend almost the entire last month dedicated to it.

It started out innocently enough; I thought that a webpage that uses the canvas tag to run the Game of Life would be the perfect way to hammer home what I was talking about in this post. It turns out that the game gets quite computationally intensive for even moderately-sized patterns however, so although the tool was functional, it chugged. What would be the solution to this problem? Write the tool in a pre-compiled programming language like Java, of course.

There are several Java implementations of the game freely available on the internet, but at this point I wanted to make an online tool that does a bit more than just evolve patterns; I wanted also to be able to upload, save, and download pattern files from the tool, something that is quite impossible from a Java applet. Also, because building interfaces for Java applets is a bit of a chore, most of the pre-existing Java applets implementing the game are a bit hard to look at. All of these problems can be solved via a bit of server-side ASP and some Java-to-javascript communication, fortunately (something I will post about separately later).

The end result? Well, I don’t really know yet, but here’s the beta 0.2.0 result:

ConwayLife.com

The Java applet that runs the game itself is based on Alan Hensel’s brilliantly fast Java staggerstep algorithm, with some added file manipulation functionality and a dynamic online database of patterns. The applet is still very much a work in progress and there are quite a few known bugs, but it works well enough for now.

The real star of the website for now is the LifeWiki, which I’m hoping will fill a huge gap on the internet that I was rather shocked to find – even though there are many great homepages with bits and pieces of information about the game scattered across the internet, there really is no central resource that catalogues everything about the game; LifeWiki will hopefully fill that gap. I have started it off with some 150 articles and uploaded as many images, but I’m hoping that I can draw a few other Life enthusiasts to the wiki to help expand it so as to ease some of the burden.

Anyway, that’s about all I have to say for now about the website; I’ll likely make another post or two in the reasonably near future with coding tips/tricks based on my experience making the tool and site in general. Until then, I present to you my favourite pattern for the Game of Life, the Canada goose:

Canada goose

PS. Happy birthday to me!

A Case for Canvas

October 30th, 2008

I recently came across this page, which shows a rudimentary rotating 3D cube made entirely of javascript. Since I’m a code geek I of course thought it deserved a kudo or two, but it got me thinking; why isn’t the canvas tag more widely used (or supported natively in Internet Explorer)? For those of you who don’t know what the canvas tag is, it’s essentially an environment for drawing things on the fly in web pages, without having to use a plug-in like Flash. It is probably something that is easiest to appreciate through some examples, so I present to you the following simple comparison of what can be done with javascript alone versus javascript plus the canvas tag (scroll your mouse over the cubes to rotate them):

Javascript Only:

Javascript and the Canvas Tag:

The top cube makes use of 18 images (for drawing the lines via the trick described here) and about 1.0kB of javascript code. The bottom cube is animated using 509 bytes of javascript code in conjunction with the canvas tag. That’s it — no auxilliary images or plug-ins of any kind.

Personally, I think that’s pretty awesome, and I wish that the usage of the canvas tag would leave the realm of the tech demo. People need to realize its potential and start really using it. It’s supported in all major current browsers (OK, you have to do some trickery to get it to work in Internet Explorer, but it still requires no work on the part of the end-user) and it does things that simply can not be done otherwise without loading a plug-in like Flash. Consider the following variation of the 3D rotating cube:

Colour Cube via Canvas Tag:

I believe that it’s flat-out impossible to replicate the above coloured cube using only CSS and javascript without the canvas tag, but even if it is possible, it certainly won’t be easy or scalable — the canvas tag is both.

Related Links

  • Canvas Tutorial – A tutorial provided by Mozilla for using the canvas tag.