boggle2.py

#!/usr/bin/env python

import pygtrie as trie


board = [['x', 'y', 'd', 'o'],
         ['o', 's', 't', 'e'],
         ['m', 'p', 'g', 'i'],
         ['n', 'r', 'i', 'c']]

dictionary = trie.Trie()


def score_word(word):
    if len(word) < 3:
        return 0
    scores = {
        3: 1,
        4: 1,
        5: 2,
        6: 3,
        7: 5,
    }
    return scores.get(len(word), 11)


with open('/usr/share/dict/words', 'r') as words_file:
    for word in words_file.readlines():
        word = word.strip()
        if len(word) > 2:
            dictionary[word] = True


def neighbors(idx1, idx2):
    for d1 in [-1, 0, 1]:
        for d2 in [-1, 0, 1]:
            if d1 == 0 and d2 == 0:
                continue
            new_idx1 = idx1 + d1
            new_idx2 = idx2 + d2
            if 0 <= new_idx1 < len(board) and 0 <= new_idx2 < len(board[0]):
                yield new_idx1, new_idx2


def find_words(idx1, idx2, current_prefix='', visited=tuple()):
    visited = visited + ((idx1, idx2),)
    current_prefix += board[idx1][idx2]
    new_words = set()
    if current_prefix in dictionary:
        new_words.add(current_prefix)
    if not dictionary.has_subtrie(current_prefix):
        return new_words
    for neighbor in neighbors(idx1, idx2):
        if neighbor in visited:
            continue
        new_words |= find_words(neighbor[0], neighbor[1], current_prefix, visited)
    return new_words


def main():
    words = set()
    for idx1 in range(len(board)):
        for idx2 in range(len(board[0])):
            words |= find_words(idx1, idx2)
    for word in words:
        print word
    print "score: {}".format(sum(score_word(word) for word in words))


if __name__ == '__main__':
    main()