151 lines
5.1 KiB
Executable File

#!/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
self.end_row = row + len(word)-1
self.end_col = col
def letter_positions(self):
if self.horizontal:
for (idx, letter) in enumerate(self.word):
yield ((self.row, self.col+idx), letter)
for (idx, letter) in enumerate(self.word):
yield ((self.row+idx, self.col), letter)
def after_position(self):
if self.horizontal:
return (self.end_row, self.end_col+1)
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])
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):
grid = self.grid
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:
target_list = components[x]
target = target_list[0]
if target != x:
merge_components(target, components[y][0])
for other in list(components[y]):
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\
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),
if crossword.valid():
print('Crossword valid')
print('Crossword invalid')
if crossword.check_connected():
print('Crossword connected')
print('Crossword unconnected')