gistfile1.py

SUFFIX_DICT = set()
DICT = set()
f = open("/usr/share/dict/words")
for line in f:
    word = line.rstrip()
    DICT.add(word)
    for i in xrange(len(word)):
        SUFFIX_DICT.add(word[i:])
    

class Word:
    def __init__(self, letterset, word):
        self.letterset = letterset
        self.word = word

    @classmethod
    def cons(cls, letter, word):
        new_letterset = set(word.letterset)
        new_letterset.add(letter)
        new_word = letter.c + word.word
        return Word(new_letterset, new_word)

class BoggleLetter:
    def __init__(self, c):
        self.c = c
        self.words = []
        self.new_words = []
        self.neighbours = []
        self.words.append(Word(set([self]), self.c))

    def get_neighbours(self):
        return self.neighbours

    def make_new_words(self):
        self.new_words = [Word.cons(self,word) 
                          for letter in self.get_neighbours() 
                          for word in letter.words
                          if self not in word.letterset]

    def collapse(self):
        for w in self.new_words:
            if w.word in SUFFIX_DICT:
                self.words.append(w)
        self.new_words = []


def make_board(letters):
    print "making board..."
    bls = [[BoggleLetter(c) for c in l] for l in letters]
    print "linking up letters..."
    
    width = len(bls)
    height = len(bls[0])

    for i in xrange(width):
        for j in xrange(height):
            rmin = i - 1 if i - 1 >= 0 else 0
            rmax = i + 1 if i + 1 < width else i

            cmin = j - 1 if j - 1 >= 0 else 0
            cmax = j + 1 if j + 1 < height else j
            
            for x in xrange(rmin, rmax+1):
                for y in xrange(cmin, cmax+1):
                    if (x,y) != (i,j):
                        bls[x][y].neighbours.append(bls[i][j])
    return bls


def do_game(board, max_size):
    for i in xrange(max_size):
        for bl in board:
            for b in bl:
                b.make_new_words()
        for bl in board:
            for b in bl:
                b.collapse()

    words = set()
    for bls in board:
        for bl in bls:
            for w in bl.words:
                if len(w.word) >= 3 and w.word in DICT:
                    words.add(w.word)

    return words


if __name__ == '__main__':
    b = make_board(["dpre","tmny","ipoo","swhy"])
    words = list(do_game(b,10))
    
    words.sort()
    print "Found %s words..." % len(words)
    print words