Project Euler Problem 220

Solution

Answer: 139776963904

Let

• $A_n$ denote the expansion of symbol a after $n$ rewrites,
• $B_n$ denote the expansion of symbol b after $n$ rewrites.

The rewrite rules are

$$a \to aRbFR,\qquad b \to LFaLb$$

and the full dragon is

$$D_n = F A_n$$

because $D_0 = Fa$.

The crucial observation is:

• the number of forward moves doubles each generation,
• but the total string length grows exponentially,
• so we cannot generate $D_{50}$ explicitly.

Instead, we recursively compute:

1. the displacement vector of each block,
2. the direction change after executing it,
3. the number of forward steps inside it.

Then we “skip” entire recursive blocks whenever possible.

---

Mathematical analysis

We use directions

$$0=\text{up},\quad 1=\text{right},\quad 2=\text{down},\quad 3=\text{left}.$$

A forward move in direction $d$ is:

$$(0,1),(1,0),(0,-1),(-1,0).$$

For each recursive block we store:

$$(\Delta x,\Delta y,\Delta d,\text{steps})$$

meaning:

• net displacement,
• net rotation,
• number of F instructions.

---

Recursive structure

For $n\ge1$,

$$A_n = A_{n-1} ; R ; B_{n-1} ; F ; R$$

$$B_n = L ; F ; A_{n-1} ; L ; B_{n-1}$$

The symbols a,b themselves do nothing at level $0$, so

$$A_0=B_0=\varepsilon$$

with zero displacement and zero steps.

---

Number of forward steps

Let $f_n$ be the number of F commands in $A_n$.

From the recursion:

$$f_n=f_{n-1}+f_{n-1}+1$$

with $f_0=0$.

Thus

$$f_n = 2^n-1.$$

Therefore $D_{50}$ contains

$$1+(2^{50}-1)=2^{50}$$

forward steps, comfortably larger than $10^{12}$.

---

Efficient recursive skipping

Suppose we want the first $k$ steps inside $A_n$.

For each sub-block:

• if the whole sub-block contains $\le k$ steps, we skip it instantly using its precomputed displacement;
• otherwise we recurse into that block.

This gives complexity only $O(n)$.

---

Python implementation

from functools import lru_cache

# Rotate a vector clockwise by 90 degrees d times
def rotate(v, d):
    x, y = v
    for _ in range(d % 4):
        x, y = y, -x
    return x, y

# ------------------------------------------------------------
# Precompute properties of A_n and B_n
#
# Returns:
#   (dx, dy, dir_change, steps)
# ------------------------------------------------------------

@lru_cache(None)
def props(symbol, n):

    # Base case: a and b do nothing at level 0
    if n == 0:
        return (0, 0, 0, 0)

    if symbol == 'a':
        seq = ['a', 'R', 'b', 'F', 'R']
    else:
        seq = ['L', 'F', 'a', 'L', 'b']

    x = y = 0
    d = 0
    steps = 0

    for t in seq:

        if t in 'ab':

            dx, dy, dd, ss = props(t, n - 1)

            # Rotate displacement into current orientation
            rdx, rdy = rotate((dx, dy), d)

            x += rdx
            y += rdy

            d = (d + dd) % 4
            steps += ss

        elif t == 'F':

            move = [(0, 1), (1, 0), (0, -1), (-1, 0)][d]

            x += move[0]
            y += move[1]
            steps += 1

        elif t == 'L':
            d = (d - 1) % 4

        elif t == 'R':
            d = (d + 1) % 4

    return (x, y, d, steps)

# ------------------------------------------------------------
# Walk the first k forward steps inside symbol_n
# ------------------------------------------------------------

def walk(symbol, n, k, pos=(0, 0), direction=0):

    x, y = pos
    d = direction

    if n == 0 or k == 0:
        return (x, y, d, k)

    if symbol == 'a':
        seq = ['a', 'R', 'b', 'F', 'R']
    else:
        seq = ['L', 'F', 'a', 'L', 'b']

    for t in seq:

        if k == 0:
            break

        if t in 'ab':

            dx, dy, dd, ss = props(t, n - 1)

            # Skip whole block if possible
            if ss <= k:

                rdx, rdy = rotate((dx, dy), d)

                x += rdx
                y += rdy

                d = (d + dd) % 4
                k -= ss

            else:
                x, y, d, k = walk(t, n - 1, k, (x, y), d)

        elif t == 'F':

            move = [(0, 1), (1, 0), (0, -1), (-1, 0)][d]

            x += move[0]
            y += move[1]

            k -= 1

        elif t == 'L':
            d = (d - 1) % 4

        elif t == 'R':
            d = (d + 1) % 4

    return (x, y, d, k)

# ------------------------------------------------------------
# Full dragon D_n = F + A_n
# ------------------------------------------------------------

def solve(n, steps):

    # Initial instruction F
    x, y = (0, 1)
    steps -= 1

    if steps > 0:
        x, y, d, rem = walk('a', n, steps, (x, y), 0)

    return x, y

# ------------------------------------------------------------
# Verification against the example
# ------------------------------------------------------------

print(solve(10, 500))      # should be (18, 16)

# ------------------------------------------------------------
# Final answer
# ------------------------------------------------------------

print(solve(50, 10**12))

---

Code walkthrough

props(symbol, n)

This recursively computes the complete effect of $A_n$ or $B_n$:

• displacement,
• final direction,
• number of forward steps.

These values are memoized, so each state is computed once.

---

walk(symbol, n, k, ...)

This recursively executes only the first $k$ forward moves.

Key optimization:

if ss <= k:

means:

the entire recursive block fits inside the remaining budget,

so we skip it instantly.

Otherwise we recurse deeper.

---

solve(n, steps)

The dragon starts with an initial F, then executes $A_n$.

So we:

1. move once to $(0,1)$,
2. recursively process the remaining steps.

---

Verification

The problem states:

• in $D_{10}$,
• after $500$ steps,
• the cursor is at $(18,16)$.

Our code reproduces exactly:

$$(18,16)$$

which confirms correctness.

The final coordinates for $10^{12}$ steps are moderate in size (roughly on the scale of $\sqrt{10^{12}}=10^6$), which is consistent with the geometry of the Heighway dragon.

Therefore the result is:

Answer: 139776,963904