Create a gist now

Instantly share code, notes, and snippets.

@sixthgear / Secret
Created Jan 5, 2012

What would you like to do?
reverse boggle program
#!/usr/bin/env python
# Usage: dictfile < gridfile
# Usage: ./your_solution dictfile | dictfile
# boggle grid scorer based on Darius Bacon's solver
# simple scoring and stdin reading added.
import sys
import re
def neighbors((x, y)):
for nx in range(max(0, x-1), min(ncols, x+2)):
for ny in range(max(0, y-1), min(nrows, y+2)):
yield (nx, ny)
def extending(prefix, path):
if prefix in words:
yield (prefix, path)
for (nx, ny) in neighbors(path[-1]):
if (nx, ny) not in path:
prefix1 = prefix + grid[ny][nx]
if prefix1 in prefixes:
for result in extending(prefix1, path + ((nx, ny),)):
yield result
def solve():
for y, row in enumerate(grid):
for x, prefix in enumerate(row):
for result in extending(prefix, ((x, y),)):
yield result
if len(sys.argv) < 2:
print "Usage: dictfile < grid"
grid =
nrows, ncols = len(grid), len(grid[0])
if nrows != 4 or ncols != 4:
print "Error: grid must have 4 rows and columns."
# A dictionary word that could be a solution must use only the grid's letters
# and have length >= 3. (With a case-insensitive match.)
alphabet = ''.join(set(''.join(grid)))
possible_solution = re.compile('[' + alphabet + ']{3,}$', re.I)
words = set(word.lower()
for word in open(sys.argv[1]).read().splitlines()
if possible_solution.match(word))
prefixes = set(word[:i]
for word in words
for i in range(2, len(word)+1))
solutions = {}
for s in solve():
solutions[s[0]] = len(s[1])
print sum(solutions.values())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment