Today I ran across an interesting paper. It gives a simple recurrence relationship to generate the elements of first *n* rows of a Stern-Brocot tree.

It’s surprisingly simple. To generate the first *n+1* rows, take the values

where

given

where

for odd *j* and non-negative *v*_{i}.

Put informally, *v*_{i} is the number of trailing zeroes in the binary representation of *i*.

What’s surprising about this sequence is that it produces a list that is rational, increasing and unique.

Lindenmayer Systems, or L-Systems are not complicated. Take a string as a set of instructions in turtle graphics. “L” means “turn left”, “R” means “turn right”, and “F” means “go forward”.

Now imagine starting with a string “A” and a set of rules. You replace the characters in this string according to the rule a fixed number of times. Then for every type of character, you can either replace it with one of “`L`

“, “`R`

“ or “`F`

“, or ignore/remove it.

For example, suppose you have one rule,

and a final rule

In this example, it takes 12 or 12 turns to turn completely around.

We start with and apply the rule to get . We apply the rule again to get , and so forth. In my example, I stopped when I got a string that would have 5000 forward moves in it.

Here’s what it looks like:

That’s one continuously traced path, all thanks to string rewriting. I’ve also created a page with a large number of random rules. It takes a lot of memory because of all the thumbnails, but if you’re curious about the rules used to generate a shape, simply follow the link to the SVG and “view source” to see what generated that shape.

I finally made to to 200 problems! Better yet, I picked two of the problems that had been pestering me for a while:

As I was working on “Robot Walks”, I figured out that I’d come *very* close to the solution last year. I had a lookup table, but it had an incorrect value for orientation in cases where the robot moved in a complete circle right or left.

This is definitely my favorite javascript pattern, since it allows for clean, modular libraries. If you’re writing your own javascript library, it’s an approach worth considering, even if you don’t use the YUI wrappers.

Based on the same space-filling curve, but with a little more variety in the parameters.