プロジェクトオイラー Problem23

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

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

Problem 23
完全数とは, その数の真の約数の和がそれ自身と一致する数のことである.
たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28であるので, 28は完全数である.

真の約数の和がその数よりも少ないものを不足数といい,
真の約数の和がその数よりも大きいものを過剰数と呼ぶ.

12は, 1+2+3+4+6=16となるので, 最小の過剰数である.
よって2つの過剰数の和で書ける最少の数は24である.
数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている.
2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.

2つの過剰数の和で書き表せない正の整数の総和を求めよ.


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

def g(n):
	L = []
	for i in xrange(1, n):
		if n%i: continue
		elif n<i*i: break
		L.append(i)
		if 1<i<n/i: L.append(n/i)
	return sum(L)
	
def f(n):
	L0 = [i for i in xrange(n+1) if i<g(i)]
	L1 = [i+j for i in L0 for j in L0 if i+j<=n]
	L2 = set(L1)
	return (n*(n+1)/2)-sum(L2)
	
print f(28123)

－－－－－

２つの関数を使用しています。

１．g(n)
・「真の約数」の和を返します。
・problem 21　の関数d(n)を再利用しました。

２．f(n)
・リストL0は、n以下の過剰数のリストです。
　for文で0～nの値を順番にループ変数iに設定し、後ろのif文へ渡します。
　i<g(i)で、自分自身よりも「真の約数の和」の方が大きい（過剰数）の場合、for文の前に渡してその計算値（この場合はiそのまま）をリストに設定していきます。

・リストL1は、リストL0の任意の２つの和のうち、n以下の値のリストです。
　最初のfor文でリストL0から値を順に取り出してループ変数iに設定し、
　次のfor文でもリストL0から値を順に取り出してループ変数jに設定します。
　これでL0から重複ありで2つ取り出した状態です。
　これで後ろのif文に値を渡します。
　if i+j<=n で、取り出したiとjの和がn以下ならば、for文の前の計算式（ここでは、i+j）に値を渡してその計算値をリストに設定していきます。

・リストL2は、リストL1内の値の重複を削除し、ユニークにします。
　set関数で引数のリストを、値のユニークなタプル（要素を変更できない配列）に変換します。

・return (n*(n+1)/2)-sum(L2)
　(n*(n+1)/2)は、1～nまでの和の公式そのままです。
　ここから、n以下の２つの過剰数の和を引くことで、
　２つの過剰数の和で書き表せない正の整数の和が返却されます。
　
　　
３．関数の外
・上記の関数fに、28123を渡せば求める数値になります。


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

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

プロジェクトオイラー Problem22

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

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

Problem 22
5000個以上の名前が書かれている46Kのテキストファイルnames.txt を用いる.
まずアルファベット順にソートせよ.
のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.

たとえば, リストがアルファベット順にソートされているとすると,
COLINはリストの938番目にある.
またCOLINは3 + 15 + 12 + 9 + 14 = 53という値を持つ.
よってCOLINは938 × 53 = 49714というスコアを持つ.

ファイル中の全名前のスコアの合計を求めよ.


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

def f(sIn):
	#alphabet dictionary
	D = {}
	for i, s in enumerate(xrange(ord("A"), ord("Z")+1)):
		D[chr(s)] = i+1
	
	#read
	L0 = []
	s = open(sIn).read()
	for t in s.split(","):
		L0.append(t[1:-1])
	
	#sort
	L1 = sorted(L0)
	
	#score
	L2 = []
	for i, s in enumerate(L1):
		u = [D[t] for t in s]
		L2.append((i+1)*sum(u))
	
	return sum(L2)
	
import os, sys
sIn = os.path.join(os.path.dirname(sys.argv[0]), "names.txt")
print f(sIn)

－－－－－

１．アルファベット辞書作成
・スコア計算で使用するアルファベットの記号と序数の対応辞書を作成します。
・for i, s in enumerate(xrange(ord("A"), ord("Z")+1)):
　アルファベットを全部手打ちするのは大変なので、ord関数で８ビット文字のバイト値（数値）にします。　例）ord("A")=65
　xrange関数でAからZのバイト値（数値）の範囲で順にfor文で値を取れるようにします。
　Zまで含めるために終了条件はord("Z")+1になります。
　enumerate関数により、変数iに0から始まる序数を設定し、変数sに各アルファベットのバイト値を設定します。
・D[chr(s)] = i+1
　chr関数はord関数の逆関数です。先ほどのバイト値を８ビット文字に戻します。
　辞書Dには文字A～Zをキーにして、スコア値1～26を持つように設定します。
　序数iは0から始まるので、Aと1を対応づけるためにi+1をセットします。
　辞書Dは以下の通り。D={"A":1, "B":2, ・・・, "Z":26}

