2013年8月25日日曜日

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

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

問81「経路の和:2方向」

下記の5次の正方行列で, 左上のセルから開始し右下のセルで終わるパスを探索する. 
ただし下方向と右方向にのみ移動できるものとする. 
通過したセルの和が最小となるパスは赤の太字で示されたもので, その値は2427である.

131 673 234 103 18 
201 96 342 965 150 
630 803 746 422 111 
537 699 497 121 956 
805 732 524 37 331 

今, 31Kのテキストファイルmatrix.txt (右クリックして, 『名前をつけてリンク先を保存』)には80×80の行列が書かれている. 
同様に左上のセルから開始し右下のセルで終わり, かつ右方向と下方向にのみ移動するときの最小のパスの和を求めよ.



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






私の回答例は以下の通りです。

def f(fn): import sys, copy L0 = open(fn).read().split("\n") L1 = [s.split(",") for s in L0 if s] tn, yn = len(L1), len(L1[0]) L2 = [[int(t) for t in s]+[sys.maxint] for s in L1]+[[sys.maxint]*yn] L3 = copy.deepcopy(L2) L4 = [["" for i in xrange(yn)] for j in xrange(tn)] for i in range(tn)[::-1]: for j in range(yn)[::-1]: if i==tn-1 and j==yn-1: continue elif L3[i][j+1]<L3[i+1][j]: L4[i][j]="R" elif L3[i+1][j]<=L3[i][j+1]: L4[i][j]="D" L3[i][j] += {"R":L3[i][j+1], "D":L3[i+1][j]}[L4[i][j]] i,j,L5,L6 = 0,0,[],[] while L4[i][j]: L5.append(L2[i][j]) L6.append(L4[i][j]) if L4[i][j]=="D": i += 1 else: j += 1 L5.append(L2[i][j]) return L3[0][0], L5, L6 import os fn = os.path.join(os.path.dirname(__file__),"problem081_matrix.txt") s, val, dir = f(fn) print "sum:", s print "val:", val print "dir:", dir



問18問67を参考にしました。

1.関数f(fn)
・下方向と右方向にのみ移動して通過したセルの最小和、そのパスを返します。

・リストL0にmatrixファイルの全データを行ごとに格納します。

・リストL1としてL0を行ごと値ごとの2次元配列にします。
 ここで縦横の要素数をそれぞれtn, ynとします。

・リストL2としてL1を数値化し、各列の最右端と最下段の要素を他の要素と同様に判定できるようにするために、各列の最右端と最下段に最大数値maxintを付加します。

・リストL3の初期値としてリストL2の値をコピーします。
 L3=L2とすると参照情報(ポインター)がコピーされ、値のコピーになりません。
 一次元配列のコピーは、L3=L2[:]ですが、
 二次元配列のコピーは、L3=L2[:][:]としてもうまくいきません。
 import copyしてから、copy.deepcopy()を使います。

・i,jの二重ループの中で右下から左上に向けて遡るように順にたどり、
 各値から終点に向けて進んだときの最小累積値をリストL3に設定します。
 また最小累積値となる次の値の方向を右方向R、下方向DをリストL4に設定します。

・始点から終点に向けて最小累積値になるように方向リストL4をたどっていき、
 リストL5にそれぞれの道筋の値を、リストL6に方向の値を設定していきます。
 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 427337
val: [4445, 2697, 5115, 718, 2209, 2212, 654, 1443, 5741, 1585, 6935, 4497, 955, 101, 1478, 2509, 5436, 1732, 9480, 706, 496, 101, 5913, 93, 1899, 328, 2876, 3604, 673, 158, 5093, 2447, 5782, 3967, 1716, 931, 239, 2000, 1228, 3513, 1909, 354, 2410, 4171, 2709, 341, 5866, 106, 6379, 508, 811, 2871, 3525, 6356, 3906, 1212, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 739, 2100, 5800, 728, 4299, 10, 1929, 114, 6393, 9398, 265, 2622, 76, 2874, 880, 7270, 4071, 697, 9060, 3578, 1163, 1228, 2621, 3275, 2737, 7731, 486, 5726, 679, 355, 1330, 2933, 985, 3200, 1663, 1456, 6846, 3120, 1211, 1622, 3176, 4524, 3996, 615, 2863, 1715, 242, 958, 3058, 584, 3234, 9688, 1549, 2917, 394, 3081, 2581, 2994, 923, 2705, 4266, 3232, 2264, 6761, 363, 483, 556, 619, 3212, 3374, 3510, 1129, 3568, 2241, 2625, 2666, 4609, 1061, 2260, 3199, 1150, 1865, 1130, 3144, 163, 6310, 2854, 3503, 3391, 6932, 1040, 5128, 1113, 3406, 7981]
dir: ['R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R']

