Project Euler 220

プロジェクトオイラー
http://projecteuler.net/index.php

Q220.
省略

まず、aを置き換えていったときと、bを置き換えていったときの位置とそこでの向きを計算する。aを置き換えていったものは、2のべきのステップ数進んだときの位置とそこでの向きになる。そのあとそうでないときに位置と向きを求める再帰関数を適切に書けばよいだけだが、これがなかなか。



def mul(x, y):
return (x[3] * y[0] + x[2] * y[1] + x[0],
x[3] * y[1] - x[2] * y[0] + x[1],
x[3] * y[2] + x[2] * y[3],
x[3] * y[3] - x[2] * y[2]
)

def mul_a(e1, e2):
return reduce(mul, (e1, R, e2, FR))

def mul_b(e1, e2):
return reduce(mul, (L, e1, L, e2))

def max_bit(n):
e = 1
while n > 1:
n >>= 1
e += 1
return e

def pow(n, e = -1):
if n == 0:
return E
if e == -1:
e = max_bit(n - 1)

e -= 1
if n == 2 ** (e + 1):
return D[e+1]
if n <= 2 ** e:
return pow(n, e)
else:
return reduce(mul, (D[e], R, pow_b(n - 2 ** e, e)))

def pow_b(n, e):
if n == 0:
return E

e -= 1
if n == 2 ** (e + 1):
return C[e+1]
if n <= 2 ** e:
return mul(L, pow(n, e))
else:
return reduce(mul, (L, D[e], L, pow_b(n - 2 ** e, e)))

N = 50
M = 10 ** 12
D = [ ]
C = [ ]
F = (0, 1, 0, 1)
R = (0, 0, 1, 0)
L = (0, 0, -1, 0)
E = (0, 0, 0, 1)
FR = mul(F, R)
LF = mul(L, F)
D.append(F)
C.append(E)
for n in range(N):
D.append(mul_a(D[n], C[n]))
C.append(mul_b(D[n], C[n]))
print pow(M)