２．読み込み
・提示されたテキストファイルを読み込みデータ要素ごとにリストL0に貯めます。
　提示されたテキストファイルはカンマ区切り、ダブルクォーテーション挟み、改行なしのデータファイルです。
・s = open(sIn).read()
　ファイルを開いて、全部一気に読み込みます。
・for t in s.split(","):
　まず区切り文字のカンマで区切って、要素に分解します。
・L0.append(t[1:-1])
　t[1:-1]で、各要素の左端と右端の文字を外します。これで挟み文字のダブルクォーテーションがとれます。

３．ソート
・L1 = sorted(L0)
　sorted関数で並べ替えます。第２引数以降でいろいろな並び替えができるのですが、第１引数だけ指定して単純に昇順に並べます。

４．スコア計算
・アルファベットに値を割り振り, リスト中の出現順の数と掛け合わせスコア値とします。
・for i, s in enumerate(L1):
　enumerate関数でリストL1の要素を１つずつ取り出すと同時に、対応する0からの連番を付与します。
　iには0からの連番、sには要素が１つずつ設定されます。
・u = [D[t] for t in s]
　先ほど取り出した要素sは文字列なので、さらにfor文で1文字ずつに分解してループ変数tに取り出します。
　そしてtをキーにしてアルファベット辞書Dの値を参照して、"A"なら1のように変換した状態でリストにため、１要素分全体でリストuとします。
　例）s=COLINのとき、u=[3, 15, 12, 9, 14]
・L2.append((i+1)*sum(u))
　スコア値は、リストuの合計値とデータ要素序数の積なので、その通りにリストL2に貯めていきます。
　このときデータ要素序数の方は、0から始まっているので、+1して、1から始まる数に調整しておきます。
・return sum(L2)
　求めるスコア合計は、上記のリストL2の合計なので、sum関数でリストの全要素の合計値を計算し返します。

５．関数fの外で
・提示されたテキストファイルのフルパスを、関数fに渡します。
・sIn = os.path.join(os.path.dirname(sys.argv[0]), "names.txt")
・sys.arvgは、今実行中のシステムが持つ引数値アーギュメントバリューです。
　sys.argv[0]は、このソースが書かれたpythonソースファイルのフルパスです。
・os.path.dirnameで親フォルダ名を取り出し、
　os.path.joinでその親フォルダとnames.txtをパスとして結合しています。
・上記で、当ソースファイルと同じフォルダにあるnames.txtのフルパスが取得できました。これを関数fに渡しています。

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

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

プロジェクトオイラー Problem21

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

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

Problem 21
d(n)をnの真の約数の和と定義する。（真の約数とはn以外の約数のことである。）
もし、d(a) = b かつ d(b) = a （a ≠ b）を満たすとき、aとbは友愛数（親和数）であるという。
例えば、220の約数は1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110なので
d(220) = 284である。
また、284の約数は1, 2, 4, 71, 142なので
d(284) = 220である。

それでは10000未満の友愛数の合計を求めよ。


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

def d(n):
	L = []
	for i in xrange(1, n):
		if n%i: continue
		elif n<i*i: break
		L.append(i)
		if 1<i<n/i: L.append(n/i)
	return sum(L)
	
def f(n):
	L = []
	for i in xrange(1, n):
		s = d(i)
		t = d(s)
		if i!=s and i==t: L.append(s)
	return L
	
L = f(10000)
print sum(L)
print L

－－－－－

２つの関数を使用しています。
１．d(n)
・nの真の約数の合計値を返します。
・リストLに約数をためていき、関数終了時にsum関数でリストLの要素の合計値を返します。
・for i in xrange(1, n):
　真の約数はnを含まないので、ループ変数iは1からn-1までの値とします。
・if n%i: continue
　%演算子は割り算の余りです。論理式では0がFalse、1以上の値がTrueです。
　iで割って余りがあれば約数ではないので、ループ変数iは次の値に進みます。
・elif n<i*i: break
　割る数iがnの約数のとき、商n/iも約数です。割る数と商の両方を約数リストにためていけば、割る数が商よりも小さい場合だけ試せば十分です。
　割る数iは２乗してnになる値を超えると割る数よりも商が小さくなり、割る数と商が入れ替わっただけの、もうすでに試した数になるためループは終了します。
・L.append(i)
　if 1<i<n/i: L.append(n/i)
　割る数iは無条件で約数リストLに追加し、商n/iはチェックして約数リストLに追加します。
　i=1の場合、n/iはnになり、自分自身を含まないという「真の約数」の定義に合わないので追加しません。
　i=i/nの場合、割る数iを直前行で約数リストに追加しているのでn/iは追加しません。

