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

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

問６２　「立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ」
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる:
56623104 (3843) と 66430125 (4053) である.
41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.

－－－－－





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





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

def f(n):
	j = 0
	while True:
		j += 1
		L = [i*i*i for i in xrange(10**j)]
		M = [[str(s).count(str(t)) for t in xrange(10)] for s in L]
		for s in M:
			t = M.count(s)
			if t>=n:
				P = [i for i, u in enumerate(M) if s==u]
				N = [L[i] for i in P]
				return N[0], N, P

n = 5
print f(n)

最初は立方数の１つひとつの順列を作り、それが立方数かチェックしようとしましたが、１分では処理が終わりません。
そこで、立方数の１つひとつを構成する数字別個数リストを作って、同じリストになるものの数が指定個数になるかチェックするようにしました。

関数を１つ使っています。

１．関数f(n)
・j = 0
　変数jは10の累乗ごとに区切ってチェックするのでその累乗値カウンタです。初期クリアします。

・while True:
　無限ループです。

・j += 1
　累乗カウントをカウントアップします。

・L = [i*i*i for i in xrange(10**j)]
　Lは立方数リストです。10**jは10のj乗で、0からこの値までを１区切りにして処理を続けます。

・M = [[str(s).count(str(t)) for t in xrange(10)] for s in L]
　Mは数字別個数リストのリストです。二重の内包表記です。
　まず外側の内包表記の「for s in L」で先ほどの立方数リストLから１つずつ取り出しfor文の前の内側の内包表記に渡します。
　次に内側の内包表記の「for t in xrange(10)」で、ループ変数tに0以上10未満の整数が１つずつ設定されfor文の前に渡されます。
　「str(s).count(str(t))」で、立方数sに含まれる0以上10未満のいずれかのtの個数を数えます。
　例えば、s=1006012008の場合、内側の内包表記は[5,2,1,0,0,0,1,0,1,0]です。
　このような内側の内包表記が数字別個数リストで、外側の内包表記でそれをさらにリストにためています。

・for s in M:
　Mは数字別個数リストのリストから１つずつ取り出した数字別個数リストをループ変数sに設定します。

・t = M.count(s)
　リストMにある、ループ変数sの数字別個数リストと同じものの件数を数えtとします。

・if t>=n:
　上記tが指定個数n以上ならば、問題に合います。

・P = [i for i, u in enumerate(M) if s==u]
　Pは問題にあう立方数の元の数のリストです。
　enumerate関数で0からの連番を発生させます。このインデックス値が立方数の元の数です。

・N = [L[i] for i in P]
　リストPの値をインデックス値に立方数リストLから値を集め、リストNとします。

・return N[0], N, P
　問題に合う最小の立方数、桁を置換した立方数のリスト、その元の数のリストの３つを呼び出し元に返します。
　
２．関数の外
・n = 5
　print f(n)
　問題に合うように指定個数を5個として関数fで関連情報リストも含めて取得し、表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。(127035954683L,
[127035954683L, 352045367981L, 373559126408L, 569310543872L, 589323567104L],
[5027, 7061, 7202, 8288, 8384])
（追記）
・20130127　ネタバレ注意の追記など

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

プロジェクトオイラーの問題を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　ネタバレ注意の追記など

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

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

問６０　「任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組を求めよ」
素数3, 7, 109, 673は非凡な性質を持っている.
任意の2つの素数を任意の順で繋げると, また素数になっている.
例えば, 7と109を用いると, 7109と1097の両方が素数である.
これら4つの素数の和は792である.
れは, このような性質をもつ4つの素数の組の和の中で最小である.

任意の2つの素数を繋げたときに別の素数が生成される, 5つの素数の組の和の中で最小のものを求めよ.

－－－－－

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





最初にコーディングしたときにfor文の五重ループになってしまったので、どうしても再帰関数に改良したかったことと、処理速度の向上とで、１ヶ月近くかかってしまいました。
上限値を設けてやっと１分ルールを満たしているので、まだまだロジックが甘いのですが、行き詰まってしまったこともあり、現在のプログラムのまま提示しておきます。
答えは合っていますが、問題では「最小のもの」を求めるところ、題意を満たす「最初のもの」を求めるプログラムです。

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

def h(n):
	if n==2: return True
	if n<2 or (not n%2): return False
	for i in xrange(3, n, 2):
		if i*i>n: break
		if not n%i: return False
	return True

def e(n):
	i = n+1+int(n%2)
	while not h(i): i += 2
	return i

