Skip to content

Instantly share code, notes, and snippets.

@bavardage
Created December 30, 2012 23:22
Show Gist options
  • Save bavardage/4415964 to your computer and use it in GitHub Desktop.
Save bavardage/4415964 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment