Null-String

Here. Have another animation. This one has colours.

Considering how long it’s been since I updated my blog (just under two months), you’d think I’d have put slightly more effort into this post.

You’d be wrong. This is almost exactly the same code as the Hilbert curve animation, but I adjusted the generator code for the L-system to generate a Heighway Dragon Curve instead of a Hilbert curve.

Just a bit of Sunday afternoon fun. A little Hilbert space-filling curve animation, implemented as an L-system.

EDIT: For those of you who missed my retweet, you should also watch Vi Hart’s video on space-filling curves.

First, the fun bit:

(Bigger version)

To use: enter a code into the box, and press the “Go!” button to see the pattern. Try out a few codes. Particularly, try 150, 110, 182, 22, 18, and whatever else you can think of. Also, make sure to try some of them with the “random pixels” setting, as well as the “1 pixel” settings. The “Complement” button finds the code which generates the same pattern, but with black and white reversed. You can enter hex codes into the box if you prefix them with ‘0x’, or octal if you use a leading 0. If that’s your cup of tea.

What am I looking at?

You’re looking at a time vs. space graph of a one-dimensional cellular automata system. Each row of the graph is a generation; black pixels represent live cells, and white ones represent dead cells. Each row is generated using a simple set of rules, taking into account the previous state of the cell and its immediate neighbors. The rule corresponding to the code is depicted by the row of t-shapes in the grey rectangle. Also, this is a circular graph - the left edge wraps around to the right, and vice versa.

What’s so cool about this?

It makes pretty pictures! On that front, check out rule 150 with random pixels as the starting pattern. If you make an n-pixel wide pattern, it’ll repeat every n/2 pixels if you have wraparound (which this does). Rule 30 can be used as a random number generator, and rule 110 can be used to build a computer. Yes, a computer - specifically a Turing machine, which is a machine which, given enough space and time, can be used to compute any computable problem. Pretty slow though, and a real pain to program.

How does the code map to the rule?

Well, since there are 8 rules which make up every graph, a chap named Wolfram came up with the idea of using the on-off pattern of the rules as an 8-bit binary number. For example look at the on-off pattern of rule 30: or 00011110. That binary number corresponds to decimal 30. The upshot of this is that each of the 256 rulesets can be described using a number from 0 through 255, which is quite convenient.

Enjoy!

Since I published Mercurial current branch in your Bash prompt in April, I’ve made some improvements.

The first is that, in a freshly initialized Mercurial repo, reporoot/.hg/branch isn’t written, so fasthgbranch doesn’t find anything. The fix for this is simple: just output “default” if you find a Mercurial repo, but no branch file.

The second is that it now works on Mac OS X (and probably, by extension, *BSD). I recently got a programming job (where we use Mercurial!), and my work computer is a Mac. Porting to OS X involved two changes. Firstly, I had to replace the Linux-only system call get_current_dir_name() with the equivalent getcwd(NULL, 0), which is also a Linux extension to POSIX, but happens to work on OS X too. Secondly, OS X sed behaves slightly differently from GNU sed. GNU sed supports both “&” and “\0” to mean “the entire match”, while OS X sed only supports &.

All of these improvements have been reflected in the original article.