プロジェクトオイラー
http://projecteuler.net/index.php
Q178.
45656のように隣の桁から1ずつ変わって、かつ0〜9をすべて使う1040より小さい数はいくつあるか。
一次元のランダムウォーク。場所を0〜9に限定して39回まで動かす。そのときに、0〜9をすべて動けばよい。そのために、そうでないものを引く。すなわち、場所を1〜9に限定したものと0〜8に限定したもの。しかし、1〜8に限定したものが重複して引かれているので、その分は足す。その場所に到達するパスの数を次々と計算していく。
def g(n, m, a):
b = [ ]
b.append(a)
for n in range(1, n):
c = [ 0 ] * m
for i in range(m):
if i == 0:
c[i] = b[n-1][1]
elif i == m - 1:
c[i] = b[n-1][i-1]
else:
c[i] = b[n-1][i-1] + b[n-1][i+1]
b.append(c)
return sum(map(sum, b))def f(n, start, end):
m = end - start + 1
if start == 0:
a = [ 0 ] + [ 1 ] * (m - 1)
else:
a = [ 1 ] * m
return g(n, end - start + 1, a)N = 40
print f(N, 0, 9) - f(N, 0, 8) - f(N, 1, 9) + f(N, 1, 8)
