Heighway Dragon

Let D0 be the two-letter string “Fa”. For n≥1, derive Dn from Dn-1 by the string-rewriting rules:
“a” → “aRbFR”
“b” → “LFaLb”
Thus, D0 = “Fa”, D1 = “FaRbFR”, D2 = “FaRbFRRLFaLbFR”, and so on.
These strings can be interpreted as instructions to a computer graphics program, with “F” meaning “draw forward one unit”, “L” meaning “turn left 90 degrees”, “R” meaning “turn right 90 degrees”, and “a” and “b” being ignored. The initial position of the computer cursor is (0,0), pointing up towards (0,1).
Then Dn is an exotic drawing known as the Heighway Dragon of order n. For example, D10 is shown below; counting each “F” as one step, the highlighted spot at (18,16) is the position reached after 500 steps.

What is the position of the cursor after 1012 steps in D50 ?
Give your answer in the form x,y with no spaces.

This is a problem from Project Euler (problem number 220) and involves concepts of string manipulation as well as recursion. The given problem is about the Heighway Dragon curve, which is an example of a self-similar fractal curve.

Calculating this value directly would take a significant amount of time since we have to compute Dn for n = 50, which is a massive string, and then perform 10^12 operations – clearly not practical. So we need to exploit the recursive structure of the problem in order to solve it efficiently.

The key insight is that the Dn curve for any n>0 consists of a copy of the Dn-1 curve, followed by a turn to the right, followed by a “reflected” copy of the Dn-1 curve where every turn is reversed (left turns become right turns and vice versa). Since the lengths of the Dn curves increase exponentially with n, the vast majority of the 10^12 steps will be within a replicated and/or reflected part of the Dn-1 curve.

So we can solve this problem as follows:

1) Compute D1, D2, D3, … up to D50, but rather than compute the actual strings, just compute the displacements and orientations of the endpoints after 1, 2, 4, …, 2^49 copies of the original D0 curve. Note that the displacements and orientations follow very simple rules: for n>0, the displacement of Dn is twice the displacement of Dn-1 rotated 45 degrees to the right, and the orientation of Dn is the orientation of Dn-1 rotated 45 degrees to the right.

2) Starting at D50 and working down to D0, check if the total length of the Dn curve is less than or equal to the remaining number of steps. If it is, subtract the length of the Dn curve from the remaining number of steps and move the cursor by the amount of the displacement of the Dn curve, updating its orientation accordingly.

3) Repeat step 2) until no steps remain.

Note: An important detail is that we can “skip over” parts of the curve that correspond to future sets of 2^49 steps, since at each such point the cursor is back at the origin.

Running this process would not be terribly difficult using a language with good support for large integers and complex numbers, but explaining it in detail would require quite a bit more space than a simple paragraph.

This solution utilizes the properties of self-similar fractal curves, recursion and string transformations. It’s also a great example of how sometimes an ostensibly straightforward brute-force approach can be smartly optimized by exploiting the structure of the problem.

More Answers: