Project Euler - Probrem 39

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

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

Problem 39
辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え, その周囲の長さをpとする.
p = 120のときには3つの解が存在する:
 {20,48,52}, {24,45,51}, {30,40,50}
p ≦ 1000 で解の数が最大になる p を求めよ.

－－－－－


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

def f(p):
	d = {}
	for i in xrange(1, p//3+1):
		for j in xrange(i, (p-i)//2+1):
			for k in xrange(j, p-i-j+1):
				if i*i+j*j==k*k:
					s = i+j+k
					d[s] = d.get(s, [])+[(i,j,k)]
	return d

p = 1000
d = f(p)
n = 0
for k, v in d.items():
	if len(v)>n: r, n, L = k, len(v), v
print r

１．関数f(p)
・周長がp以下で、各辺の長さが整数である直角三角形について、
　周長をキーに３辺の長さの組のリストを値とする辞書（連想配列）を返します。

・for i in xrange(1, p//3+1):
　ループ変数iは最短辺の長さです。
　値の範囲は、1以上で周長の1/3までの整数です。

・for j in xrange(i, (p-i)//2+1):
　ループ変数jは２番目の長さの辺の長さです。
　値の範囲は、最短辺長i以上で、最大周長pから最短辺長iを引いた残りの長さの半分以下です。

・for k in xrange(j, p-i-j+1):
　ループ変数kは最長辺の長さです。
　値の範囲は、第２辺長j以上で、最大周長pから他の２辺長を引いた残りです。

・if i*i+j*j==k*k:
　上記i,j,kが直角三角形を構成するかのチェックです。
　ピタゴラスの定理、そのままです。

・s = i+j+k
　d[s] = d.get(s, [])+[(i,j,k)]
　辞書dの周長sをキーとする値リストに３辺の組(i,j,k)を登録します。
　辞書dからキーsの値を取得するには、d[s]とd.get(s)の２つの方法があります。
　d[s]は、辞書dにキーsが存在しないときエラーになります。
　d.get(s,[])は、辞書dにキーsが存在しないとき、第２引数を返します。
　ここでは第２引数に初期値として空リスト[]を設定しています。
　そして３辺の組のタプル(i,j,k)を要素とするリストに追加していきます。

２．関数の外
・関数f()で問題に合う値の辞書が戻ってくるので、３辺の組の件数が最大のときの周長を求めます。

・for k, v in d.items():
　d.items()で、辞書dのキーと値を一緒に取り出し、それぞれk,vとします。

・if len(v)>n: r, n, L = k, len(v), v
　len(v)で値の件数を求め、今までの抽出値より大きければ、キー、件数、値（３辺の組のリスト）を、それぞれr,n,Lとして取り出しておきます。
　


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
840
8 [(40, 399, 401), (56, 390, 394), (105, 360, 375), (120, 350, 370), (140, 336,364), (168, 315, 357), (210, 280, 350), (240, 252, 348)