import time
def word_candidates(board):
"""
>>> for cand in word_candidates(['ab']):
... print(cand)
a
ab
b
ba
"""
for y, row in enumerate(board):
for x, c in enumerate(row):
cands = candidates(board, y, x, visited=set([(y, x)]), candidate=c)
for cand in cands: break
while True:
try:
cand = cands.send((yield cand))
except StopIteration:
break
def candidates(board, row, col, visited, candidate=''):
if (yield candidate):
return
for c, (y, x) in unvisited_neighbors(board, visited, row, col):
visited.add((y, x))
cands = candidates(board, y, x, visited, candidate+c)
for cand in cands: break
while True:
try:
cand = cands.send((yield cand))
except StopIteration:
break
visited.remove((y, x))
def unvisited_neighbors(board, visited, row, col):
"""
>>> unvisited_neighbors(['abc', 'def'], set([(0, 0), (0, 1)]), 0, 0)
[('d', (1, 0)), ('e', (1, 1))]
"""
return [(board[y][x], (y, x))
for y, x in [(row + dy, col + dx)
for dx in [-1, 0, 1]
for dy in [-1, 0, 1]]
if -1 < y < len(board) and -1 < x < len(board[0]) and (y, x) not in visited]
class Trie(object):
"""
>>> t = Trie()
>>> t.add('hi')
>>> t.add('hello')
>>> list(t.data.keys())
['h']
>>> print(t.display())
h
e
l
l
O
I
<BLANKLINE>
>>> t.add('bad')
>>> t.add('ad')
>>> 'hello' in t
True
"""
def __init__(self):
self.data = {}
self.is_word = False
def add(self, word):
cur = self
for c in word:
if c not in cur.data:
cur.data[c] = Trie()
cur = cur.data[c]
cur.is_word = True
def has_children(self, word):
if len(word) == 0:
return bool(self.data)
if word[0] in self.data:
return self.data[word[0]].has_children(word[1:])
return False
def display(self, indent=0):
s = '\n' if indent else ''
for c, t in sorted(self.data.items()):
s += ' '* indent + (c.upper() if self.data[c].is_word else c.lower()) + t.display(indent+1)
return s
def __getitem__(self, word):
if len(word) == 0:
return self
return self.data[word[0]][word[1:]]
def __contains__(self, word):
if len(word) == 0:
return self.is_word
if word[0] not in self.data:
return False
return word[1:] in self.data[word[0]]
@classmethod
def from_words(cls):
t = Trie()
for word in open('/usr/share/dict/words'):
t.add(word.strip())
return t
if __name__ == '__main__':
import doctest
doctest.testmod()
board = ['abcd',
'efgh',
'ijkl',
'mnop']
t0 = time.time()
t = Trie.from_words()
t_trie = time.time() - t0
t0 = time.time()
w = word_candidates(board)
candidate = next(w)
while True:
if candidate in t:
print(candidate)
try:
candidate = w.send(not t.has_children(candidate))
except StopIteration:
break
print(t_trie)
print(time.time() - t0, 'seconds spent searching the boggle board')
|
import time
def word_candidates(board):
"""
>>> for cand in word_candidates(['ab']):
... print(cand)
a
ab
b
ba
"""
for y, row in enumerate(board):
for x, c in enumerate(row):
yield from candidates(board, y, x, visited=set([(y, x)]), candidate=c)
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
def candidates(board, row, col, visited, candidate=''):
if (yield candidate):
return
for c, (y, x) in unvisited_neighbors(board, visited, row, col):
visited.add((y, x))
yield from candidates(board, y, x, visited, candidate+c)
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
visited.remove((y, x))
def unvisited_neighbors(board, visited, row, col):
"""
>>> unvisited_neighbors(['abc', 'def'], set([(0, 0), (0, 1)]), 0, 0)
[('d', (1, 0)), ('e', (1, 1))]
"""
return [(board[y][x], (y, x))
for y, x in [(row + dy, col + dx)
for dx in [-1, 0, 1]
for dy in [-1, 0, 1]]
if -1 < y < len(board) and -1 < x < len(board[0]) and (y, x) not in visited]
class Trie(object):
"""
>>> t = Trie()
>>> t.add('hi')
>>> t.add('hello')
>>> list(t.data.keys())
['h']
>>> print(t.display())
h
e
l
l
O
I
<BLANKLINE>
>>> t.add('bad')
>>> t.add('ad')
>>> 'hello' in t
True
"""
def __init__(self):
self.data = {}
self.is_word = False
def add(self, word):
cur = self
for c in word:
if c not in cur.data:
cur.data[c] = Trie()
cur = cur.data[c]
cur.is_word = True
def has_children(self, word):
if len(word) == 0:
return bool(self.data)
if word[0] in self.data:
return self.data[word[0]].has_children(word[1:])
return False
def display(self, indent=0):
s = '\n' if indent else ''
for c, t in sorted(self.data.items()):
s += ' '* indent + (c.upper() if self.data[c].is_word else c.lower()) + t.display(indent+1)
return s
def __getitem__(self, word):
if len(word) == 0:
return self
return self.data[word[0]][word[1:]]
def __contains__(self, word):
if len(word) == 0:
return self.is_word
if word[0] not in self.data:
return False
return word[1:] in self.data[word[0]]
@classmethod
def from_words(cls):
t = Trie()
for word in open('/usr/share/dict/words'):
t.add(word.strip())
return t
if __name__ == '__main__':
import doctest
doctest.testmod()
board = ['abcd',
'efgh',
'ijkl',
'mnop']
t0 = time.time()
t = Trie.from_words()
t_trie = time.time() - t0
t0 = time.time()
w = word_candidates(board)
candidate = next(w)
while True:
if candidate in t:
print(candidate)
try:
candidate = w.send(not t.has_children(candidate))
except StopIteration:
break
print(t_trie)
print(time.time() - t0, 'seconds spent searching the boggle board')
|