プロジェクトオイラー
http://projecteuler.net/index.php
最初、深さ優先探索をしたら時間的に話にならなかった。
すぐに、状態とそれが何通りあるかを記憶していけばそれなりにいけるのではないかと思ったが、なんとなくめんどくさくて放っておいた。少し精神的に余裕が出来たのでやってみたら、簡単にできた。
敷き詰めた状態は108ビットあれば表せるので、最初は4つの整数の配列を使っていたが、多倍長整数にしたら、少し速くなった。このほうがコードはすっきり。それから、トリオミノは上から順に敷き詰めていったが、全体が縦長の長方形と考えるほうがかなり速くなる。
triomino = (
(0, 1, 4), (0, 1, 5), (0, 4, 5), (0, 3, 4), (0, 4, 8), (0, 1, 2)
)domain = (
( 0, 1, 1), (0, 1, 1), (0, 1, 1),
(-1, 0, 1), (0, 0, 2), (0, 2, 0)
)class Grid:
def __init__(self, w, h, s = 0):
self.w = w
self.h = h
self.a = s
self.t = [ ]
self.num_solution = 0
def is_fit(self, k, pos):
if not self.is_inside(k, pos): # O.B
return False
for e in triomino[k]:
if not self.is_empty(self.offset_pos(pos, e)):
return False
return True
def is_inside(self, k, pos):
if domain[k][0] + pos % self.w < 0: # left
return False
if domain[k][1] + pos % self.w >= self.w: # right
return False
if domain[k][2] + pos / self.w >= self.h: # bottom
return False
return True
def offset_pos(self, pos, e):
if e == 3:
pos += self.w - 1
else:
pos += (e & 3) + self.w * (e >> 2)
return pos
def push(self, k, pos):
for e in triomino[k]:
self.add_square(self.offset_pos(pos, e))
self.t.append( (k, pos))
def pop(self):
k, pos = self.t.pop()
for e in triomino[k]:
self.remove_square(self.offset_pos(pos, e))
def get_pos(self):
i = 0
while self.a & (1 << i):
i += 1
return i
def is_empty(self, p):
return (self.a & (1 << p)) == 0
def add_square(self, p):
self.a |= 1 << p
def remove_square(self, p):
self.a ^= 1 << pw = 9
h = 12
N = w * h / 3
g = Grid(w, h)
stats = { 0:1 }
for i in range(w * h / 3):
stats_next = { }
for s, n in stats.iteritems():
g1 = Grid(w, h, s)
pos = g1.get_pos()
for k in range(6):
if g1.is_fit(k, pos):
g1.push(k, pos)
if g1.a in stats_next:
stats_next[g1.a] += n
else:
stats_next[g1.a] = n
g1.pop()
stats = stats_nextprint sum(stats.values())