２．f(n)
・n未満の友愛数のリストを返します。
・for i in xrange(1, n):
　真の約数はnを含まないので、ループ変数iは1からn-1までの値です。
・s = d(i)
　t = d(s)
　sはループ変数iの「真の約数」の和で、tはこのsの「真の約数」の和です。
・if i!=s and i==t: L.append(s)
　iとsが異なる値であり、iとtが同じ値であることは友愛数の定義です。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
31626
[284, 220, 1210, 1184, 2924, 2620, 5564, 5020, 6368, 6232]

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

番地号の表記（６） 文字街区－漢字のみ（その２）

過去記事、「番地号の表記（６）　文字街区－漢字のみ」の続報です。

埼玉県鴻巣市には、かねてより以下のような、「番地」「街区」の部分に漢字地名を設定した、「文字街区」とでも言うべき住所がありました。
普通は「１番地」のように数字がくる部分が「本一町」「宮本町」などと設定されています。

埼玉県鴻巣市本町１丁目　本一町
埼玉県鴻巣市本町１丁目　宮本町

場所はここです。（Googleマップ）
公園を作るときに旧町名の地名を街区部分に設定していました。

そしてこの春、鴻巣市がまたやってくれました。
今度は学校の校庭の街区部分に、旧町名を設定しました。

埼玉県鴻巣市本町６丁目　富永町
埼玉県鴻巣市本町６丁目　石橋町

鴻巣市　広報誌「かがやき」平成２４年４月号
＞　１８ページ　(※pdfファイル)
情報広場　本町６丁目４番の街区名を旧町名の「富永町」「石橋町」に変更
によると、
「東小学校地内における住居表示の街区符号が、写真のとおり旧町名の「富永町」「石橋町」となりました。」
とのことです。

鴻巣東小学校の場所はここです。（Googleマップ）

住居表示法上の「街区」は、道路などの恒久的なもので区切られている必要がありますが小学校の校庭にはそのような区切るものがなく、どうやって「街区」を設定したものかと思っていたところ、以下の参考記事によれば、登記上は校庭に道路が何本もあるそうで、この登記上の道路で区切ったようです。

（参考）講釈師はクプクプ笑う　（神田鯉風さんのサイト）
916 【団子饅頭３５】また復活した旧町名と「塩あんびん」‥鴻巣

プロジェクトオイラー Problem20

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

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


Problem 20
n × (n - 1) × ... × 3 × 2 × 1 を n! と表す。
100! の各桁の数字の合計を求めよ。


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

def f(i):
	if i<=1: return 1
	else: return i*f(i-1)
	
print sum([int(i) for i in str(f(100))])

－－－－－

・f()
　階乗の関数を再帰呼び出しで書いてみました。
　停止条件がi=1であり、f(1)になるまで、引数iに１つ前の階乗値f(i-1)をかけます。
　１つ前の階乗値を求めるなかで、さらに１つ前の階乗値を使用するため自分自身を呼び出します。

・sum([int(i) for i in str(f(100))])
　階乗値f(100)をstr関数で文字型に変換します。
　文字型はpythonではシーケンス(sequence)という、forループで回せるオブジェクトです。
　文字列をforループで回すと、ループ変数に文字列の1文字ずつが設定されます。
　こうしてループ変数iに階乗値の1桁ずつが文字型で設定されてfor文の前に渡され、int関数で整数型にした状態で配列の要素として保持します。
　こうして、100の階乗値の1桁ずつの数値を設定した配列ができあがり、これをsum関数で合計します。

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

（追記）
・20120708
　関数fの停止条件がn==1では無限ループになるのでn<=1に修正。
・20120715
　ソースコード部分にSyntaxHighlighterを導入。

プロジェクトオイラー Problem19_2

前回のproblem19では、うるう年と曜日の計算をする部分を、あえて標準モジュールを使わずに自作しましたので、pythonの標準モジュールとどうなるかを以下に記述します。

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

import datetime
def f(ymd0, ymd1):
	s, t, r = str(ymd0), str(ymd1), 0
	y0, m0 = int(s[:4]), int(s[4:6])
	y1, m1 = int(t[:4]), int(t[4:6])
	for i in xrange(y0, y1+1):
		j0, j1 = {y0:m0}.get(i,  1), {y1:m1}.get(i, 12)
		for j in xrange(j0, j1+1):
			if datetime.datetime(i, j, 1).weekday()==6: r += 1
	return r
	
