Project Euler Problem 015

http://projecteuler.net/index.php?section=problems&id=15

Starting in the top left corner of a 2x2 grid,
there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20x20 grid?

何通りの経路があるかどうか。

import datetime

def find_path_step(grid):
    n = grid + 1
    
    m = [ [ 0 ] * n for i in xrange(n) ]
    
    for y in xrange(n):
        for x in xrange(n):
            if x == 0 and y == 0:
                m[y][x] = 1
            else:
                m[y][x] = m[y-1][x] + m[y][x-1]
    
    return m[-1][-1]
    


begin = datetime.datetime.now()

N = 20
print find_path_step(grid=N)

end   = datetime.datetime.now()
print end - begin

答え: 137846528820
実行時間: 0.000649秒くらい

二次元配列を作る部分はこんなふうに書いちゃダメ。

m = [ [ 0 ] * n ] * n

これで m[0][0] = 1 すると m[1][0] も 1 になってしまう。

内側の [ 0 ] * n で作ったリストへのポインタを 外側で n 倍してしまうみたい。

別解

組み合わせで計算してもいい。gridが20くらいならたいして変わらないけど、もっと大きくなったらこの方法でないと無理。

import datetime
import operator

def C(n, m):
    nn = reduce(operator.mul, xrange(n-m+1, n+1) or [0]) or 1
    mm = reduce(operator.mul, xrange(    1, m+1) or [0]) or 1
    return nn / mm


begin = datetime.datetime.now()

N = 20
print C(N * 2, N)

end   = datetime.datetime.now()
print end - begin

答え: 137846528820
実行時間: 0.000763秒くらい