Ezra and I took 30 minutes this evening and wrote a word find puzzle solver in Python. This uses a little bit of pre-processing, sets, dictionaries, tuples, and other (less efficient) techniques to fairly quickly find the answers.
board = ''' | |
m a i n v f | |
a n a f d d | |
s m i t h a | |
i r o n r v | |
e m o z a i | |
a e e t a d | |
''' | |
words = ''' | |
ezra | |
david | |
sam | |
smith | |
iron | |
fire | |
''' | |
# use this to get a dictionary involved. | |
#words = open('dictionary.txt', 'rt').read() | |
BOARD = {} | |
x = 0 | |
y = 0 | |
for line in board.strip().split('\n'): | |
y += 1 | |
x = 0 | |
for char in line: | |
char = char.lower() | |
if char in 'abcdefghijklmnopqrstuvwxyz': | |
x += 1 | |
BOARD[x,y] = char | |
WORDS = set() | |
for line in words.strip().split('\n'): | |
word = line.strip().lower() | |
if len(word) >= 3: | |
WORDS.add(word) | |
DIREC = ( | |
(0,–1), | |
(1,–1), | |
(1,0), | |
(1,1), | |
(0,1), | |
(–1,1), | |
(–1,0), | |
(–1,–1), | |
) | |
PREFX = set() | |
FOUND = set() | |
for word in WORDS: | |
prefix = '' | |
for c in word[:–1]: | |
prefix += c | |
PREFX.add(prefix) | |
# For each position on the board | |
for x,y in BOARD: | |
# For each direction of 8 | |
for xx,yy in DIREC: | |
x1 = x #cur pos | |
y1 = y #cur pos | |
word = '' #cur word | |
while True: | |
# Check if off board | |
if (x1,y1) not in BOARD: | |
break | |
# Get character at current pos | |
word += BOARD[x1,y1] | |
# If it is a word, add it | |
if word in WORDS: | |
FOUND.add(word) | |
# If this is not a prefix, then bail out | |
if word not in PREFX: | |
break | |
# Increment current position based on direction | |
x1 += xx | |
y1 += yy | |
print(FOUND) |