You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
151 lines
5.1 KiB
Python
151 lines
5.1 KiB
Python
#!/usr/bin/env python3
|
|
|
|
class CrosswordClue(object):
|
|
def __init__(self, word, horizontal, row, col):
|
|
self.word = word
|
|
self.horizontal = horizontal
|
|
self.row = row
|
|
self.col = col
|
|
|
|
if horizontal:
|
|
self.end_row = row
|
|
self.end_col = col + len(word)-1
|
|
else:
|
|
self.end_row = row + len(word)-1
|
|
self.end_col = col
|
|
|
|
@property
|
|
def letter_positions(self):
|
|
if self.horizontal:
|
|
for (idx, letter) in enumerate(self.word):
|
|
yield ((self.row, self.col+idx), letter)
|
|
else:
|
|
for (idx, letter) in enumerate(self.word):
|
|
yield ((self.row+idx, self.col), letter)
|
|
|
|
@property
|
|
def after_position(self):
|
|
if self.horizontal:
|
|
return (self.end_row, self.end_col+1)
|
|
else:
|
|
return (self.end_row+1, self.end_col)
|
|
|
|
def __repr__(self):
|
|
return "CrosswordClue({self.word!r}, {self.horizontal!r}, {self.row!r}, {self.col!r})".format(self=self)
|
|
|
|
|
|
class Crossword(object):
|
|
def __init__(self, clues):
|
|
self.clues = clues
|
|
|
|
self.min_row = min([c.row for c in clues])
|
|
self.min_col = min([c.col for c in clues])
|
|
self.max_row = max([c.end_row for c in clues])
|
|
self.max_col = max([c.end_col for c in clues])
|
|
|
|
self.width = self.max_col + 1
|
|
self.height = self.max_row + 1
|
|
|
|
def __repr__(self):
|
|
return "Crossword({self.clues!r})".format(self=self)
|
|
|
|
def __str__(self):
|
|
return '\n'.join([''.join([(letter or '_') for letter in row]) for row in self.grid])
|
|
|
|
@property
|
|
def grid(self):
|
|
grid = [[None for col in range(self.width)]
|
|
for row in range(self.height)]
|
|
for clue in self.clues:
|
|
for ((row, col), letter) in clue.letter_positions:
|
|
if grid[row][col] is not None and \
|
|
letter != grid[row][col]:
|
|
raise Exception("Collision at ({row}, {col}): {existing_letter} and {letter} from {clue}".format(row=row, col=row, existing_letter=grid[row][col], letter=letter, clue=clue))
|
|
grid[row][col] = letter
|
|
return grid
|
|
|
|
def valid(self):
|
|
try:
|
|
grid = self.grid
|
|
except:
|
|
return False
|
|
|
|
clues_map = {(clue.row, clue.col, clue.horizontal): clue
|
|
for clue in self.clues}
|
|
|
|
for clue in self.clues:
|
|
(after_row, after_col) = clue.after_position
|
|
if after_row < self.height and after_col < self.width:
|
|
if grid[after_row][after_col] is not None:
|
|
return False
|
|
|
|
# Check horizontal clues exist
|
|
for row in range(len(grid)):
|
|
for col in range(len(grid[0])-1):
|
|
if (col == 0 or grid[row][col-1] is None)\
|
|
and grid[row][col] is not None\
|
|
and grid[row][col+1] is not None\
|
|
and (row, col, True) not in clues_map:
|
|
return False
|
|
|
|
# Check vertical clues exist
|
|
for col in range(len(grid[0])-1):
|
|
for row in range(len(grid)-1):
|
|
if (row == 0 or grid[row-1][col] is None)\
|
|
and grid[row][col] is not None\
|
|
and grid[row+1][col] is not None\
|
|
and (row, col, False) not in clues_map:
|
|
return False
|
|
|
|
return True
|
|
|
|
def check_connected(self):
|
|
components = {clue: [clue] for clue in self.clues}
|
|
|
|
def merge_components(x, y):
|
|
if x == y:
|
|
return
|
|
target_list = components[x]
|
|
target = target_list[0]
|
|
if target != x:
|
|
merge_components(target, components[y][0])
|
|
else:
|
|
for other in list(components[y]):
|
|
target_list.append(other)
|
|
components[other] = target_list
|
|
|
|
clue_letter_positions = [(clue, set(clue.letter_positions))
|
|
for clue in self.clues]
|
|
for (clue, letter_positions) in clue_letter_positions:
|
|
for (other, other_letter_positions) in clue_letter_positions:
|
|
if clue != other\
|
|
and not letter_positions\
|
|
.isdisjoint(other_letter_positions):
|
|
merge_components(clue, other)
|
|
|
|
component = components[self.clues[0]]
|
|
for l in components.values():
|
|
if l != component:
|
|
return False
|
|
return True
|
|
|
|
|
|
if __name__ == '__main__':
|
|
crossword = Crossword([
|
|
CrosswordClue('hello', True, 0, 0),
|
|
CrosswordClue('hell', False, 0, 0),
|
|
CrosswordClue('leaf', True, 2, 0),
|
|
CrosswordClue('lifer', False, 0, 3),
|
|
CrosswordClue('olive', False, 0, 4),
|
|
])
|
|
print(repr(crossword))
|
|
print(crossword)
|
|
if crossword.valid():
|
|
print('Crossword valid')
|
|
else:
|
|
print('Crossword invalid')
|
|
if crossword.check_connected():
|
|
print('Crossword connected')
|
|
else:
|
|
print('Crossword unconnected')
|