Solve Quizzy's Word Challenge

quizzy.py

#1. The input is a list of rings. Each ring is a list of letters.
#2. Once you choose a letter from ring k then you can only choose letters from
#   ring k, k + 1, ... Outermost ring is ring 0. And ring depth increases inwards.
#3. points[k] is the points for getting the letter chr(k + ord('A'))

from bisect import bisect, bisect_left
from time import time

try:
    import psyco
    psyco.full()
except ImportError:
    pass

class Solver(object) :

	def __init__(self, ringfile, points = [1]*26, dictionary = '/usr/share/dict/words') :
		"""Setup the base. Use default scrabble scoring when points is unspecified. Use default Linux dictionary"""
		self.words = [i[:-1].upper() for i in open(dictionary) if i[:-1].isalpha()]
		self.words.sort()	#just in case
		self.points = points
		self.parse(ringfile)
        default = 'endeoatifldiolrt\naolcetee\nt'
		self.depth = len(self.rings)
		self.possibilities = []
		self.tried = set()
		self.minlength, self.maxlength = 3, 15

	def parse(self, ringfile) :
		rings = []
		for line in open(ringfile) :
			if line.strip() :
				rings += [list(line.strip().upper())]
		self.rings = [[[j, True] for j in i] for i in rings]

	def isvalid(self, word) :
		"""Check the validity of the word using binary search"""
		index = bisect(self.words, word)
		if index == 0 or self.words[index - 1] != word :
			return False
		return True

	def wordworth(self, word) :
		"""Return the points scored for 'word'"""
		ret = 0
		for letter in word :
			ret += self.points[ord(letter) - ord('A')]
		return ret

	def nowordwithstart(self, start) :
		"""If there is no word that begins with start return True."""
		index = bisect_left(self.words, start)
		try :
			if self.words[index].startswith(start) :
				return False
		except IndexError :
			return True

		return True

	def suggest(self, tillnow = '', curDepth = 0) :
		"""Recursive Depth First Search. Adds valid words to self.possibilities"""
		#not interested
		if len(tillnow) > self.maxlength or self.nowordwithstart(tillnow) or tillnow in self.tried:
			return False

		#memoize : add to the list of tried ends
		self.tried.update([tillnow])

		#if its a word then add to the list of possibilities
		if len(tillnow) >= self.minlength and self.isvalid(tillnow) :
			self.possibilities += [(self.wordworth(tillnow), tillnow)]

		#pick more letters from this ring or a deeper ring
		for i in range(curDepth, self.depth) :
			#in this depth pick a (letter, availability) pair
			for pair in self.rings[i] :
				#if the letter is availabile
				if pair[1] :
					pair[1] = False
					#recurse : find words with this as a beginning
					self.suggest(tillnow + pair[0], i)
					pair[1] = True

	def solve(self) :
		t = time()
		self.suggest()
		self.possibilities.sort(key = lambda x : x[0], reverse = True)
		for worth, word in self.possibilities : print word,
		#print 'Took %.3f seconds' % (time() - t)

if __name__ == '__main__':
	import os, sys
	if len(sys.argv) > 1 and os.path.isfile(sys.argv[1]) :
		inst = Solver(sys.argv[1])
		inst.solve()
	else :
		print 'Did you give the right filename?'
 
# example input file
# 
# endeoatifldiolrt
# aolcetee
# t