Skip to content

Instantly share code, notes, and snippets.

@RyanBalfanz
Created July 30, 2013 19:27
Show Gist options
  • Save RyanBalfanz/6116053 to your computer and use it in GitHub Desktop.
Save RyanBalfanz/6116053 to your computer and use it in GitHub Desktop.
Boggle Solver in Python
2 2
R Y
A N
4 4
S N X P
P A X L
A E E Qu
N I S H
3 3
R Y A
N W A
S T O
"""
Solves a "Boggle" game board by finding all solutions.
See http://www.python.org/doc/essays/graphs.html
"""
import operator
import sys
# from collections import Counter
from collections import defaultdict
def get_words(inputFile, norm=None):
words = []
with open(inputFile, "r") as f:
for line in f:
if norm:
line = norm(line)
words.append(line)
return words
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
def path_to_word(board, path):
return "".join(board[pos[0]][pos[1]] for pos in path)
def nodes_from_board(board):
nodes = []
for i in range(len(board)):
for j in range(len(board[0])):
nodes.append((i ,j))
return nodes
def graph_from_board(board):
neighborOffsets = (
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 0), (0, 1),
(1, -1), (1, 0), (1, 1),
)
graph = {}
nodes = nodes_from_board(board)
for node in nodes:
graph[node] = []
for dn in neighborOffsets:
if dn == (0, 0):
continue
neighbor = node[0] + dn[0], node[1] + dn[1]
if (neighbor[0] >= 0 and neighbor[0] < len(board) and
neighbor[1] >= 0 and neighbor[1] < len(board[0])):
graph[node].append(neighbor)
return graph
def normalize(s):
return s.strip().lower()
def summarize_results(result):
print "Found {} unique words and {} paths".format(len(result.keys()), sum(len(v) for v in result.values()))
counts = {}
for k, v in result.iteritems():
counts[k] = len(v)
for k, v in sorted(counts.iteritems(), key=operator.itemgetter(1)):
print "{word: <15} {numSolutions}".format(word=k, numSolutions=v)
if __name__ == "__main__":
words = get_words("/usr/share/dict/words", norm=normalize)
words = dict((w, None) for w in words)
board = []
for l, line in enumerate(sys.stdin):
line = line.strip()
if not line: continue
if l == 0:
n, m = line.split()
continue
else:
board.append(line.split())
nodes = nodes_from_board(board)
graph = graph_from_board(board)
solutionDetails = defaultdict(list)
numNodes = len(nodes)
for i in range(numNodes):
for j in range(numNodes):
if i == j:
continue
start, end = nodes[i], nodes[j]
print start, end
for path in find_all_paths(graph, start, end):
# candidateWord = normalize("".join(board[pos[0]][pos[1]] for pos in path))
candidateWord = normalize(path_to_word(board, path))
if candidateWord in words:
solutionDetails[candidateWord].append(path)
print "{:0>4} {: >15}: {}".format(len(solutionDetails.keys()), candidateWord, path)
summarize_results(solutionDetails)
profile:
python -m cProfile foo.py < board_3.txt
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment