Project Euler 61

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

Q61.
8128 → 2882 → 8281 → 8128
みたいに2桁がしりとりになるように巡回して、6つで巡回、それが三角数から八角数の一つずつを取る、そのときの総和

あらかじめ多角数のリストを作ってから、有向グラフを作る。そして6つで戻ってくるルートを探し、三角数から八角数の一つずつを使っているかどうか調べる。



from math import sqrt

def is_square(n):
m = int(sqrt(n + 0.5))
return m * m == n

def is_polygonal(n):
for k in range(3, 9):
if is_polygonal_type(n, k):
return True
return False

def is_polygonal_type(n, k):
det = (k + 8 * (n - 1)) * k - 16 * (n - 1)
if is_square(det):
num = k - 4 + int(sqrt(det) + 0.5)
den = 2 * (k - 2)
if num % den == 0:
return True
return False

def get_type(p):
return filter(lambda k: is_polygonal_type(p, k), range(3, 9))

def is_connect(p, q):
return p % 100 == q / 100

def is_valid(n):
if n % 100 >= 10:
return is_polygonal(n)
else:
return False

def graph(poly):
g = { }
for p in poly:
g[p] = filter(lambda q: is_connect(p, q), poly)
return g

def gen(g, n):
if n == 1:
for p in g.keys():
yield [ p ]
else:
for l in gen(g, n - 1):
for p in g[l[n-2]]:
yield l + [ p ]

def is_loop(l):
return l[0] == l[len(l)-1]

def find(l, x):
i = 0
for a in l:
if a == x:
return i
i += 1
return -1

def gen_type(l, i):
if i == 0:
for k in l[i]:
yield [ k ]
else:
for k in l[i]:
for li in gen_type(l, i - 1):
if len(li) == 0:
break
if find(li, k) == -1:
yield li + [ k ]
yield [ ]

def is_each_type(l):
l = l[:-1]
t = [ get_type(p) for p in l ]
return len(gen_type(t, len(l) - 1).next()) > 0

def find_loop(g, n):
for l in gen(g, n):
if is_loop(l) and is_each_type(l):
return l[:-1]
return [ ]

N = 6
polygons = filter(is_valid, range(1000, 10000))
g = graph(polygons)
l = find_loop(g, N + 1)
print l
print sum(l)