出典：Project Euler（日本語翻訳サイト）
参考： サイエンスもの置き場 プロジェクトオイラーを遊び倒すガイド（初級編）
Problem 18
以下の三角形の頂点から下まで移動するとき、その数値の合計の最大値は23になる。
3
7 4
2 4 6
8 5 9 3
この例では 3 + 7 + 4 + 9 = 23
以下の三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。
※問題の三角形はプログラム中に記述
注: ここではたかだか 16384 通りのルートしかないので、 すべてのパターンを試すこともできる。
Problem 67 は同じ問題だが100行あるので、総当りでは解けない。
もっと賢い方法が必要である。
私の解答例は以下です。
－－－－－
p = """
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""
def f(u):
#1.init
p = []
for i in u.split("\n"):
if not i: continue
p.append([int(j) for j in i.split() if j])
n = len(p)
A = [["" for i in xrange(n)]]
q = p[n-1][:]
#2.val List, LR List
for i in xrange(n-2, -1, -1):
L = []
for j in xrange(i+1):
s, t = q[j], q[j+1]
v = max(s, t)
L.append({s:"L", t:"R"}[v])
q[j] = p[i][j] + v
A.insert(0, L)
q.pop(i+1)
#3.Route Search for MaxValue
L, M, i = [], [], 0
for s, t in zip(A, p):
L.append(s[i])
M.append(t[i])
if s[i]=="R": i+=1
return sum(M), M, L
s, val, LR = f(p)
print "sum:", s
print "val:", val
print "LR :", LR
－－－－－「Problem 67 は・・・総当りでは解けない。もっと賢い方法が必要である。」
・・・後で困るからproblem18も「総当たり」以外の賢い方法でやっておこうねと暗に言っているので、まずやり方を考えました。
上からたどっていくとどうしても総当りになってしまうため、下から不要な枝を切り落としていくようにしました。
・関数f(u)は、「整数の三角形」を受け取り以下の３つの値を返します。
たどった値の合計値の最大値。
各段で選んだ「値リスト」。
次に左下と右下どちらを選んだかをそれぞれ"L"と"R"で示す「LRリスト」。
・「整数の三角形」を丸ごと"""で挟むことで、複数行にわたるデータを改行文字を含んだ状態で1つの文字列値として変数uに設定しています。
１．init
・初期化です。「整数の三角形」uをリストpに設定します。
・まず「整数の三角形」を改行文字\nで区切ってリストiに設定します。
なお、値が無い場合はその行は処理せず次の行へ進みます。
・[int(j) for j in i.split() if j]
これは内包表記という記述方法で、以下の動作結果のリストを意味しています。
i.split()でリストiを半角空白で区切ってその要素１つひとつをjとし、後ろのif文で値があることをチェックしてから、前のint(j)で文字列から整数型に変換します。この整数型の要素をリストにします。
・入力リストpは、段ごとに値を設定した２次元配列になります。
例）p = [[75],[95, 64],・・・]
・変数nは「整数の三角形」の段数です。この値は最下段の要素数でもあります。
・リストAは各段ごとの「LRリスト」のリストです。
初期値として最下段の各要素のLR値として、""を最下段の要素数分用意します。
・リストqは、入力リストpの最下段～１つ下の段までの最大値の累積値を設定します。初期値は最下段の値そのままです。
・q = p[n-1][:] の[:]はリストの[開始位置:終了位置]の値を省略した表記で、リストの最初から最後まで全要素を表し、この行全体では「リストの全要素の値コピー」の意味になります。
q = p[n-1]という記述では「ポインタコピー」なので、リストqの値を変更するとリストp[n-1]の値も変更されてしまいます。このためここでは「値コピー」で記述します。
２．val List, LR List
・「値リスト」と「LRリスト」を作成します。
・for i in xrange(n-2, -1, -1):
段番号iのループです。n-2で最下段の１つ上の段から始めて、-1段目になったら処理を抜けるので0段目である最上段まで処理し、刻みは-1なので下の段から上へ１段ずつ処理します。
・for j in xrange(i+1): 段内番号jのループです。段番号iはその段内の要素数でもあるので、段内の最初0番目の要素から、段内最後のi番目まで処理し、i+1になったら処理せず終了します。
・s, t = q[j], q[j+1]
リストqは１つ下の段以下の最大値の累積です。
q[j]が左下、q[j+1]が右下へそれぞれ進んだ場合に取れる最大累積値で、それぞれs, tに設定します。
・v = max(s, t)
値vは1つ下の段の左右いずれかに進んだときの合計最大数のうち、大きい方の値です。
・{s:"L", t:"R"}[v]
値vが判定条件になって、v=sならば"L"、v=tならば"R"を返します。
・L.append({s:"L", t:"R"}[v])
一時リストLに、段内の各要素のLR値をためていきます。
・q[j] = p[i][j] + v
リストqは、「入力リストpの最下段～１つ下の段までの累積最大値」なので、次の段の処理の準備として、現在のi段目j個目の値とここより下段の最大累積値vの合計を改めて設定しておきます。
・A.insert(0, L)
段内の全要素の処理が終わったところで、この一時リストを丸ごとリストAにためます。後で上段からたどることになるので、ここでは要素番号0の位置に順番に挿入することで、処理は下段からですがリストAの要素としては上段から並ぶようにします。
・q.pop(i+1)
段が１つ上がるごとに要素数が１つ減るので、最後の要素分を削除しておきます。
３．Route Search for MaxValue
・最上段からたどって合計が最大値になる道筋を探索します。
・for s, t in zip(A, p):
リストAはLRリストの２次元配列で、pは「整数の三角形」の２次元配列です。
zip関数は引数のリストから同じ位置番号の要素を組として取り出します。
ここでは、上段から順に、段ごとのLRリストと整数の三角形の値リストをs、tに設定してループを回します。
なお、zip関数の引数はリストだけでなく、シーケンスと言う、リストのように位置番号で値が取れる構造のデータはすべて設定可能です。例えばpytonでは文字列もシーケンスです。
・L.append(s[i])
M.append(t[i])
リストLとMに、各段で採用する値とLR値（その次の段は左下に進むか右下か進むか）を設定します。
・if s[i]=="R": i+=1
iは段内の位置番号です。左下にすすむ場合は段内位置番号は変わりませんが、右下に進む場合は段内位置番号が1増加します。
・return sum(M), M, L
戻り値として、リストMの合計として最大の合計値、リストMそのものとして最大合計値になる道筋の値のリスト、リストLとしてLRリストを返却します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 1074
val: [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93]
LR : ['R', 'R', 'L', 'L', 'R', 'L', 'L', 'R', 'R', 'R', 'R', 'R', 'L', 'R', '']
（追記）
・20120715
ソースコード部分にSyntaxHighlighterを導入。
0 件のコメント:
コメントを投稿