#!/usr/bin/python
"""
====
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."""

    # Data filenames
    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

        # Try to open the file as a pickle; if not, then import as a wordlist
        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

        # Add each letter of each >2 length word in the file to the tree
        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]

            # Adding the whole word as one entry signals the end-of-word
            d[word] = True

            # Count the number of words added
            numwords += 1

            # Track the length of the longest word
            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()
        #self.wordlist.sort()
        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()

        # Iterate over each letter in each row
        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.
        """

        # Append the current letter to the test word
        letr = self.table[i][j]
        if letr == 'q':
            testword = partword + "qu"
        else:
            testword = partword + letr

        # Add word if it is in the dict and not already in the word list
        if self.bogldict.is_word(testword) and testword not in self.wordlist:
            self.wordlist.append(testword)

        # If the test word is a valid prefix
        if self.bogldict.is_start_of_word(testword):

            # Push the current coordinate
            usedcoords.append((i, j))

            tabledim = len(self.table)

            # Check each letter starting at high-noon going clockwise
            # Be sure to not re-use a coordinate and that the coord is in-bounds
            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)

            # Pop the current coord
            usedcoords.pop()

def main():
    bogldict = BoglDict()
    while(True):
        p = BoglPlayer(bogldict)
        p.get_table()
        p.find_words()
        p.print_words()

if __name__ == "__main__":
    main()