プロジェクトオイラー
http://projecteuler.net/index.php
Q215.
2×1と3×1のレンガを積んで、32×10の壁を作る。ただし、上下で同じ位置にレンガの切れ目があってはならない。レンガの積み方は何通りあるか。
1列の並べ方をグラフの点と考えて、上下に並べられるとき線で結ぶ。最初はバイナリ法のようなものを考えていて、5列と5列を結合するのに5列の一番上と下のレンガの並びが必要なので、両方をもって状態と考えていた。しかし、そうではなく、一番上の並びだけ状態と考え、その上に可能な1列を並べる、と考える。レンガではなく、純粋にグラフで考えるほうがわかりやすかった。グラフ理論では正確にどう呼ぶのか知らないが、長さが9の道を考える。そのとき始点に対して、隣の点を始点とする長さ8の道の数を足し合わせればよい。
from itertools import combinations
import timedef make_row_core(n, e):
t = ()
j = 0
s = 0
for i in range(n - 1):
if j < len(e) and i == e[j]:
s += 3
j += 1
else:
s += 2
t += (s,)
return tdef make_row(len):
a = [ ]
n0 = len % 2
for n in range(n0, len / 3 + 1, 2):
m = (len - n * 3) / 2
for e in combinations(range(n + m), n):
a.append(make_row_core(n + m, e))
return adef is_match(r1, r2):
if abs(len(r1) - len(r2)) >= 2:
return False
if len(r1) < len(r2):
r1, r2 = r2, r1
if len(r1) > len(r2):
if r1[0] >= r2[0]:
return False
offs = 1
else:
offs = 0
for i in range(len(r2)):
if r1[i+offs] == r2[i]:
return False
return Truedef is_match(r1, r2):
for e in r1:
if r2.count(e):
return False
return Truedef make_graph(a):
n = len(a)
g = [ [ ] for i in xrange(n) ]
for i in xrange(n):
for j in xrange(i + 1, n):
if is_match(a[i], a[j]):
g[i].append(j)
g[j].append(i)
return gdef mul(g, a):
return [ sum(map(lambda k: a[k], e)) for e in g ]def pow(g, n):
if n == 2:
return [ len(e) for e in g ]
return mul(g, pow(g, n - 1))t = time.clock()
N = 32
M = 10
a = make_row(N)
print len(a)
g = make_graph(a)
print sum(pow(g, M))
print time.clock() - t