reverse boggle score.py program

score.py

#!/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())