2015年1月18日日曜日

プロジェクトオイラー 問105

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問105「特殊和集合:検査」
大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう.

i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない.
ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.

たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は, 
65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが, 
{157, 150, 164, 119, 79, 159, 161, 139, 158} は
すべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また S(A) = 1286 である.

7個 から 12個 の要素を含む 100 個の集合が記された 4K のテキストファイル sets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合 A1, A2, ... , Ak をすべて特定し, S(A1) + S(A2) + ... + S(Ak) を求めよ.


注意: この問題は Problem 103 と 106 に関連している.





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






私の回答例は以下の通りです。
def chk1(L):
	import itertools
	M = []
	for i in xrange(len(L)):
		for j in itertools.combinations(L, i+1):
			s = sum(j)
			if s in M: return False
			M.append(s)
	return True

def chk2(L):
	a, b = (len(L)+1)//2, len(L)//2+1
	return sum(L[:a])>sum(L[b:])

def f(fn):
	c, s = 0, 0
	p = open(fn)
	for t in p.readlines():
		L = sorted([int(u) for u in t.split(",")])
		if chk1(L) and chk2(L): s += sum(L); c += 1
	p.close()
	p = None
	return s, c

t = os.path.join(os.path.dirname(__file__), "p105_sets.txt")
s, c = f(t)
print "sum  :", s
print "count:", c





問題文にあるとおり、問103の関連問題です。
特殊和集合のチェックは既に問103でやっているので、そのまま流用しました。

1.関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
 i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
 を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問103を参照。

2.関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
 ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
 を満たしていればTrue、満たしていなければFalseを返します。
・詳細は問103を参照。

3.関数f(fn)
・入力ファイルのフルパスを受け取り、特殊和集合の合計値と個数を返します。
・入力ファイルを1行ずつ読み込み、カンマで分けて数値型の要素にして昇順に並べたリストLについて、特殊和集合の条件2つが成り立てば、変数cにためていきます。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum  : 73702
count: 28

0 件のコメント:

コメントを投稿