出典： Project Euler （日本語翻訳サイト）
参考：サイエンスもの置き場 プロジェクトオイラーを遊び倒すガイド（初級編）
Problem 11
20 × 20 の数字（※「私の解答例」に記載）のなか、
()でマークされた数字の積は 26 × 63 × 78 × 14 = 1788696 となる。
上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものを求めよ。
私の解答例は以下のとおりです。
－－－－－
p = """
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10(26)38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95(63)94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17(78)78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35(14)00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
"""
def g(L): return reduce(lambda x, y:int(x)*int(y), L)
def f(p, n):
L, a = [t.split() for t in p.split("\n") if t], 0
for i in xrange(len(L)):
for j in xrange(len(L[i])):
M = [
[L[i+k][j] for k in xrange(n) if i+k<len(L)],
[L[i][j+k] for k in xrange(n) if j+k<len(L[i])],
[L[i+k][j+k] for k in xrange(n) if i+k<len(L) and j+k<len(L[i])],
[L[i+k][j-k] for k in xrange(n) if i+k<len(L) and 0<=j-k]]
for k, m in zip(["down","right","rightdown","leftdown"], M):
if len(m)==n: r = g(m)
else: r = 0
if a<r: a, b, c, d, e = r, i, j, k, m
return a, b, c, d, e
a, b, c, d, e = f(p, 4)
print a, "=", " x ".join(e), "from", (b, c), "to the", d
－－－－－
・"""
トリプルクォーテーション（"または'の連続3つ）で挟むと、複数行にわたる文字列を改行コードも含めて設定できます。
左辺が無く"""で挟むだけならば、ただのコメント行として機能します。
ここでは与えられた長大な文字列を変数pに設定しています。
以下、２つの関数を使っています。
１．関数g(L)
リストLの要素をすべて掛け合わせた結果を返します。
・lambda x, y:int(x)*int(y)
ラムダ関数という表記方法です。関数名は無く、無名関数とも呼びます。
式の中に関数を直書き（じかがき）するような場合に使用します。
書式は「lambda 引数:処理」で、引数を処理した結果を返します。
ここでは、２つの引数x,yを受け取り、数値扱いにしてその積を返します。
・reduce(lambda x, y:int(x)*int(y), L)
reduce文は指定した関数に累積的に引数を渡した結果を返します。
書式は「reduce(関数, シーケンス)」で、関数にシーケンスの１つ１つの値を左から右に累積的に適用します。
ここでは「２つの引数の積」を返す関数にリストLの要素を累積的に適用します。
ここでの処理は具体的には以下のようになります。
最初、L[0] x L[1]を求めます。
次に、直前で求めた値 x L[2]を求めます。
さらに直前で求めた値 x L[3]を求めます。
やっていることは以下と同じです。
(・・・((L[0]*L[1])*L[2])*L[3]・・・)
つまり、引数のシーケンスの要素すべての積です。
ラムダ関数を使わず、def文で定義する関数で書き換えると以下の通りです。
def h(x, y): return int(x)*int(y)
reduce(h, L)
ラムダ関数を使えば、書き換え例での「h」という関数名が不要というわけです。
２．関数f(p,n)
縦横配列イメージの文字列pに対して、上下左右斜めのいずれかの方向で連続するn個の数字の積のうち最大のものを返します。
ただし、文字列pは半角空白で区切られた数字を複数行もつ文字列です。
・L, a = [t.split() for t in p.split("\n") if t], 0
変数の初期設定です。変数aに0を設定し、Lには以下のように設定します。
「for t in p.split("\n")」にて、文字列pを改行コード(\n)で分割し順に変数tに設定していきます。
次に「if t」にて、先ほどのtのうち、論理判定でTrue（0以外、カラ以外のオブジェクト）の場合に処理対象とします。
そして「t.split()」にて、先ほどのtをsplit文の引数（未設定時は半角空白）によって分割したリストを作成し、これをLの要素とします。
結果としてリストLは、pの「各行のリスト」を要素にもつリストになります。
L=[["08", "02", ・・・,"08"], ["49", "49", ・・・,"00"], ・・・]
・for i in xrange(len(L)):
for j in xrange(len(L[i])):
二重ループです。iが行番号、jが列番号です。いずれも0からの連番です。
ループ内ではL[i][j]が二次元配列の現在処理位置を表します。
iの最大値は、len(L)、リストLの要素数、つまり行数です。
jの最大値は、len(L[i])、i行目の要素数、つまりi行目の列数です。
・M = [
[L[i+k][j] for k in xrange(n) if i+k<len(L)],
[L[i][j+k] for k in xrange(n) if j+k<len(L[i])],
[L[i+k][j+k] for k in xrange(n) if i+k<len(L) and j+k<len(L[i])],
[L[i+k][j-k] for k in xrange(n) if i+k<len(L) and 0<=j-k]]
リストMに、要素として計算候補を内包表記でリストとして４つ入れます。
いずれも内包表記でループ変数kは0からn個分の整数です。
1番目のリストはL[i+k][j]。
列固定でn行分なので、現在位置から縦にn個分の値です。
2番目のリストはL[i][j+k]。
行固定でn列分なので、現在位置から横にn個分の値です。
3番目のリストはL[i+k][j+k]。
行番号を+1で下方向、列番号も+1で右方向に同時にずらしながらn個分なので、右斜め下にn個分の値です。
4番目のリストはL[i+k][j-k]。
行番号を+1で下方向、列番号を-1で左方向に同時にずらしながらn個分なので、左斜め下にn個分の値です。
これで、M=[[下方向], [右方向], [右斜め下], [左斜め下]]の値となります。
なお、内包表記末尾のif文で要素数の範囲内の場合だけ有効にしています。
縦横表からはみ出る分は取得しません。
このため、リストM内の各リストには値がn個より少ないものもあります。
・for k, m in zip(["down","right","rightdown","leftdown"], M):
zip関数は指定した複数のシーケンスから同じインデックス位置にある要素を順に取り出します。
ここでは、以下のように取り出してそれぞれ変数kと変数mに設定します。
最初、"down", M[0]の要素（=下方向の値のリスト）
次に、"right",M[1]の要素（=右方向の値のリスト）
・・・となります。
なお、pythonでは大文字と小文字は区別するので、変数のmとMは別扱いです。
・if len(m)==n: r = g(m)
else: r = 0
mは計算対象の値のリストで、rに計算結果を設定します。
要素数がn個ある場合は関数gで計算し、そうでない場合は対象外なので0とします。
・if a<r: a, b, c, d, e = r, i, j, k, m
計算結果rがその保存値であるaを超える場合、新たな保存値aとして保存します。i,j,k,mは関連情報として、それぞれb,c,d,eに保存しておきます。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
70600674 = 89 x 94 x 97 x 87 from (12, 6) to the leftdown
（追記）
・20120715
ソースコード部分にSyntaxHighlighterを導入。
0 件のコメント:
コメントを投稿