def g(L, t):
	t = str(t)
	for s in L:
		s = str(s)
		if not h(int(s+t)): return False
		if not h(int(t+s)): return False
	return True

def f(n, L=[], p=0):
	if len(L)>=n: return L
	while p<10**(n-1):
		p = e(p)
		if g(L, p):
			L = f(n, L+[p], p)
			if len(L)>=n: break
	else:
		L.pop()
	return L

n = 5
s = f(n)
print sum(s), s

４つの関数を使っています。

１．関数h(n)
・素数判定です。問５８で作成したものを流用しました。
　素数ならTrue、素数でなければFalseを返します。

２．関数e(n)
・引数を超える最小の素数を返します。n>1のとき有効です。

・i = n+1+int(n%2)
　変数iが素数候補です。
　%演算子は割り算の余りです。割り切れれば0、割り切れないと1なので、
　式全体では偶数なら1足し、奇数なら2足すことになります。
　後続処理の準備として、素数候補iを奇数にしておきます。

・while not h(i): i += 2
　関数h()で素数判定をして、素数でなければ2ずつ増やしてチェックします。
　前準備でこの処理にくるときには素数候補iは奇数にしているので、
　iが偶数で無限ループになることはありません。

・return i
　ここまでの処理でnを超える最初の素数としてiを返却します。

３．関数g(L, t)
・引数リストLの各要素と引数tを任意の順に２つ連結した値が、すべて素数かどうかを判定します。

・t = str(t)
　後で連結するので、引数tを文字型にします。

・for s in L:
　引数リストLから順にループ変数sに設定します。

・s = str(s)
　後で連結するので、ループ変数sを文字型にします。

・if not h(int(s+t)): return False
　if not h(int(t+s)): return False
　上記の文字列sと文字列tを前後とその入れ替えの２パターンで連結し、
　int関数で数値化して、関数hで素数判定します。
　素数でなければ即終了でFalseを返します。

・return True
　引数リストLと引数tでここまでで処理を抜けていなければ、そのすべての組合せが素数なので、Trueを返します。

４．関数f(n, L=[], p=0)
・問題に合う値のリストを返します。
　自分で自分を呼び出す記述のある再帰関数です。
　引数nは求める素数の個数です。
　引数Lは素数を格納するリストで初期値は空リストです。
　引数pは最後にチェックした素数で、初期値は0とします。

・if len(L)>=n: return L
　再帰関数の終了条件です。
　リストLに求める個数n個以上の要素がたまったら処理終了で、リストLを返します。

・while p<10**(n-1):
　対象とする素数が青天井では処理が終わらないので、とりあえず求める素数の個数分の桁数、10**(n-1)、未満の素数で、処理することにしました。
　求める素数が２個なら10以内の素数の組で最小組[3,7]が見つかり、
　同じく３個なら100以内の素数の組で最小組[3, 37, 67]が見つかり、
　同じく４個なら問題文にあるように1000以内の素数の組が見つかります。

・p = e(p)
　得られている最後の素数pを関数eで処理し、次に大きい素数を改めてpとします。

・if g(L, p):
　関数gで引数リストLの各要素と引数pを任意の順に２つ連結した値が、すべて素数かどうかを判定します。Falseの場合はwhileループの次の値へ進みます。

・L = f(n, L+[p], p)
　１つ前の関数g()ですべて素数の場合、次に大きい素数pを候補として、さらに題意にある素数を探して追加するため、当関数f()を再帰呼び出しします。
　なお、第２引数の「L+[p]」は、再帰呼び出しで引数Lで受けるので、お試しでリストLの末尾に追加することになります。

・if len(L)>=n: break
　再帰呼び出しから戻り、リストLの要素数がn以上ならば探索終了でwhileループから抜けます。

・else:
 L.pop()
　このelse節はインデント（行頭のずらし位置）から明らかなように、for文のelseです。直前のif文のelse節ではありません。
　for文のelse節の処理タイミングは、forループの最後の値まで処理が行われた場合のループ終了直後です。
　ここまでの処理でbreakで抜けない場合、再帰呼び出しの際にお試しで追加したpが求める値ではないということになります。
　このため、関数pop()で末尾の要素を削除しておきます。

・return L
　処理の最後にリストLを呼び出し元に戻します。

５．関数の外
・n = 5
　s = f(n)
　print sum(s), s
　問題に合うように引数の値を5として関数f()を呼び出します。
　返されたリストをsとして、そのリスト要素合計、及び参考としてリスト要素を表示します。


　
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
26033 [13, 5197, 5701, 6733, 8389]

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