2012年8月17日金曜日

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)]


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にためます。

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

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

0 件のコメント:

コメントを投稿