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

2015年1月12日月曜日

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

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

問104「両端がパンデジタルなフィボナッチ数」
フィボナッチ数列は再帰的な関係によって定義される:

Fn = Fn-1 + Fn-2
F541 (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. 
そして, F2749 (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

Fkが, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき, kを求めよ.






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






私の回答例は以下の通りです。
<pre class="brush:python;collapse:true" title="問104">
def f(s):
pl, ps = len(s), sorted(s)
a, b, c, d, k, g, n = 1, 0, 1, 0, 1, 0, pl*2
while sorted(str(a)[:pl])!=ps or sorted(str(c)[-pl:])!=ps:
a, b, c, d, k, m = a+b, a, c+d, c, k+1, len(str(a))-n
if pl<m:
u, v = 10**m, 10**n
a, b, c, d, g = a//u, b//u, c%v, d%v, g+m
g += len(str(a))
return k, g

P = "123456789"
k, t = f(P)
print "k    :", k
print "digit:", t
</pre>

問題のまま実装すると、数千桁から数万桁の数値の加算に処理時間がかかり、とても1分では終わりません。
フィボナッチ数の先頭と末尾それぞれの必要な桁数分だけ桁調整して計算します。
なお、桁調整の際に必要な桁を超える桁数は累積しておき、後で全体桁数を把握できるようにします。

1.関数f(s)
・文字列sに含まれる文字が先頭と末尾に順不同で存在するフィボナッチ数での項番と桁数を返します。
・変数plは文字列sの文字列長、変数psは文字列sを1文字ずつ昇順に並べた要素として持つリストです。
・kはフィボナッチ数の項番、
 aはフィボナッチ数Fkの上から必要な桁数分、bはフィボナッチ数Fk-1の上から必要な桁数分、
 cはフィボナッチ数Fkの下から必要な桁数分、dはフィボナッチ数Fn-1の下から必要な桁数分、
 gはフィボナッチ数Fkの桁数です。
・変数nは本問の計算に必要な桁数です。
 大きな値にすると加算処理に時間がかかるので必要な桁数以上でなるべく小さな値とします。
 題意にあう必要なチェックをするために少なくとも引数sの文字数分は必要で、また加算の繰り上がりの影響を吸収するためにさらに引数sの文字数分を考慮しておきます。合わせて、計算に必要な桁数nは、引数sの2倍の値とします。

・whileループ内でのフィボナッチ数計算の継続チェックは以下の通りです。
 先頭と末尾を引数と同じ桁数だけ取り出して昇順に並べて、事前に用意した変数psと比較し、どちらかが不一致ならば処理を継続します。

・whileループ内ではフィボナッチ数の計算をします。
 フィボナッチ数Fk、Fk-1の先頭部分a,bにそれぞれa+b、aを設定します。
 フィボナッチ数Fk、Fk-1の末尾部分c,dにそれぞれc+d、cを設定します。
 項番kを1つ進めます。
 変数mは先頭部分から桁調整で減らす桁数で、フィボナッチ数の先頭部分の計算結果の桁数と計算に必要な桁数nの差です。

・変数mはすぐに正の値になりますが、あまり頻繁に桁調整しなくても処理速度に影響ないので、mがplより大きい場合、先頭と末尾両方の桁調整を行います。
 変数uは先頭部分の末尾から減らす桁数分の10の累乗値で、フィボナッチ数Fk、Fk-1それぞれの先頭部分a,bをuで割った商を新たにa,bとします。
 変数vは末尾部分の先頭から減らす桁数分の10の累乗値で、フィボナッチ数Fk、Fk-1それぞれの末尾部分c,dをvで割った余りを新たにc,dとします。
 桁数gには調整して減らした桁数mを累積していきます。

・フィボナッチ数の計算が終わりwhileループ終了後に、桁数gにはフィボナッチ数の先頭部分aの桁数を足して、全体桁数にしておきます。
 なお、計算中に桁調整をしていなければ変数aはフィボナッチ数そのものです。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
k    : 329468
digit: 68855

2015年1月11日日曜日

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

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

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

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

ある n に対し S(A) が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

ある最適集合 A = {a1, a2, ... , an} に対し, 次の最適集合は B = {b, a1+b, a2+b, ... ,an+b} となりそうである. ここで b は前列の「中央の」要素である.

この「法則」を用いると n = 6 に対する最適集合は A = {11, 17, 20, 22, 23, 24} で, S(A) = 117 と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適集合とはならない. n = 6 に対する最適集合は A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である. これに対応する集合の文字列は 111819202225 である.

A を n = 7 に対する最適特殊集合とするとき, その集合の文字列を求めよ.

注意: この問題は Problem 105 と 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 g(L):
	if not L: return [1]
	c = L[(len(L)-1)//2]
	for b in xrange(c, c+L[-1]):
		M = [a+b for a in [0]+L]
		if chk1(M) and chk2(M): return M

def f(n):
	M = []
	for i in xrange(n):
		M, N, k = g(M), [[]], i//2
		for j in M:
			L = xrange(max(1, j-k), j+k+1)
			N = [s+[t] for s in N for t in L if (not s) or s[-1]<t]
		for L in N:
			if sum(L)<sum(M) and chk1(L) and chk2(L): M = L
	return "".join([str(s) for s in M]), sum(M)

n = 7
t, s = f(n)
print "str:", t
print "sum:", s




ゼロベースで最適特殊集合を作り出そうとするととても1分で処理が終わりません。
「最適に近い集合」が提示されているので、まずこれを基に各要素ごとにいくらかの幅を設定して候補値を選定します。
そしてこの「各要素ごとの候補値の組合せ」から最適特殊解集合を求めることにしました。

1.関数chk1(L)
・リストLが最適特殊和集合の以下の条件、
 i. S(B) ≠ S(C); つまり, 部分集合の和が等しくてはならない.
 を満たしていればTrue、満たしていなければFalseを返します。
・リストLの部分集合の和を作成し、リストMに無ければためていき、あればFlseで終了します。
・ループ変数iは、リストLから部分集合を作る際に取り出す要素数(0~)です。
・ループ変数jは、組み合わせ関数combinationsを利用して、
 リストLからi+1個の要素を取り出した組み合わせ結果のタプルが設定されます。

2.関数chk2(L)
・リストLが最適特殊和集合の以下の条件、
 ii. B が C より多くの要素を含んでいればこのとき S(B) > S(C) となる.
 を満たしていればTrue、満たしていなければFalseを返します。
・この条件を満たすかどうかが一番厳しい部分集合の和同士でチェックします。
・一番厳しい部分集合の和同士は、要素を昇順に並べた集合の中で、
 要素が奇数個の場合、最小値から中央値までの和とそれより後の和同士、
 つまり{1,2,3,4,5}ならば、{1,2,3}と{4,5}の和を比較(この場合False)します。
 要素が偶数個の場合、集合の前半の和と後半の2番目に小さい値以降の和同士、
 つまり{1,2,3,4,5,6}ならば、{1,2,3}と{5,6}の和を比較(この場合False)します。
 
3.関数g(L)
・リストLの次の「最適に近い集合」のリストを返します。
・次の「最適に近い集合」は、問題にあるロジックの通り、中央値と中央値を全要素に足した集合です。
・Lが空集合の場合、要素が1だけのリストを返却します。

4.関数f(n)
・要素数がn個の最適特殊集合の要素連結文字列と和を返します。
・既知の最適特殊集合に基づいて要素数が1つ多い最適特殊集合をもとめていきます。
 要素数が1個から始めてn個になるまで順に最適特殊集合を求めていきます。

・リストMは既知の最適特殊集合で、関数gにより次の「最適に近い集合」を設定します。
・ループ変数iはリストMの要素数です。

・ループ変数jは最適に近い値を1つずつ設定します。
・変数kは候補値の幅です。ここでは「最適に近い集合」の要素数の半分とします。
 要素数が4や5ならば各要素の±2に含まれる値を各要素の候補値とします。
 jのループ中で、各要素ごとの候補値リストLとして持ちます。
・リストNは各要素の候補値の組合せリストです。なお昇順になる組合せのみ採用します。

・候補値組合せリストNのループ内で、リストNの中から最適特殊集合を求めます。
・「最適に近い集合」Mよりも和が小さいこと、最適特殊集合の条件2つに合うかチェックし、最適特殊集合として採用します。
 チェックして合うものが無ければ、「最適に近い集合」Mを最適特殊集合とします。



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

2015年1月3日土曜日

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

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

問102「三角形の包含」
3つの異なる点が -1000 ≦ x, y ≦ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.

以下の2つの三角形を考える.

A(-340,495), B(-153,-910), C(835,-947) 
X(-175,41), Y(-421,-714), Z(574,-645)
三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.

27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.

注: ファイル中の最初の二つは三角形ABC, XYZである.






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






私の回答例は以下の通りです。
def f(fn):
	c = 0
	p = open(fn)
	for s in p.readlines():
		t, L, M = s.split(","), [], []
		for i in xrange(0, len(t), 2): L.append((int(t[i]), int(t[i+1]))) 
		L.append(L[0])
		for i in xrange(len(t)//2):
			a, b = L[i], (L[i+1][0]-L[i][0], L[i+1][1]-L[i][1])
			M.append(a[0]*b[1] - a[1]*b[0])
		if abs(sum(M))==sum([abs(u) for u in M]): c += 1
	p.close()
	p = None
	return c

s = "p102_triangles.txt"
t = os.path.join(os.path.dirname(__file__), s)
print f(t)



原点が三角形の各辺の左右同じ側にあるかという位置関係で判定します。
ベクトルの外積を利用します。

対象となる点(当問題では原点)が三角形の内部にあれば、
その点は三角形を一周して常に同じ側にあることになります。
つまり、対象となる点(当問題では原点)から各頂点へのベクトルと、
その頂点から次の頂点へのベクトルの外積の符号がすべて同じになります。
なお、平面上の話なので、外積はベクトルにならずスカラー量です。

aベクトル:原点から三角形のi番目の頂点へのベクトル
bベクトル:i番目の点からi+1番目の点へのベクトル
として、
aベクトルとbベクトルの外積の符号が、
正ならばaベクトルが右側、つまり原点はbベクトルの左側で、
負ならばaベクトルが左側、つまり原点はbベクトルの右側です。
3つの外積がすべて正ならば原点を右回りに一周し、
3つの外積がすべて負ならば原点を左回りに一周することになります。

外積の公式は以下のとおりです。
aベクトル=(Ax, Ay)、bベクトル=(Bx, By)とすると、
a×b = Ax*By - Ay*Bx

以上を実装しました。

1.関数f(fn)
・入力ファイルのフルパスを受け取り、問題にある内部に原点を含む三角形の数を返します。
・ループ変数sは、入力ファイルの1行分で、6つの数字のcsv文字列です。
・変数tは、6つの数字(まだ文字型)を持つリストです。
・一周して計算する都合上、最初の座標を最後にもう一度追加し
座標を4つ分にしてから外積計算を3回行います。
リストLは、平面座標値(タプル型)を最初3つ持ち、最初の1つを末尾に追加して
計4つの座標値を持ちます。
・変数a,bはそれぞれ上記の説明にあるaベクトルとbベクトルです。
・リストMには外積値をためていきます。
・外積の符号一致判定は、外積値の和の絶対値=外積値の絶対値の和かどうかで行います。



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

2015年1月1日木曜日

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

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

問101「最適多項式」
数列のk個の項を与えられたときに, 次の項を確実に求めることは不可能である. 
その数列に合うような多項式が無限個存在するからである.

例として, 立方数の数列を考えよう. これは生成関数 un = n3 で定義され, 1, 8, 27, 64, 125, 216, ...となる.

この数列の最初の2項のみが与えられているとしよう. 
"Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する.

数列の最初のk項を生成できる最適な多項式のn項を OP(k, n) で表すことにする. 
明らかに, n ≦ k について OP(k, n) は正しい. 
最初の異なる項 (First Incorrect Term, FIT) は OP(k, k+1) であろう. 
これを bad OP (BOP) と呼ぶことにする.

原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう;即ち, n ≧ 2, OP(1, n) = u1.

従って, 立方数の数列について以下のOPを得る.

OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n2−11n+6      1, 8, 27, 58, ...
OP(4, n) = n3 1, 8, 27, 64, 125, ...

明らかに, k ≧ 4 のときにはBOPは存在しない.
BOPのFIT (上の例ではで示されている) の和は, 1 + 15 + 58 = 74 である.

以下の10次多項式からなる生成関数を考える:
un = 1 - n + n2 - n3 + n4 - n5 + n6 - n7 + n8 - n9 + n10
BOPのFITの総和を求めよ.






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






私の回答例は以下の通りです。
def g(Y):
	x, y = len(Y), 0
	Xi = [i for i in xrange(x)]
	for i in xrange(x):
		a, b = Y[i], 1
		for j in xrange(x):
			if i==j: continue
			a *= (x - Xi[j])
			b *= (Xi[i] - Xi[j])
		y += a//b
	return y

def f(s):
	L, FIT, BOP, t, n = [], 0, 0, -1, 0
	while FIT!=t:
		BOP += FIT
		n += 1
		FIT, t = g(L), eval(s)
		L.append(t)
	return BOP

u = "1 - n + n**2 - n**3 + n**4 - n**5 + n**6 - n**7 + n**8 - n**9 + n**10"
BOP = f(u)
print "BOP:", BOP



この問題は解法が思いつかず、ネット検索したところ、「ラグランジュの補間多項式」の問題と判明。
ラグランジュ補間(wiki) を参考にロジックを組みました。

1.関数g(Y)
・ラグランジュの補間多項式を組み込んだ関数です。
 数値リストYから要素数より1つ少ない次元の補間多項式による、次の要素を返します。
・数値xはリストYの要素数で、求める要素の要素番号です。
 リストXiは、リストYの要素番号のリストです。
・ループ変数iは補間式内の項の番号です。
 ループ変数jは補間式の各項内の掛け算要素の番号です。
・変数a, bは、その掛け算要素の分子と分母です。
 項1つ分の分子と分母の計算が終わったら、その商を変数yに累積していきます。

2.関数f(s)
・文字型で数式を受取り、問題文にあるBOPのFITの総和を返します。
 数式の変数は1種類、nだけとします。
・リストLは、受け取り数式sによる実値をためていきます。
・whileループ内は、現在までの実値リストに基づく推定値FITと
 数式による実値tとが不一致の間、処理を実行します。
 また、初回n=1のときは一致することがあるので、実値リストLがカラのときは処理を行うようにします。
・受け取り数式sの変数nに1から順に値を代入していき、関数g()を使って推定値FITを求めます。
 文字列である数式をeval関数で処理する数式として認識させ実行します。



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