Created
March 27, 2011 05:23
-
-
Save tylerkahn/888943 to your computer and use it in GitHub Desktop.
Usage: `python CryptarithmeticSolver.py eat that apple`
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment