- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 61. しりとり多角数
原文 Problem 61: Cyclical figurate numbers
**問題の要約：4桁の多角数（３・４・５・６・７・８角数）6種類が2つの数字のしりとりで循環するような集合の和を求めよ。
言葉で書くと分かりづらいですが、条件としては、
- 4桁の多角数6種類（３・４・５・６・７・８角数）の集合
- 6つの数は後ろ2桁と前2桁が等しい2桁しりとりの形になり巡回する
- 多角数6種類の順番は自由
以下が多角数3種類の例です。
8128（三角数）2882（五角数）8281（四角数）
まず2桁しりとりのチェックする関数isCytclic。
def isCyclic(n1, n2):
return str(n1)[-2:] == str(n2)[:2]
次に4桁の多角数6種類（３・４・５・６・７・８角数）をすべてリストします。
# Create a list of 4-digit poligon numbers
FigNums = [[pn for pn in [f(n) for n in range(1,1000)] if len(str(pn)) == 4] for f in funclist]
後は再帰呼び出しで2桁しりとりの数を異なる多角数から循環するまで探索します。
def findCyclic(foundList, remPolType): # FoundList, Remaining Pol Type e.g [0,1,2]
if len(foundList) == 6 and isCyclic(foundList[-1],foundList[0]):
return foundList+[0] # Answer found = len(foundList) == 7
for pt in remPolType:
for nextnum in FigNums[pt]:
if len(foundList) == 0 or isCyclic(foundList[-1],nextnum):
fl = findCyclic(foundList+[nextnum],remPolType-{pt}) # call findCyclic for remaining Pol Types
if len(fl) == 7: return fl
return foundList
remPol = set({0,1,2,3,4,5})
fl = findCyclic([],remPol)
print(f"Answer: {sum(fl)}, {fl[:-1]}")
（開発環境：Google Colab）