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(4ⁿ) 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:

• C source code (zip file): numLakes.zip (1.48kB)
• C source code (plaintext): numLakes.txt

The two smallest lakes, pond and lake 2:

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:

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:

PS. Happy birthday to me!

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.

The idea of math-based CAPTCHAs has been around for a while, but it still hasn’t caught on much for some reason. Personally, I think the idea of a website asking you to enter the value of 7 + 8 is much less annoying than it asking you to squint and try to make out distorted letters and numbers. Thus, I have put together four ASP math-based CAPTCHA scripts that are freely-available for download and can be used or modified however you see fit. I have outlined the pros and cons of each of the scripts to help you decide which (if any) of them is right for you. Note that all four of these scripts make use of the AspJpeg component though the scripts could easily be modified to work with other components or produce text output.

Arithmetic CAPTCHA

This is the most basic of the math CAPTCHA scripts — it asks the user to provide the answer to a simple arithmetic question (either addition, subtraction, multiplication, or division). The script could easily be modified to ask more complicated questions such as “(12 / 4) + 7 = ?” or “3³ = ?”.

Features and Benefits:

• You can select the difficulty of the questions that the CAPTCHA asks.

Downsides:

• If the difficulty is low, most answers will be in the range 1 – 25, which means that a SPAMbot has a decent chance of randomly guessing the correct answer.

Example:

 

Download:

• Download arithmetic.zip (v1.00 — 5.18kB)
• Test it Online

 

Dictionary CAPTCHA

Quite a few websites now use CAPTCHAs that display words rather than random letters and numbers, and that is definitely a step in the right direction towards making CAPTCHAs less annoying. One step further though, is to use themed word lists that fit with the content of your website. This script does exactly that; it displays three words randomly selected from word lists that you create.

Features and Benefits:

• Won’t alienate users with no math knowledge.
• Comes with enough math terms to generate over 25 000 unique CAPTCHAs.
• Word lists can easily be customized to fit any website.

Downsides:

• Defeated reasonably easily by OCR software (this could be fixed by adding lines through the image and so on).

Example:

 

Download:

• Download dictionary.zip (v1.00 — 5.89kB)
• Test it Online

 

Sequence CAPTCHA

The Sequence CAPTCHA displays a sequence of numbers and asks the user to predict the next number in the sequence. The script generates one of three types of sequences: arithmetic, geometric, or Fibonacci-type. However, you could easily edit the code to generate some really nasty sequences if you dislike the visitors of your website that much.

Features and Benefits:

• It’s reasonably immune to being broken by SPAMbots, unless someone spends a lot of time making a script specifically for your website.

Downsides:

• Unless your visitors are very math-oriented, they will hate you.

Example:

 

Download:

• Download sequence.zip (v1.00 — 5.41kB)
• Test it Online

 

Word Arithmetic CAPTCHA

This is a simple twist on the Arithmetic CAPTCHA that replaces the numbers by words and thus asks questions like “Ten × Four = ?”. The questions are slightly easier by default than the questions in the Arithmetic CAPTCHA script.

Features and Benefits:

• Accepts both numeric and word input from the user.
• Quite resilient against being broken by SPAMbots.

Downsides:

• As with the Arithmetic CAPTCHA, a random answer in the range 1 – 25 has a decent chance of being correct.
• Some questions like “Forty Three – Twenty Seven” might scare away certain users. Then again, those may be precisely the types of users that you want to scare away.

Example:

 

Download:

• Download wordarithmetic.zip (v1.00 — 5.76kB)
• Test it Online

Here are some scripts that can be used to estimate (or in some cases, calculate exactly) the completely bounded norm of linear maps. The algorithm that these scripts are based on was described in this paper. If the given map is completely positive, then the exact cb norm of that map is calculated and given as the output of these scripts. If the given map is not completely positive, then an upper bound is given for the completely bounded norm — run the script with a high number of iterations to obtain a tighter upper bound.

MATLAB Script

This is the recommended script for estimating the cb norm of a map as it is currently the fastest implementation of the algorithm that I have. The script consists of one .m file (zipped in a .zip archive) for MATLAB. After extracting this file and putting it in your MATLAB scripts directory, you will be able to use the CBNorm function; an example of how to use this function is provided here:

>> A(:,:,1) = diag([exp(-5*i*pi/4),exp(-i*pi),exp(-3*i*pi/4)]);
>> A(:,:,2) = eye(3);
>> B(:,:,1) = diag([exp(5*i*pi/4),exp(i*pi),exp(3*i*pi/4)]);
>> B(:,:,2) = -eye(3);
>> CBNorm(A,B,1000)

ans =
    1.4390

In the above example, the completely bounded norm of the map was estimated based on 1 000 iterations of the algorithm (which took just under half of a second on my laptop). We know from Theorem 26 that the actual completely bounded norm of that map is sqrt(2), so the relative error of our estimate is about 1.75%.

Download:

• MATLAB Code [zip, v1.00 — 2.45kB]

Maple Script

This is an alternative script for estimating the cb norm of a map for people who either can not use the MATLAB script above or simply prefer working with Maple. This .zip archive contains three files: a Maple 8 worksheet, a Maple 11 worksheet, and a plain text version of the script. Example code for how to use the script is provided on the Maple worksheets, but here is the example code if you are loading in the procedures from the plain text file:

> NumOps:=2:
> NumIts:=100:
> A:=Array(1..NumOps):
> B:=Array(1..NumOps):
> A[1]:=DiagonalMatrix([exp(-5*I*Pi/4),exp(-I*Pi),exp(-3*I*Pi/4)]):
> A[2]:=IdentityMatrix(3):
> B[1]:=DiagonalMatrix([exp(5*I*Pi/4),exp(I*Pi),exp(3*I*Pi/4)]):
> B[2]:=-IdentityMatrix(3):
> CBNorm(A,B,NumIts,NumOps);

The output of the above commands was 1.4932 based on 100 iterations of the algorithm (which took about 7 seconds on my laptop). We know from Theorem 26 that the actual completely bounded norm of that map is sqrt(2), so the relative error of our estimate is about 5.59%.

Download:

• Maple Code [zip, v1.00 — 17.7kB]

Related Links:

• Computing Stabilized Norms for Quantum Operations via the Theory of Completely Bounded Maps — The paper describing the algorithm that these scripts were based on.