Today in class my professor was describing this problem. We thought about it for a while, and than he started describing the brute force solution. His code was six nested for loops. I assumed there had to be a better way to represent this problem, so I wrote a script to solve this and other similar problems.

from sets import Set
from itertools import permutations

numbers = map(str,range(9))
s = Set()

def makeWord(prompt):
    word = raw_input(prompt).upper()
    for letter in word:
        s.add(letter)
    return word

first = makeWord(" First: ")
second = makeWord("Second: ")
answer = makeWord("Answer: ")

probVars = list(s)

trials = list(permutations(numbers,len(probVars)))
print len(probVars),"letters in total, &",len(trials)," permutations."
for trial in trials:
    def buildNumber(nString):
        builtList = []
        for letter in nString:
            builtList.append(problem[letter])
        return int("".join(builtList))

    problem = {probVars[i]:trial[i] for i in range(len(trial))}

    firstNumber = buildNumber(first)
    secondNumber = buildNumber(second)
    answerNumber = buildNumber(answer)

    if(firstNumber + secondNumber == answerNumber):
        print problem

I am happy with the solution I arrived at, other than two small points. I wish I could get out of the habit of thinking of lists in terms of their indexes. You can see on line 37 where I am generating each mapping of numbers to letters, my dictionary comprehension relies on ‘range(len(trial))’. This solution also runs in n! time, but that is just because of how hard of a problem it is.

This problem is NP-Complete. This explains why it has such a high complexity. It is important to note that this problem is bounded where n<10, as you can only have that many unique letters representing unique numbers.