Project Euler 150

プロジェクトオイラー
http://projecteuler.net/index.php

Q150.
決められた疑似乱数（リンク先参照）を三角形状に並べたとき、同じ向きの小三角形内の和の最小

和を見ていくとき、頂点を決めてそこから下に三角形を広げて和を取っていく。
ここで、一列和を取るのは時間がかかるので、左端から各点の和をあらかじめ取っておく。途中からの和の場合は、引き算する。
もう少し複雑なことをすれば速くなりそう。

def gen_random():

    a = 615949

    b = 797807

    e = 20

    t = 0

    while True:

        t = (a * t + b) & 0xfffff

        yield t - 0x80000
def make_triangle(M):

    a = [ ]

    g = gen_random()

    for i in range(M):

        b = [ ]

        for j in range(i + 1):

            b.append(int(g.next()))

        a.append(b)

    return a
def sum_line(a, i0, j0, l):

    if j0 == 0:

        return a[i0][j0+l-1]

    else:

        return a[i0][j0+l-1] - a[i0][j0-1]

def convert_sum(a):

    for b in a:

        s = 0

        for i in range(len(b)):

            s += b[i]

            b[i] = s
a = [

    [  15 ],

    [ -14,  -7 ],

    [  20, -13,  -5 ],

    [  -3,   8,  23, -26 ],

    [   1,  -4,  -5, -18,   5 ],

    [ -16,  31,   2,   9,  28,   3 ]

]
M = 1000

N = M * (M + 1) / 2

a = make_triangle(M)

convert_sum(a)

m = 1 << 19

for i in range(M):

    for j in range(i + 1):

        s = 0

        for k in range(1, M - i + 1):

            s += sum_line(a, i + k - 1, j, k)

            m = min(m, s)

print m