2013年8月15日木曜日

プロジェクトオイラー 問80別解

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

問80「平方根の10進展開」
よく知られているように、自然数の平方根が整数ではないならば、それは無理数である。
そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。
2の平方根は1.41421356237309504880..., であり、
その頭から100桁の数字を合計すると475になる。

初めの100個の自然数の平方根のうち、無理数について、
それぞれの頭から100桁の数字を足した数の総和を求めよ。


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






私の回答例は以下の通りです。

def f(n, m): L, c = [i*i for i in xrange(n+1)], 0 for i in xrange(n+1): if i in L: continue x, a = i*10**m, i*10**(m*2) while x*x-a>1: x = (x+a/x)/2 c += sum([int(s) for s in str(x)[:m]]) return c n, m = 100, 100 print f(n, m)


平方根をニュートン法で求めます。
ニュートン法は方程式の解を近似計算する数値計算法です。
ニュートン法ではf(x)=0となるxを求める際に、xの近傍のxnでの接線とそのX軸との交点xn+1を順に求めていくことを繰り返してxの近似値を求めます。

(参考)
ニュートン法(wikipedia)

y=f(x)において、x=xnでの接線の傾きは微分係数f'(xn)なので以下の式が成り立ちます。
f(xn) = f'(xn) × (xn - xn+1)
式変形して、
xn+1 = Xn - f(xn)/f'(x)

当問題では平方根を求める元の数をaとして
f(x) = x2 - a としてf(x)=0となるxの近似値を求めます。
なお、xもaもそのままの値では小数点以下の桁が丸められてしまうので10のm乗倍などして大きな整数値にしてから処理して、x2 - a が1を超える場合に近似値を求め続けていきます。

開平法と比べ、ループ変数iの内側が簡単な式になっています。
処理時間も私の作った開平法ロジックと比べて30%程度です。


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

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

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

問80「平方根の10進展開」
よく知られているように、自然数の平方根が整数ではないならば、それは無理数である。
そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。
2の平方根は1.41421356237309504880..., であり、その頭から100桁の数字を合計すると475になる。

初めの100個の自然数の平方根のうち、無理数について、それぞれの頭から100桁の数字を足した数の総和を求めよ。



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






私の回答例は以下の通りです。
def f(n, m):
	L, c = [i*i for i in xrange(n+1)], 0
	for i in xrange(n+1):
		if i in L: continue
		M, s, t = [], 0, i
		for j in xrange(m):
			N = [s*10+k for k in xrange(10)]
			for k in range(10)[::-1]:
				w = s*10+k
				if w*k<=t: break
			M.append(k)
			s, t = w+k, (t-w*k)*100
		c += sum(M)
	return c

n, m = 100, 100
print f(n, m)


平方根を開平法で求めます。

(参考)
開平法(wikipedia)

ルートを開こう(中村文則氏のサイト)


1.関数f(n, m)
・n個の自然数の平方根のうち、無理数について、それぞれの頭からm桁分の数字の和の総和を返します。

・リストLは自然数の2乗のリストで、その要素は平方根が有理数になる自然数す。

・変数cに求める総和を累積していきます。初期値は0です。

・ループ変数iが平方根を求める対象の自然数です。
 iがリストLに含まれている場合は対象外なので処理を飛ばします。

・リストMは平方根の各桁ごとの数字をためていくリストです。
・sは初期値0です。
・端数tは、元の数から、平方根を求めた桁までの2乗を差し引いた端数です。
 最初は平方根は1桁も求まっていないので、tの初期値はiです。

・ループ変数jは平方根の左端の桁位置を0とした桁位置を示します。

・for k in range(10)[::-1]:
w = s*10+k
if w*k<=t: break
 ループ変数kは、0から9までの配列を逆順に1つずつ取り出します。
 1つ前のループで計算したsの桁を1つ上げて(10倍して)kをたした値をwとし、
 wとkの積がtを超えない最大値となるkを探します。
 このkが平方根の求める桁の値です。

・s, t = w+k, (t-w*k)*100
 上記のkで1桁進みましたので次の桁の準備をします。
 wとkの和をsとします。
 新たに決定した桁の分である、wとkの積を端数tから差し引きます。
 100の平方根が10なので、平方根は元の数2桁ごとに1桁決まります。
 このため端数tは100倍しておきます。


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