Instantly share code, notes, and snippets.

# sixthgear/score.pySecret Created Jan 5, 2012

What would you like to do?
reverse boggle score.py program
 #!/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())