プロジェクトオイラー 問６１

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問６１　「6つの巡回する4桁の図形数となる唯一の集合の和を求めよ」
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

三角数	P3,n=n(n+1)/2	1, 3, 6, 10, 15, ...
四角数	P4,n=n2	1, 4, 9, 16, 25, ...
五角数	P5,n=n(3n-1)/2	1, 5, 12, 22, 35, ...
六角数	P6,n=n(2n-1)	1, 6, 15, 28, 45, ...
七角数	P7,n=n(5n-3)/2	1, 7, 18, 34, 55, ...
八角数	P8,n=n(3n-2)	1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
2. それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
3. 4桁の数の組で上の2つの性質をもつはこの組だけである.

同じように, 6つの4桁の数からなる順番付きの集合で,

1. 集合は巡回的である
2. 三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる唯一の集合を求め, その和を求めよ.

－－－－－

注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下です。たたんでいます。

def p3(n): return n*(n+1)//2
def p4(n): return n*n
def p5(n): return n*(3*n-1)//2
def p6(n): return n*(2*n-1)
def p7(n): return n*(5*n-3)//2
def p8(n): return n*(3*n-2)

def h(f, a, b):
	m = __import__(__name__)
	L = []
	for i in xrange(b):
		s = getattr(m, f)(i)
		if a<=s<b: L.append(s)
		elif b<=s: break
	return L

def g(L, M=[], n=2):
	if len(L)<=len(M): return M
	for s in L[len(M)]:
		if M and str(M[-1])[-n:]!=str(s)[:n]: continue
		if len(L)-len(M)>1:
			M = g(L, M[:]+[s], n)
			if len(L)<=len(M): break
			if s==L[len(M)][-1]: break
		elif str(s)[-n:]==str(M[0])[:n]: return M+[s]	
	else:
		M.pop()
	return M

def f(a, b, n=4, m=2):
	import itertools
	P = [h("p"+str(i), 10**(n-1), 10**n) for i in xrange(a, b+1)]
	for t in itertools.permutations(xrange(b+1-a)):
		L = [P[int(i)] for i in t]
		M = g(L, n=m)
		if M: break
	return sum(M), M, [str(i+a)+"kakusu" for i in t]

if __name__=="__main__":
	s, M, t = f(a=3, b=8, n=4, m=2)
	print s, M
	print t

角数の関数６個と他３個の関数を使っています。

１．関数p3(n)～p8(n)
・三角数から八角数の定義式のとおりです。

２．関数h(f, a, b)
・当pythonソースファイル内の関数fにb未満の値を渡し、a以上b未満の戻り値のリストを返します。

・m = __import__(__name__)
　__import__関数は、指定したモジュールを実行時に動的にインポートする関数です。
　＿name__変数には、このプログラムのpythonソースのモジュール名（ファイル名の拡張子よりも前の部分）が設定されています。
　通常のimport関数はインポートするモジュール名を事前に固定文字列で指定しておきますが、自分のファイル自身をインポートする場合はファイル名変更しても影響を受けないように、動的にインポートします。
　後で関数を動的にインポートするための準備です。
　変数mには動的にインポートしたモジュールオブジェクトが設定されます。
　
・for i in xrange(b):
　ループ変数iは0以上b未満の範囲で1ずつ増加します。

・s = getattr(m, f)(i)
　getattr(m, f)関数は、モジュールmの関数fを呼び出します。
　変数iは関数fの引数です。
　当pythonソースファイル中の関数fに先ほどのループ変数iを渡し、その戻り値を変数sとします。

・if a<=s<b: L.append(s)
　elif b<=s: break
　上記の値sが、a以上b未満ならリストLに追加し、b以上なら終了します。

３．関数g(L, M=[], n=2)
・リストLは三角数などの角数リストが格納されたリストです。
　リストMはリストLの要素である角数リストを順にn桁で巡回的連結した値を格納したのリストです。
　リストLの全部の要素リストをn桁で巡回的連結した場合、その連結した値のリストを返します。

・if len(L)<=len(M): return M
　自分自身を呼び出す再帰関数なので、まず再帰呼び出し終了条件です。
　リストLの要素リストの個数以上に、順に巡回的連結した値の個数があれば順に巡回的に連結できた値のリストMを返し処理終了です。

