Project Euler 208

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

Q208.
ロボットはランダムに移動する。ただし、ある一定の半径の円弧を描いて72度分動く。70回動いて元に戻るルートはいくつかるか。

位置と向きは、整係数で4次元で表される。あとは一歩ずつ進んで、状態と個数を記録していく。
バイナリ法的にしたほうが速いような気もするが、ちょっと気力がない。

import time
def add(t1, t2):

    return (t1[0] + t2[0], t1[1] + t2[1], t1[2] + t2[2], t1[3] + t2[3])
def subtract(t1, t2):

    return (t1[0] - t2[0], t1[1] - t2[1], t1[2] - t2[2], t1[3] - t2[3])
def minus(t):

    return (-t[0], -t[1], -t[2], -t[3])
def add_item(a, e, n):

    if e in a:

        a[e] += n

    else:

        a[e] = n
t1 = time.clock()

v = [ (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1) ]

v.append(minus(reduce(add, v)))

for i in range(5):

    v.append(minus(v[i]))
c2c  = [ ( (i + 1) % 5,      i + 10 ) for i in range(5) ]

c2c += [ ( (i + 1) % 5 + 5,  i + 15 ) for i in range(5) ]

c2c += [ ( (i + 4) % 5 + 10, i      ) for i in range(5) ]

c2c += [ ( (i + 4) % 5 + 15, i + 5  ) for i in range(5) ]
N = 70

a = { ( (0, 0, 0, 0), 4 ): 1 }

for i in range(N):

    b = { }

    for t, n in a.iteritems():

        pt0, k0 = t

        for k1 in c2c[k0]:

            v1 = v[k1%10]

            pt1 = add(pt0, v1)

            add_item(b, (pt1, k1), n)

    a = b
s = 0

for t, n in a.iteritems():

    if t[0] == (0, 0, 0, 0):

        s += n

print s

print time.clock() - t1