プロジェクトオイラー Problem8

「プロジェクト　オイラー」の問題をpythonでやってみます。

出典： Project Euler （日本語翻訳サイト）
参考： サイエンスもの置き場　プロジェクトオイラーを遊び倒すガイド（初級編）

Problem 8
以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する。
そのような積の中で最大のものの値はいくらか。

例）6桁の数123789なら、1*2*3*7*8と2*3*7*8*9の二通りとなり、後者の2*3*7*8*9＝3024が最大の積となる。

(問題の数字は以下の変数p）


私の解答例は以下のとおりです。
－－－－－

p = \
"""
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""
def g(x, y): return x*y
def f(p, n):
 L, t = [int(i) for i in list(p) if "0"<=i<="9"], 1
 for i in xrange(len(L)-n+1):
  s = reduce(g, L[i:i+n])
  if s>t: t, v = s, i
 return t, v+1, L[v:v+n]

s = f(p, 5)
print s[0], ":", s[1], "番目からの", s[2], "の積"

－－－－－
・p = \
　バックスラッシュ（または円マーク）は継続行を示します。複数行を1行として扱いたい場合の行末に付けます。

・"""
　トリプルクォーテーション（"または'の連続3つ ）で挟むと、複数行にわたる文字列を改行コードも含めて設定できます。
　ここでは与えられた長大な文字列を変数pに設定しています。
　左辺が無い、"""～"""で挟むだけならば、ただのコメント行として機能します。

以下、２つの関数を使っています。
１．２つの数の積　g(x, y)
　２つの引数の積を返します。

２．文字列pに含まれる連続するn個の数字の積の最大値　f(p, n)
・L, t = ・・・
　文字列pを1字ずつ数字型で要素に持つリストLと、求める最大値tを初期化します。

・[int(i) for i in list(p) if "0"<=i<="9"]
　文字列pをlist関数で1文字ずつのリストにします。
　次に、for文で変数iに1つずつ取り出します。まだ改行文字も含まれています。
　そして、if文で変数iが"0"～"9"の場合だけ取り出し数字だけにします。
　最後に、こうして取り出した変数iをint関数で数値型に型変換します。

　p="731・・・"　→　L=[7, 3, 1, ・・・]　となります。

　リストの内包表記での処理順は、
　中程のfor文 ＞ 末尾のif文 ＞ 先頭の配列値　です。
　上記の内包表記例では、if文で判定するのは、for文で取り出した直後でまだint関数が効いていない文字型なので、
　「if 0<=i<=9」ではなく「if "0"<=i<="9"」と判定します。

・for i in xrange(len(L)-n+1):
　変数iはn個掛け算するうちの最初の値です。
　n個の数字が取れるのは、最初から「最後からn-1番目まで」です。
　それより後ろはn個未満しか残っていないので対象外です。

・s = reduce(g, L[i:i+n])
　reduce関数は、reduce(関数名, シーケンス)として、関数にシーケンスの１つ１つの値を左から右に累積的に適用します。

　関数g(x, y)は引数を２つ受け取ってその積を返します。
　リストL[i:i+n]は、リストLのi番目からn個分の要素です。
　つまりここでの処理は以下のようになります。

　最初、関数gにL[i]とL[i+1]を渡し、その積を求めます。
　次に、関数gに先ほど求めた値とL[i+2]を渡し、その積を求めます。
　さらに関数gに先ほど求めた値とL[i+3]を渡し、その積を求めます。

　やっていることは以下を要素n個分続けることと同じです。
　(・・・((L[i]*L[i+1])*L[i+2])*L[i+3]・・・)

　for文を使って以下のように書くこともできます。
 s = L[i]
 for j in xrange(1, n):
  s *= L[i+j]

　なお、reduce関数はpython3ではfunctoolsに外出しされ、使用する行より前にimportしておく必要があります。
from functools import reduce

・if s>t: t, v = s, i
　reduce関数での計算値sが、いままでの最大値tよりも大きい場合、
　計算値sとそのときの開始位置iを、それぞれtとvとして保存しておきます。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
40824 : 365 番目からの [9, 9, 8, 7, 9] の積


（追記）
・20120716
　ソースコード部分にSyntaxHighlighterを導入。