"""
====
Bogl
====
A Boggle Board Solver in Python
===============================
:Author: Dean Hall
:Date: 2005/08/30
Classes to brute-force search for all words on a Boggle board. BoglDict is
used to create and use a Dictionary containing official Scrabble (tm) words.
BoglPlayer accepts table input, performs the search algorithm and prints the
results.
Generates a 27-ary tree for word lookup.
Looks up whole word or first-N letters.
Imports/exports tree struct.
Scrabble Dictionary comes from::
http://www.dcs.shef.ac.uk/research/ilash/Moby/mwords.html
Command line Usage::
> python bogl.py
Interactive Usage::
>>> import bogl
>>> p = bogl.BoglPlayer()
>>> p.get_table()
>>> p.find_words()
>>> p.print_words()
Building the dictionary (2-letter words filtered out)::
>>> bd = bogl.BoglDict('113809of.fic')
File (113809of.fic) is a word list.
>>> bd.numwords
113724
>>> bd.append_from_word_list(open('4160offi.cia','r'))
>>> bd.numwords
117875
>>> bd.export_dict(open("bogldict.pkl",'wb'))
"""
import cPickle
class BoglDict(object):
"""A 27-ary tree for per-character word lookup."""
boglDictFn = "bogldict.pkl"
wordList1Fn = "113809of.fic"
wordList2Fn = "4160offi.cia"
def __init__(self, fn = boglDictFn):
"""Create an initial tree using data from fn.
fn must contain a word list or a pickled tree.
"""
self.tree = {}
self.longest = 0
self.numwords = 0
f = open(fn, 'r')
try:
self.tree, self.longest, self.numwords = cPickle.load(f)
print "File (%s) is a pickle file." % fn
except Exception, e:
self.append_from_word_list(f)
print "File (%s) is a word list." % fn
def append_from_word_list(self, f):
"""Appends entries to the tree using the words in the given file"""
longest = self.longest
numwords = self.numwords
for word in f.read().splitlines():
if len(word) < 3:
continue
d = self.tree
for letr in word:
if not d.has_key(letr):
d[letr] = {}
d = d[letr]
d[word] = True
numwords += 1
l = len(word)
if l > longest:
longest = l
self.numwords = numwords
self.longest = longest
def is_start_of_word(self, word):
"""Returns true if partial word is in the tree"""
d = self.tree
for letr in word:
if not d.has_key(letr):
return False
d = d[letr]
return True
def is_word(self, word):
"""Returns true if word is in the tree with an end-of-word marker"""
d = self.tree
for letr in word:
if not d.has_key(letr):
return False
d = d[letr]
return d.has_key(word) and d[word] == True
def export_dict(self, f):
"""Writes the tree as a pickle to the given file object"""
cPickle.dump((self.tree, self.longest, self.numwords), f, True)
class BoglPlayer(object):
"""Methods to create list of valid words from entry"""
def __init__(self, bogldict=None):
"""Load the dictionary (create it if needed)"""
self.table = []
self.wordlist = []
self.bogldict = bogldict or BoglDict()
def get_table(self,):
"""Ask for and store the letters"""
print "Enter letters one row at a time, no spaces."
t = []
i = 1
tabledim = 10
while i <= tabledim:
row = raw_input("Enter row %d > " % i)
if i == 1: tabledim = len(row)
else: assert len(row) == tabledim
t.append(tuple(row))
i += 1
self.table = t
def print_words(self,):
"""Find and print the words"""
if not self.wordlist:
self.find_words()
print self.wordlist
def find_words(self,):
"""Find words in the table that are also in the dict"""
tabledim = len(self.table)
self.wordlist = []
if not self.table:
self.get_table()
check_words = self.check_words
for i in range(tabledim):
for j in range(tabledim):
check_words(i, j, "", [])
print "Found %d words." % len(self.wordlist)
def check_words(self, i, j, partword, usedcoords):
"""Add the current word to the wordlist if it is in the dictionary and
recursively check the word formed by appending the neighboring letter
in all 8 directions being sure not to reuse any coordinate.
"""
letr = self.table[i][j]
if letr == 'q':
testword = partword + "qu"
else:
testword = partword + letr
if self.bogldict.is_word(testword) and testword not in self.wordlist:
self.wordlist.append(testword)
if self.bogldict.is_start_of_word(testword):
usedcoords.append((i, j))
tabledim = len(self.table)
check_words = self.check_words
if (i , j-1) not in usedcoords and j-1 >= 0:
check_words(i , j-1, testword, usedcoords)
if (i+1, j-1) not in usedcoords and i+1 < tabledim and j-1 >= 0:
check_words(i+1, j-1, testword, usedcoords)
if (i+1, j ) not in usedcoords and i+1 < tabledim:
check_words(i+1, j , testword, usedcoords)
if (i+1, j+1) not in usedcoords and i+1 < tabledim and j+1 < tabledim:
check_words(i+1, j+1, testword, usedcoords)
if (i , j+1) not in usedcoords and j+1 < tabledim:
check_words(i , j+1, testword, usedcoords)
if (i-1, j+1) not in usedcoords and i-1 >= 0 and j+1 < tabledim:
check_words(i-1, j+1, testword, usedcoords)
if (i-1, j ) not in usedcoords and i-1 >= 0:
check_words(i-1, j , testword, usedcoords)
if (i-1, j-1) not in usedcoords and i-1 >= 0 and j-1 >= 0:
check_words(i-1, j-1, testword, usedcoords)
usedcoords.pop()
def main():
bogldict = BoglDict()
while(True):
p = BoglPlayer(bogldict)
p.get_table()
p.find_words()
p.print_words()
if __name__ == "__main__":
main()