#!/usr/bin/python
#
# Jumble example:
#	This is an example of using strings, lists and dictionaries
#	in implementing a simple puzzle solver.
#
#	Jumble is a game found in the San Francisco Chronicle.
#	The player is given letters from a word in random order
#	and the goal is to find the original word.
#
#	There are at least a couple different ways of solving
#	this problem.  For example, we can compute all permutations
#	of the given letters and check whether each one is a
#	real word.  Another is to start with a list of real
#	words and check which ones have the same letter composition
#	(fingerprint) as the given set of letters.
#
#	We are implementing the latter solution.  In our program
#	words are Python strings.  Fingerprints are Python dictionaries
#	whose keys are letters and whose values are the number
#	of occurrences of those letters (in short, a histogram).
#	The list of real words is kept in a Python dictionary
#	whose keys are the lengths of words and whose values are
#	Python lists of words of those lengths.  (The choice to
#	use word length as the key is for easy elimination of
#	words that cannot possibly match the given input.)
#
#	An interesting question is "which approach will be faster?"
#	Consider five-letter words (the statistics are similar for
#	six-letter words).  There are about 3,000 to 4,000 "real"
#	words, depending on your dictionary.  Is it faster to compute
#	the 120 (5*4*3*2*1) permutations of letters and check them
#	against a Python dictionary; or is it faster to compute
#	the fingerprints for all the "real" words and compare them
#	against the fingerprint of the given letters?
#

# Python 2/3 compatibility
from __future__ import print_function
try:
    read_input = raw_input
except NameError:
    read_input = input

#
# Main program
#
def main():
	"""Main program"""
	# Load a dictionary of words then prompt users
	# for letters that they want to "unjumble"
	load('words')	# or get a larger distionary at http://thinkpython.com/code/words.txt
	while True:
		line = read_input('Letters: ')
		characters = line.strip()
		if not characters:
			break	# blank line means quit program
		print(jumble(characters))

def jumble(w):
	"""Find a word in the dictionary with the same letters as 'w'"""
	matches = []
	n = length(w)
	fp = fingerprint(w)
	for w in wordsOfLength(n):
		if fingerprint(w) == fp:	# note that this compares two dictionaries!
			matches.append(w)
	return matches

#
# Functions for handling a dictionary of words
#
words = {}	# key is number of characters, value is list of words with that many chars

def wordsOfLength(l):
	"""Return a list wof words of requested length 'l'"""
	return words.get(l, [])

def load(filename):
	"""Load dictionary of words from a file"""
	# Only keep words of length 5 and 6 because the
	# SF Chronicle jumble only uses words of those lengths
	with open(filename) as f:
		for line in f:
			w = line.strip()
			n = length(w)
			# Only keep words of length 5 and 6 because the
			# SF Chronicle jumble only uses words of those lengths
			if n != 5 and n != 6:
				continue
			try:
				words[n].append(w)	# append another word to the list
			except KeyError:
				words[n] = [w]	# first time through, create a list with just that word
	# print('words: ', words)

#
# Functions for handling words
#
def length(word):
	"""Return number of alphabetic characters in 'word'"""
	count = 0
	for c in word:
		if c.isalpha():
			count = count + 1
	return count

def fingerprint(word):
	"""Return fingerprint (character histogram) of 'word'"""
	fp = {}
	for c in word:
		if not c.isalpha():
			continue
		c = c.lower()
		try:
			fp[c] = fp[c] + 1
		except KeyError:
			fp[c] = 1
	return fp

#
# If invoked directly (i.e., not via "import"), run the program
#
# Some words to try: lebjmu, siruv, soome, zugea, retine, timer, silly, python
#
if __name__ == '__main__':
	main()