print f(19010101, 20001231)

－－－－－

うるう年と曜日の計算をする部分は、datetimeという標準モジュールですべて代替できます。
前回のソースコードと比べると、uruu関数とyoubi関数が不要になりました。

注意すべき点は、datetimeモジュールのdatetimeオブジェクトのweekday関数の戻り値は、「月曜日を 0、日曜日を 6 とする整数」であることです。
このため、日曜日判定では、weekday関数の戻り値が6かどうかを判定しています。


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

プロジェクトオイラー Problem19

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

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

Problem 19
次の情報が与えられている。
・1900年1月1日は月曜日である。
・9月、4月、6月、11月は30日まであり、2月を除く他の月は31日まである。
・2月は28日まであるが、うるう年のときは29日である。
・うるう年は西暦が4で割り切れる年に起こる。
  しかし、西暦が400で割り切れず100で割り切れる年はうるう年でない。
 20世紀（1901年1月1日から2000年12月31日）で月の初めが日曜日になるのは何回あるか。


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

M = [31,28,31,30,31,30,31,31,30,31,30,31]
def uruu(y, m=3):
	if m<=2: return 0
	if y%400 and (not y%100): return 0
	elif not y%4: return 1
	else: return 0
	
def youbi(y, m):
	yy = [365+uruu(i) for i in xrange(1900, y)]
	mm = [M[i] for i in xrange(m-1)]
	s = sum(yy)+sum(mm)+uruu(y, m)+1
	return s%7
	
def f(ymd0, ymd1):
	s, t, r = str(ymd0), str(ymd1), 0
	y0, m0 = int(s[:4]), int(s[4:6])
	y1, m1 = int(t[:4]), int(t[4:6])
	for i in xrange(y0, y1+1):
		j0, j1 = {y0:m0}.get(i,  1), {y1:m1}.get(i, 12)
		for j in xrange(j0, j1+1):
			if youbi(i, j)==0: r += 1
	return r
	
print f(19010101, 20001231)

－－－－－

・指定期間の日数の累積値を求め、7で割った余りで曜日を判定します。
・リストMは、平年の月別日数リストです。
 うるう年の影響は判定して+1することにします。
・関数を３つ使っています。

１．uruu(y, m=3)
・うるう年の追加日数です。
・２月以前はうるう年に関係なく追加日数は0です。
・%関数は割り算の余りです。
　余りがある(0以外)は論理的にTrueで、余りがない(0)は論理的にFalseです。
・問題文の通り、400で割れて100で割れない年は0、これ以外で4で割れれば1を返します。
・引数を年だけにすると、mの初期値を3月にしてあるので、うるう年かどうかの判定関数としても使用可能です。

２．youbi(y, m)
・指定年月の月初日の曜日を返します。
　曜日は0=日曜日, 1=月曜日,・・・, 6=土曜日です。
・yyは前年までの各年の年間日数のリストです。
 uruu()を年だけ引数にしてうるう年判定をしています。
・mmは最終年について、年初から前月末までの月別日数リストです。
　うるう年調整前状態です。
・sは1900年1月1日から指定月の前月末までの日数です。
　リストyyの和で前年末までの日数、
　リストmmの和で前月末までの日数、
　そして年月指定でのうるう年追加日数、
　さらに1900年1月1日が月曜日になるように調整で1加算しています。
・戻り値は、上記の累積日数を7で割った余りです。

３．f(ymd0, ymd1)
・期間の開始と終了の日づけをyyyymmdd形式の数値で受取り、その期間内の日曜日で始まる月数を返します。
・年ループ変数iと月ループ変数jの二重ループで、期間内の年月を生成し曜日を求め、日曜日ならカウントアップします。
・y0, m0 = int(s[:4]), int(s[4:6])
　開始年、開始月を一度に設定しています。
・{y0:m0}.get(i,  1)
　辞書{y0:m0}は、開始年をキーに開始月を値に持つ辞書です。
　get関数で、年iを判定して開始年y0の場合に開始月m0を返却し、辞書にキーが無い他の年は1を返します。
・j0, j1 = {y0:m0}.get(i,  1), {y1:m1}.get(i, 12)
　月ループ変数初期値j0は、開始年なら開始月m0で、それ以外の年は1月です。
　月ループ変数終了値j1は、終了年なら終了月m1で、それ以外の年は12月です。

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

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

プロジェクトオイラー Problem18

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

出典：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を導入。