-
-
Save sixthgear/6e5a6e396b109459388f to your computer and use it in GitHub Desktop.
reverse boggle score.py program
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# Usage: score.py dictfile < gridfile | |
# Usage: ./your_solution dictfile | score.py dictfile | |
# boggle grid scorer based on Darius Bacon's solver | |
# http://stackoverflow.com/a/750012/139022 | |
# 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: score.py dictfile < grid" | |
sys.exit(2) | |
grid = sys.stdin.read().lower().splitlines() | |
nrows, ncols = len(grid), len(grid[0]) | |
if nrows != 4 or ncols != 4: | |
print "Error: grid must have 4 rows and columns." | |
sys.exit(2) | |
# 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