Project Euler - Probrem 38

Project Euler(プロジェクト　オイラー）の問題をpythonでやってみます。

出典： Project Euler（日本語 翻訳サイト）
　　　 ProjectEuler.net（英語サイト）

Problem 38
192に1, 2, 3を掛けてみよう.
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
積を連結することで1から9の全ての数字で構成される数、Pandigital数 192384576 が得られる.
192384576を 192と(1,2,3)の連結積と呼ぶ.

同じようにして, 9を1,2,3,4,5と掛け連結することでPandigital数918273645が得られる.
これは9と(1,2,3,4,5)との連結積である.

整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ.

－－－－－


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

def f(n):
	N = set([str(i) for i in xrange(1, n+1)])
	L = []
	for i in xrange(1, 10**(n//2)):
		for j in xrange(1, n//len(str(i))+1):
			t = "".join([str(i*k) for k in xrange(1, j+1)])
			if len(t)==n and set(t)==N: L.append((i, j, int(t)))
	return L

L = f(9)
m = max([s[2] for s in L])
print m
for s in L:
	if s[2]==m:
		print [str(s[0])+"x"+str(i)+"="+str(s[0]*i) for i in xrange(1,s[1]+1)]

１．関数f(n)
・1～nまでの数字を使ったpandigital数のリストを返します。

・N = set([str(i) for i in xrange(1, n+1)])
　1からnまでの数字を1つずつ文字型に変換したリストを、さらに集合型に変換しておきます。後で候補値による集合と比較します。

・for i in xrange(1, 10**(n//2)):
　ループ変数iは連結積の左側部分の数字候補です。
　問題文からpandigital数x1だけはダメで、最低でも2つの数字の連結が必要なことから、対象となる数字の桁数は桁数nの半分以下となります。
　そのため、最大値は10のn//2乗です。//演算子は割り算の商の整数部分です。

・for j in xrange(1, n//len(str(i))+1):
　ループ変数jは連結積の右側部分の数字です。
　jの最大値の数の分だけ掛け算結果を連結することになるので、
　桁数nを連結積左側部分iの桁数で割った商が、その最大値になります。

・t = "".join([str(i*k) for k in xrange(1, j+1)])
　iと(1～j)との連結積を返します。
　内包表記を使っています。
　まず、1からjの連番を1つずつループ変数kとし、forの前に渡し、iとkの積を計算し、連結するのでstr関数で数字型から文字型に変えてリストにためます。
　そのリストを区切り文字無しで連結しtとします。

・if len(t)==n and set(t)==N: L.append((i, j, int(t)))
　上記の計算値tがpandigital数か判定します。
　長さがn桁であり、かつ構成要素が1からnまでの数字かを判定します。
　set関数で文字列tの構成要素を集合型にすることで、重複文字を削除し集合Nと一致するか判定します。
　条件に合えば、そのときのi,j,tのタプルをリストLにためます。

２．関数の外
・関数f()で問題に合う値のリストが戻ってくるので、max関数でその最大値を求めます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
932718654
['9327x1=9327', '9327x2=18654']