・for s in L[len(M)]:
　len(M)は巡回的連結済みの個数であり、リストLのインデックス値としては次の巡回的連結要素を探すリストのインデックス値です。
　リストLから次に巡回的に連結する値を探す対象の角数リストを選び、ループ変数sとします。

・if M and str(M[-1])[-n:]!=str(s)[:n]: continue
　リストMに要素があり、その最後の要素がループ変数sにn桁で巡回的連結しなければsは対象外なので、次のループ変数sにループを進めます。
　リストMの最後の要素とループ変数sがn桁で巡回的連結している場合は以下の処理を続けます。

・if len(L)-len(M)>1:
　　M = g(L, M[:]+[s], n)
　　if len(L)<=len(M): break
　巡回的連結値の個数とリストLの要素数の差が1より大きい、つまり、リストLの最後までいっていない場合、さらに自分自身である関数g()を再帰呼び出しして、巡回的連結可能な値を探します。
　この再帰呼び出しのときの引数はリストLと巡回判定桁数nはそのままの値で、巡回的連結値リストMにはsを追加した状態で次を探します。
　再帰呼び出しから戻ってきたら、最初の行と同じ終了判定をします。

・elif str(s)[-n:]==str(M[0])[:n]: return M+[s]
　巡回的連結値の個数よりも、リストLの要素数が多くないということは、これらの個数が等しく、リストLの要素である角数リストすべてから巡回的連結値を探し出した状態なので、最後のチェックとして先頭要素との巡回的連結で連結の輪が閉じれるかを判定します。まだリストMに追加前のループ変数sからリストMの最後の要素にn桁で巡回的連結できればリストMが完成しこれを呼び出し元に返します。
　M+[s]は、リストMと要素sだけのリストの連結です。appendして返すことと同じです。

・else:
　M.pop()
　このelseはループ変数sのfor文のelseです。
　for文が途中でbreakせず、ループ変数の最後の要素まで処理し終った後に行う処理です。
　ここでは呼び出し元に返すこともなくfor文が終わったということなので、現在にリストMの最後の要素が巡回的連結先が無いことが確定しているので、このリストMの最後の要素をpop()関数で取り除きます。
　
・return M
　最後まで処理が来た場合は、リストMをそのまま返します。

４．f(a, b, n=4, m=2)
・n桁のa角数からb角数を１つずつ選びm桁で巡回的につながる組を返します。

・import itertools
　標準モジュールitertoolsを使えるようにしておきます。

・P = [h("p"+str(i), 10**(n-1), 10**n) for i in xrange(a, b+1)]
　リストPは、関数h()による角数リストをためたリストです。内包表記で書いています。
　for文でループ変数iにa以上b以下の整数を１つずつ設定します。
　ループ変数iは前に送られ、関数h()を呼び出しその戻り値を設定します。
　関数hの第１引数で、"p"+str(i)、つまり三角数などの関数、「p3」などを指定します。第２引数と第３引数で戻り値がn桁になるようします。例えばn=3の場合、100、1000を引き渡します。
　
・for t in itertools.permutations(xrange(b+1-a)):
　ループ変数tは、後ででてくるリストLのindex番号の組合せに使います。
　permutations()は順列を返す関数です。
　例えばrange(3)ならば、012, 021, 102, 120, 201, 210と順に返します。
　xrange(b+1-a)で、角数リストの個数分だけ0からの連番を発生させます。
　
・L = [P[int(i)] for i in t]
　上記tで先ほどのリストPの中を組み替えて、６つの角数リストを任意の順に組み替えます。
・M = g(L, n=m)
　if M: break
　関数g()を呼び出し、空のリスト（論理的にFalse)ならば、ループを続け次の
　順列の角数リストで巡回的連結可能な値を探しにいきます。

・return sum(M), M, [str(i+a)+"kakusu" for i in t]
　巡回的連結がした値の合計値、その値リスト、およびどの角数リストからとってきたかを呼び出し元に返します。

５．関数の外
・s, M, t = f(a=3, b=8, n=4, m=2)
　print s, M
　print t
　三角数から八角数まで各角数のうち4桁の値を１つずつ2桁で循環的連結できる値の和、そのときの値のリスト、どの角数リストからとってきたかのリストの３つを受け取り表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
28684 [8256, 5625, 2512, 1281, 8128, 2882]
['3kakusu', '4kakusu', '7kakusu', '8kakusu', '6kakusu', '5kakusu']

（追記）
・20130127　ネタバレ注意の追記など