プロジェクトオイラー
http://projecteuler.net/index.php?section=problems&id=256
畳の敷き詰め方。これは難しいのではないかと思う。今のところ何も思いついていない。とりあえず、7×10は敷き詰められないことは以下のコードで確かめられる。
# coding: s_jisclass Room:
def __init__(self, a, b):
self.a = a
self.b = b
self.s = a * b
self.tatamis = [ ]
self.points = [ [ 0 ] * (a + 1) for m in xrange(b + 1) ]
self.heights = [ 0 ] * a
def next_point(self):
x = 0
y = self.heights[0]
for k in xrange(1, self.a):
if self.heights[k] < y:
x = k
y = self.heights[k]
if y == self.b:
return False
else:
return (x, y)
def place(self, cell, k):
x, y = cell
# out of room?
if k == 0: # horizontal
if x == self.a - 1:
return False
else: # vertical
if y == self.b - 1:
return False
# overlap?
if k == 0 and self.heights[x] < self.heights[x+1]:
return False
if k == 0:
width, height = 2, 1
else:
width, height = 1, 2
# cross?
if self.points[cell[1]][cell[0]+width] == 2:
return False
# place
self.points[cell[1] ][cell[0] ] += 1
self.points[cell[1] ][cell[0]+width] += 1
self.points[cell[1]+height][cell[0] ] += 1
self.points[cell[1]+height][cell[0]+width] += 1
if k == 0:
self.heights[cell[0] ] += 1
self.heights[cell[0]+1] += 1
else:
self.heights[cell[0] ] += 2
self.tatamis.append( (cell, k) )
return True
def remove(self):
cell, k = self.tatamis.pop()
if k == 0:
width, height = 2, 1
else:
width, height = 1, 2
self.points[cell[1] ][cell[0] ] -= 1
self.points[cell[1] ][cell[0]+width] -= 1
self.points[cell[1]+height][cell[0] ] -= 1
self.points[cell[1]+height][cell[0]+width] -= 1
if k == 0:
self.heights[cell[0] ] -= 1
self.heights[cell[0]+1] -= 1
else:
self.heights[cell[0] ] -= 2
def __str__(self):
c = [ [ "■" ] * (self.a * 2) for n in range(self.b * 2) ]
for cell, k in self.tatamis:
x0, y0 = cell
if k == 0:
c[y0*2 ][x0*2:x0*2+4] = [ "┏", "━", "━", "┓" ]
c[y0*2+1][x0*2:x0*2+4] = [ "┗", "━", "━", "┛" ]
else:
c[y0*2 ][x0*2:x0*2+2] = [ "┏", "┓" ]
c[y0*2+1][x0*2:x0*2+2] = [ "┃", "┃" ]
c[y0*2+2][x0*2:x0*2+2] = [ "┃", "┃" ]
c[y0*2+3][x0*2:x0*2+2] = [ "┗", "┛" ]
return "\n".join(map(lambda x: "".join(x), c))def place(room):
cell = room.next_point()
n = len(room.tatamis)
if cell == False:
return True
for k in range(2):
if room.place(cell, k):
if place(room):
return True
room.remove()
return Falsedef is_tatami_free(a, b):
room = Room(a, b)
b_free = not place(room)
if not b_free:
print room
return b_freeprint is_tatami_free(7, 10)
