boggle.py

#!/usr/bin/env python

from functools import partial
from random import randint, uniform
from pprint import pprint
from operator import truth, add

def build_dict_tree(filename):
    f = open(filename)
    D = {}
    for word in f:
        current = D
        for i, c in enumerate(word):
            c = c.upper()
            if c == '\n':
                current['.'] = True
            elif c in current:
                current = current[c]
            else:
                current[c] = {}
                current = current[c]
    return D

def test_dict_tree(tree, word, partial=False):
    wlen = len(word)
    for i, c in enumerate(word):
        if c in tree:
            tree = tree[c]
            if i == wlen - 1 and '.' in tree or partial and i == wlen - 1:
                return True
        else:
            return False

print "building dictionary tree...",
tree = build_dict_tree('/usr/share/dict/words')
partial_word_test = lambda (a,b): test_dict_tree(tree, a, partial=True)
full_word_test = lambda (a,b): test_dict_tree(tree, a)
print "done."

# returns the neighbors of C within the bounds 
# of an NxM 0-indexed rectangle, skipping the skip 
# coordinate.
def enumerate_nearby(M, N, C, skip=None):
    nearby = []
    x, y = C
    if x + 1 < M:
        nearby.append( (x+1, y) )
    if x > 0:
        nearby.append( (x-1, y) )
    if y + 1 < N:
        nearby.append( (x, y+1) )
    if y > 0:
        nearby.append( (x, y-1) )
    if skip:
        nearby[:] = [p for p in nearby if nearby != skip]
    return nearby

def boggle_words(B, W, depth=0, skip=None, max_depth=6):
    S, C = W
    N = len(B)
    nearby_coords = enumerate_nearby(N, N, C, skip=skip)
    nearby_strings = map(lambda (x, y): S + B[x][y], nearby_coords)
    nearby = zip(nearby_strings, nearby_coords)
    partials = filter(partial_word_test, nearby)
    words = map(lambda (a, b): a, filter(full_word_test, nearby))

    # continue with partial words
    if depth < max_depth:        
        derive_words = partial(boggle_words, B, depth=depth+1, skip=S, max_depth=max_depth)
        derived_words = filter(truth, map(derive_words, partials))
        words += reduce(add, derived_words, [])
    return words


letter_freqs = [
    (8.12, 'A'),
    (10.83, 'C'),
    (12.32, 'B'),
    (24.34, 'E'),
    (28.66, 'D'),
    (30.69, 'G'),
    (32.99, 'F'),
    (40.30, 'I'),
    (46.22, 'H'),
    (46.91, 'K'),
    (47.01, 'J'),
    (49.62, 'M'),
    (53.60, 'L'),
    (61.28, 'O'),
    (68.23, 'N'),
    (68.34, 'Q'),
    (70.16, 'P'),
    (76.44, 'S'),
    (82.46, 'R'),
    (85.34, 'U'),
    (94.44, 'T'),
    (96.53, 'W'),
    (97.64, 'V'),
    (99.75, 'Y'),
    (99.92, 'X'),
    (99.99, 'Z')
]

def generate_board(M, N):
    B = []
    for i in xrange(N):
        row = []
        for j in xrange(M):
            r = uniform(0, 100)
            for k in xrange(len(letter_freqs)):
                if r < letter_freqs[k][0] and (k == 0 or r > letter_freqs[k-1][0]):
                    row.append(letter_freqs[k][1])
        B.append(row)
    return B

def print_board(B):
    N, M = len(B), len(B[0])
    print "{:d}x{:d} board".format(N, M)
    print '--' * M
    for row in B:
        for square in row:
            print "{}".format(square),
        print
    print '--' * M

def test_boggle(N, D):
    words = False
    B = generate_board(N, N)
    print_board(B)

    while(not words):
        x, y = (randint(0, N-1), randint(0, N-1))
        W = (B[x][y], (x, y))
        words = boggle_words(B, W, max_depth=D)
    print "source: '{}' at {}".format(*W)
    print "words: {}".format(', '.join(words))

def test_max_word(N, D):
    words = False
    B = generate_board(N, N)
    print_board(B)    
    max_word_tuple = ("", 0)
    max_word_W = None
    for x in xrange(N):
        for y in xrange(N):
            W = (B[x][y], (x, y))
            words = boggle_words(B, W, max_depth=D)
            if words:
                get_len = lambda (w,l): l
                word_tuple = max(zip(words, map(len, words)), key=get_len)
                if get_len(word_tuple) > get_len(max_word_tuple):
                    max_word_tuple = word_tuple
                    max_word_W = W
    print "source: '{}' at {}".format(*max_word_W)
    print "longest word is {}, with a length of {}".format(*max_word_tuple)

# test_boggle(5, 6)
test_max_word(20, 20)