Project Euler 220

题目

Heighway Dragon

Let $\mathbf{D}0$ be the two-letter string “Fa”. For $n\ge1$, derive $\mathbf{D}_n$ from $\mathbf{D}{n-1}$ by the string-rewriting rules:

“a” → “aRbFR”
“b” → “LFaLb”

Thus, $\mathbf{D}_0$ = “Fa”, $\mathbf{D}_1$ = “FaRbFR”, $\mathbf{D}_2$ = “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 $\mathbf{D}n$ is an exotic drawing known as the Heighway Dragon of order $n$. For example, $\mathbf{D}{10}$ 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 $10^{12}$ steps in $D_{50}$ ?

Give your answer in the form $x,y$ with no spaces.

解决方案

令$N=10^{12}$。并假设机器人第$i$步走到的点为$(x_i,y_i)$。

令$a_0=\varnothing,b_0=\varnothing$，那么可以写出

$\begin{aligned}
an&\rightarrow a{n-1}Rb{n-1}FR\
b_n&\rightarrow LFa{n-1}Lb_{n-1}\
D_n&\rightarrow Fa_n
\end{aligned}$

令$Dn’\rightarrow b{n-1}F$，那么可以将$a_n,b_n$从这些规则中消去：

$\begin{aligned}
Dn&\rightarrow Fa_n\rightarrow Fa{n-1}Rb{n-1}FR\rightarrow D{n-1}RD{n-1}’R\
D_n’&\rightarrow b_nF\rightarrow LFa{n-1}Lb{n-1}F\rightarrow LD{n-1}LD_{n-1}’\
\end{aligned}$

最终这些规则可以写成：

$\begin{aligned}
D0&\rightarrow F\
D_0’&\rightarrow F\
D_n&\rightarrow D{n-1}RD{n-1}’R\
D_n’&\rightarrow LD{n-1}LD_{n-1}’\
\end{aligned}$

可以发现，$D_{n-1}$是$D_n$的前缀，那么实际上可以将$D$可以看成是一个无限字符串。并且，如果走完$D_n$或者是$D_n’$中的所有步骤，那么就相当于已经行走了$2^n$步。

考虑动态规划的思想，从原点开始，如果运行完$D_n$或者是$D_n’$中所有的指令后，当前机器人所处的位置和旋转的角度，用一个三元组$(x,y,d)$来表示。那么，就按照给定的规则，逐步递推到运行第$N$个$F$的地方。

另外，在该页面中查询到了这种龙形曲线的一些信息：在第$m$次迭代前，龙形曲线的最后一段端点在$(a{m-1},b{m-1})$处。那么，将整个龙形曲线逆时针旋转$90°$，原点$(0,0)$的位置将被旋转到$(am,b_m)$，旋转前和旋转后的曲线合并在一起就是第$n$轮的迭代结果。另外，$(a_0,b_0)=(0,1)$。并且，可以发现$(x{2^m},y_{2^m})=(a_m.b_m)$

这启发我们给出了寻找坐标点另一个更简单的算法：如果需要求第$n$次行走的结果，那么需要找到最小的整数$t$使得$2^t\ge n$，那么第$n$步的结果就相当于是将第$2^t-n$步的点$(x{2^t-n},y{2^t-n})$绕$(x{2^{t-1}},y{2^{t-1}})$点逆时针旋转$90°$得到。这相当于将问题转化成了两个子问题：找出点$(x{2^{t-1}},y{2^{t-1}})$点$(x{2^t-n},y{2^t-n})$的坐标。逐步递归即可得到最终答案。

代码

N = 10 ** 12


def f(now: tuple, *dir_list):
    x, y, d = now
    for dif in dir_list:
        if d == 0:
            x, y = x + dif[0], y + dif[1]
        elif d == 1:
            x, y = x - dif[1], y + dif[0]
        elif d == 2:
            x, y = x - dif[0], y - dif[1]
        else:
            x, y = x + dif[1], y - dif[0]
        d = (d + dif[2]) % 4
    return x, y, d


l = len(bin(N)) - 2
F, L, R = (0, 1, 0), (0, 0, 1), (0, 0, -1)
Da = [F]
Db = [F]
for i in range(1, l + 1):
    Da.append(f(Da[i - 1], R, Db[i - 1], R))
    Db.append(f(L, Da[i - 1], L, Db[i - 1]))
now = (0, 0, 0)
flag = 0
for i in range(l - 1, -1, -1):
    if flag == 0:
        if N >> i & 1:
            now = f(now, Da[i], R)
            flag = 1
        else:
            flag = 0
    else:
        now = f(now, L)
        if N >> i & 1:
            now = f(now, Da[i], L)
            flag = 1
        else:
            flag = 0
ans = ",".join(str(x) for x in now[:2])
print(ans)

N = 10 ** 12
mp = {0: (0, 0), 1: (0, 1)}


def cal(c, p):
    cx, cy = c
    px, py = p
    return cx - py + cy, cy + px - cx


def find(n):
    if n in mp.keys():
        return mp[n]
    pw = 1
    while pw < n:
        pw *= 2
    mp[n] = cal(find(pw // 2), find(pw - n))
    return mp[n]


ans = ",".join(str(x) for x in find(N))
print(ans)