Usage: `python CryptarithmeticSolver.py eat that apple`

CryptarithmeticSolver.py

import itertools
import sys
import time

def factorial(n):
	return reduce(int.__mul__, range(1, n+1), 1)

def main():
	words = map(str.lower, sys.argv[1:])
	uniqueLetters = set(reduce(str.__add__, words))
	
	numPermutations = (factorial(10)/factorial(10-len(uniqueLetters)))
	
	print "Estimated time: ", (1.6e-5)*numPermutations, "\n" # 1.6e-5 is the average real time per permutation on my machine
	
	startTime = time.time()
	count = 0
	
	for k in getSolutions(words, uniqueLetters):
		print k
		count += 1
	
	delta = time.time() - startTime
	print "\nRunning time: ", delta
	print "Time per permutation: ", delta/numPermutations
	print "Number of unique solutions: ", count

def wordToNumber(word, letterToDigitMapping):
	'''
		words are turned into numbers according to the dictionary passed in.
		
		# examples
		wordToNumber("abc", {'a':4, 'b':7, 'c':9}) -> 479
		wordToNumber("hats", {'h':1, 'a':0, 's':5, 't':2}) -> 1025
	'''
		
	numericEquivalents = map(letterToDigitMapping.get, word)
	return reduce(lambda x,y: x * 10 + y, numericEquivalents)

def getSolutions(words, uniqueLetters):
	'''
		Dictionaries representing solutions are yielded. The last word
		in words represents the sum.
		
		# examples
		getSolutions(["forty", "ten", "ten", "sixty"], "fortyensxi") ->
			[{'e': 5, 'f': 2, 'i': 1, 'o': 9, 'n': 0, 's': 3, 'r': 7, 't': 8, 'y': 6, 'x': 4}]
			
		getSolutions(["send", "your", "money"], "sendyourm") -> 
			[{'e': 0, 'd': 5, 'm': 1, 'o': 2, 'n': 3, 's': 8, 'r': 9, 'u': 6, 'y': 4}
			 {'e': 0, 'd': 8, 'm': 1, 'o': 2, 'n': 3, 's': 5, 'r': 9, 'u': 6, 'y': 7}
			 {'e': 0, 'd': 8, 'm': 1, 'o': 3, 'n': 4, 's': 6, 'r': 9, 'u': 5, 'y': 7}]
	'''
	for p in itertools.permutations(range(10), len(uniqueLetters)): # for each tuple in the cartesian product of {0..9}^len(uniqueCharacters), ex: (1,4,0,9,7)
		if len(p) != len(set(p)): # only solutions with unique values for each character  
			continue
			
		d = dict(zip(uniqueLetters, p)) # "eathpl" and (1,4,5,6,2,3) becomes {'e': 1, 'a': 4, ...}
		
		if 0 in map(lambda s: d.get(s[0]), words): # numbers/words can't have leading zero
			continue
		
		wordsAsNumbers = map(lambda x: wordToNumber(x, d), words)
		
		if sum(wordsAsNumbers[:-1]) == wordsAsNumbers[-1]:
			yield d
				
if __name__ == "__main__":
	main()