Trie-based Boggle solver - potential interview exercise?

boggle.py

from __future__ import print_function

import random
import string
import sys


def generate_board(width=10, height=10):
    return {
        'width': width,
        'height': height,
        'cells': [
            [random.choice(string.ascii_lowercase) for _ in range(width)]
            for _ in range(height)
            ],
        }


def print_board(board, fp=sys.stdout):
    board_string = '\n'.join([''.join(row_cells) for row_cells in board['cells']])
    print(board_string, file=fp)


def solve_board(board, dictionary):
    prefix_tree = build_prefix_tree(dictionary)

    cell_coords = [(r, c) for r in range(board['height']) for c in range(board['width'])]
    solutions = set()
    for cell in cell_coords:
        solutions |= find_words_starting_in_cell(cell, board, prefix_tree)

    non_words = list(solutions - set(dictionary))
    assert len(non_words) == 0
    return sorted(list(solutions))


def find_words_starting_in_cell((row, column), board, prefix_tree):
    words = set()
    cell_char = get_character_on_board((row, column), board)
    prefix_node = prefix_tree.subtree_map.get(cell_char)

    if not prefix_node:
        return words

    if prefix_node.word:
        words.add(prefix_node.word)

    for (adj_row, adj_column) in adjacent_spaces(board, (row, column)):
        words |= find_words_starting_in_cell((adj_row, adj_column), board, prefix_node)

    return words


def get_character_on_board((row, column), board):
    return board['cells'][row][column]


def load_dictionary(file_='/usr/share/dict/words'):
    with open(file_) as f:
        return [word.strip().lower() for word in f.readlines()]


def build_prefix_tree(dictionary):
    prefix_tree = PrefixTreeNode(None)
    for word in dictionary:
        prefix_tree.add_word(word.lower())
    return prefix_tree


def adjacent_spaces(board, (row, column)):
    unfiltered_adjacents = [
        (row - 1, column - 1),
        (row - 1, column),
        (row - 1, column + 1),
        (row, column - 1),
        (row, column + 1),
        (row + 1, column - 1),
        (row + 1, column),
        (row + 1, column + 1),
        ]

    adjacents = [(r, c) for r, c in unfiltered_adjacents
                 if 0 <= r < board['width'] and 0 <= c < board['height']]
    return adjacents


class PrefixTreeNode(object):

    def __init__(self, char):
        self.char = char
        self.word = None
        self.char = None
        self.subtree_map = {}

    def add_word(self, word):
        return self._add_word(word, word)

    def _add_word(self, word, remaining_chars):
        if not remaining_chars:
            self.word = word
            return

        char, rest = remaining_chars[0], remaining_chars[1:]
        child_node = self.subtree_map.get(char)
        if not child_node:
            child_node = PrefixTreeNode(char)
            self.subtree_map[char] = child_node
        child_node._add_word(word, rest)