再帰関数苦手です。混乱してしまいます。
もっとキレイにできると思うけど脳味噌が悲鳴をあげているので早々にギブアップ。
Problem 61 「巡回図形数」
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
$三角数 \quad P_{3,n}=n(n+1)/2 \hspace{30pt} 1, 3, 6, 10, 15, ...$
$四角数 \quad P_{4,n}=n^2 \hspace{67pt} 1, 4, 9, 16, 25, ...$
$五角数 \quad P_{5,n}=n(3n-1)/2 \hspace{25pt} 1, 5, 12, 22, 35, ...$
$六角数 \quad P_{6,n}=n(2n-1) \hspace{35pt} 1, 6, 15, 28, 45, ...$
$七角数 \quad P_{7,n}=n(5n-3)/2 \hspace{25pt} 1, 7, 18, 34, 55, ...$
$八角数 \quad P_{8,n}=n(3n-2) \hspace{35pt} 1, 8, 21, 40, 65, ...$
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 ($P_{3,127}=8128$), 四角数 ($P_{4,91}=8281$), 五角数 ($P_{5,44}=2882$) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.
from itertools import count, permutations
def hoge():
def find_chain(chain, i):
for x in p[perm[i]]:
if len(chain) == 6: return
if len(chain) != i+1: chain.pop() # 繋がらなかったとき
if x.startswith(chain[-1][-2:]):
chain.append(x)
if len(chain) < 6: find_chain(chain, i+1)
#
p = { n: P(n) for n in range(3, 9) }
for n in p[8]: # 個数の少ない8画数を起点に
for perm in permutations(range(3,8)): # 3~7角数の登場順
chain = [n]
find_chain(chain, 0)
if len(chain) == 6 and chain[0][:2] == chain[-1][-2:]:
#print(chain)
return sum(map(int, chain))
def P(n):
if n == 3: f = lambda n: (n * (n + 1)) // 2
elif n == 4: f = lambda n: n * n
elif n == 5: f = lambda n: (n * (3 * n - 1)) // 2
elif n == 6: f = lambda n: n * (2 * n - 1)
elif n == 7: f = lambda n: (n * (5 * n - 3)) // 2
elif n == 8: f = lambda n: n * (3 * n - 2)
l = []
for m in count(1):
x = f(m)
if 1000 <= x < 10000:
l.append(str(x))
elif x >= 10000:
return l
print(hoge())