crossword-generator/crossword.py

#!/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')