boggle.py

from random import choice

BOARD_SIZE = 5


class Node:
    def __init__(self):
        self.value = 0
        self.children = {}


class DictTrie:
    def __init__(self):
        self.root = Node()
        self._length_to_value = {
            1: 0, 2: 0, 3: 1, 4: 1, 5: 2, 6: 3, 7: 5
        }

        with open('/usr/share/dict/words', 'r') as f:
            dictionary = f.read()

        for word in dictionary.split():
            word = word.strip().lower()
            self.insert(word)

    def insert(self, key):
        value = self._length_to_value.get(len(key), 11)
        node = self.root

        for c in key:
            if c not in node.children:
                node.children[c] = Node()

            node = node.children[c]

        node.value = value

    def find(self, key):
        node = self.root

        for c in key:
            if c not in node.children:
                return None

            node = node.children[c]

        return node.value


class Die:
    def __init__(self, values):
        self.values = values
        self.current = None
        self.roll()

    def roll(self):
        self.current = choice(self.values)


class Board:
    def __init__(self):
        self.dice = [
            [Die('qbzjxk'), Die('touoto'), Die('ovwrgr'), Die('aaafsr'), Die('aaafsr')],
            [Die('hhlrdo'), Die('nhdtho'), Die('lhnrod'), Die('afaisr'), Die('yifasr')],
            [Die('telpci'), Die('ssnseu'), Die('riyprh'), Die('dordln'), Die('ccwnst')],
            [Die('ttotem'), Die('sctiep'), Die('eandnn'), Die('mnneag'), Die('uotown')],
            [Die('aeaeee'), Die('yifpsr'), Die('eeeema'), Die('ititie'), Die('etilic')]
        ]

    def reshuffle(self):
        for row in self.dice:
            for die in row:
                die.roll()


class Solver:
    def __init__(self, board):
        self.letter_grid = [[die.current for die in row] for row in board.dice]
        self.trie = DictTrie()

    def neighbors(self, x, y, visited):
        ns = []

        for i in range(max(0, x-1), min(BOARD_SIZE, x+2)):
            for j in range(max(0, y-1), min(BOARD_SIZE, y+2)):
                if (i, j) not in visited:
                    ns.append((i, j))

        return ns

    def find_words(self, x, y, prefix, visited):
        current_letter = self.letter_grid[x][y]
        visited.append((x, y))

        prefix += current_letter
        value = self.trie.find(prefix)

        if value is None:
            return 0
        elif value != 0:
            print('Found word "{}"'.format(prefix))

        return value + sum([
            self.find_words(i, j, prefix, visited[:]) for (i, j) in self.neighbors(x, y, visited)
        ])

    def solve(self):
        for row in self.letter_grid:
            print(row)
        total_points = 0

        for x in range(BOARD_SIZE):
            for y in range(BOARD_SIZE):
                visited = []
                prefix = ''
                total_points += self.find_words(x, y, prefix, visited)

        return total_points


if __name__ == '__main__':
    board = Board()
    solver = Solver(board)
    total = solver.solve()
    print('Total score = {}'.format(total))