Problem 61
三角数、四角数、五角数、六角数、七角数、ハ角数はいずれも多角数で、以下の公式で生成される。
（中略）3つの4桁の数、8128,2882,8281は、3つの興味深い性質を持つ。
1. そのセットは循環的、すなわち、各々のかずの最後の2桁が次の数の最初の2桁になっている（最後の数の次は最初の数）。
2. それぞれの多角数のタイプ：三角数（P3,127=8128）、四角数（P_{4,91}=8281）、五角数（P5,44=28）は、違う数によって表される。
3. これは、この性質を持つ4桁の数の唯一のセットである。
各々の多角数のタイプ：三角数、四角数、五角数、六角数、七角数、ハ角数がそのセットの違う数で表されるような6つの4桁の循環する数のセットの和を求めよ。
http://projecteuler.net/index.php?section=problems&id=61
このようなときはグラフを作ります。グラフというのは、物事を点と線とに置き換えたものです。8128 → 2882 → 8281 → 8128となっているので、例えば8128の次はと言われると2882が出てくるようなデータ構造を考えます。繋がっている数は2882以外にも2809や2850もあるので、リストにします。gを辞書として、
g[8228] = [ 2809, 2882, 2850, .. ]
実際のコードでは、n角数のnとタプルにしてグラフにします。
g[(8228,3)] = [(2809, 4), (2882, 5), (2850, 6), ... ]
このグラフを作って、三角数からはじめてちょうど7つ目で戻ってきてかつ角数がダブらないようなループを探します。
from itertools import count, takewhiledef gen_polygonal(p):
for n in count(1):
yield n * ( (p - 2) * n - p + 4) / 2def calc_polygonal():
a = [ ]
for p in range(3, 9):
a.extend(map(lambda n: (n, p), filter(lambda n: n > 1000,
takewhile(lambda n: n < 10000, gen_polygonal(p)))))
return adef make_graph(a):
b = [ [ ] for n in range(100) ]
for t in a:
b[t[0]/100].append(t)
g = { }
for e in a:
g[e] = filter(lambda t: t[1] != e[1], b[e[0]%100])
return gdef gen_loop(g, v0, n, v, flag = 0):
if n == 0:
if v == v0:
yield [ ]
elif (flag & (1 << v[1])) == 0:
flag |= 1 << v[1]
for v1 in filter(lambda v1: v1 != v, g[v]):
for path in gen_loop(g, v0, n - 1, v1, flag):
yield [ v ] + pathdef search_loop(g, n):
for v in filter(lambda v: v[1] == 3, g):
for a in gen_loop(g, v, n, v):
yield ag = make_graph(calc_polygonal())
for a in search_loop(g, 6):
print a
print sum(map(lambda e: e[0], a))
