Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/env python3
# change params here
N = 3
M = 3
PRINT_UNIQUE_ANSWERS = True
##############################################################################
def transpose(grid):
return tuple(zip(*grid))
def rotate(grid):
return transpose(reversed(grid))
class Grid(object):
@staticmethod
def slot(n, m):
return 2*n*m - n - m
def __init__(self, n, m):
self.n, self.m = sorted([n, m])
self.grid = [['. '[i%2 or j%2] for j in range(2*self.m-1)] for i in range(2*self.n-1)]
def __str__(self):
return '\n'.join(''.join(row) for row in self.grid)
def iter_line(self):
for i in range(2*self.n-1):
for j in range(2*self.m-1):
if i % 2 ^ j % 2:
yield i, j
def iter_cell(self):
for i in range(2*self.n-1):
for j in range(2*self.m-1):
if i % 2 != 0 and j % 2 != 0:
yield i, j
def load(self, config):
for c, (i, j) in zip(config, self.iter_line()):
self.grid[i][j] = ' X'[c]
return self
def conflict_cell(self, i, j):
return sum(self.grid[x][y] != ' ' for x, y in ((i-1,j), (i,j-1), (i+1,j), (i,j+1))) >= 3
def fillable_line(self, i, j):
if self.grid[i][j] != ' ':
return False
if i % 2 == 0:
if i > 0:
if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j-1), (i-2,j), (i-1,j+1))) >= 2:
return False
if i < 2*self.n-2:
if sum(self.grid[x][y] != ' ' for x, y in ((i+1,j-1), (i+2,j), (i+1,j+1))) >= 2:
return False
return True
else:
if j > 0:
if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j-1), (i,j-2), (i+1,j-1))) >= 2:
return False
if j < 2*self.m-2:
if sum(self.grid[x][y] != ' ' for x, y in ((i-1,j+1), (i,j+2), (i+1,j+1))) >= 2:
return False
return True
return
def is_final(self):
return ( all(not self.conflict_cell(i, j) for i, j in self.iter_cell())
and all(not self.fillable_line(i, j) for i, j in self.iter_line()) )
def is_unique(self, answers):
tg = transpose(self.grid)
for _ in range(2):
for _ in range(4):
if tg in answers:
return False
tg = rotate(tg)
tg = transpose(tg)
return True
def compact_show(g):
for row in g:
print(''.join(row))
def cleary_show(g, hscale=5, vscale=3):
for i, row in enumerate(g):
display_row = ''.join((1 if j % 2 == 0 else hscale)*cell for j, cell in enumerate(row))
print(display_row)
if i % 2 != 0:
for _ in range(vscale-1):
print(display_row)
##############################################################################
slot = Grid.slot(N, M)
print(f'There are {2**slot:,} tasks to test.')
answers = []
for i in range(2**slot):
if i % 2**16 == 0: print(f'progress: {i:,}/{2**slot:,}')
config = [x == '1' for x in format(i, f'0{slot}b')]
g = Grid(N, M).load(config)
if g.is_final():
answers += [g]
print('All possible answers are:', len(answers))
unique_answers = set()
for g in answers:
if g.is_unique(unique_answers):
unique_answers |= {transpose(transpose(g.grid))}
print('Only unique answers are:', len(unique_answers))
if PRINT_UNIQUE_ANSWERS:
print()
print()
print()
for i, g in enumerate(sorted(unique_answers)):
print('====', i, '==================================================')
print()
cleary_show(g)
print()
print()
print()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment