Cryptarithmetic puzzle generic solution in Python 3

Question

I am stuck with this problem statement, My code does work but I used itertools.permutations and that makes it very slow. Moreover, I don't know how to make it generic for all or any input. I think I have to use backtracking but I am not use how to use it here.

Any valuable suggestion or advice or code is welcome. And yes this is an assignment and I am not asking for whole code. Thanks!

Here is problem statement:

Substitute different digits (0, 1, 2, .., 9) for different letters below, so that the corresponding addition is correct, and the resulting value of M O N E Y is as large as possible. What is the value?

SHOW + ME + THE = MONEY

There are 3 solutions satisfy the equation: 10376, 10267, 10265. Therefore, the correct one is (the largest) 10376. If there are multiple mappings evaluating to the same maximum value, output all of them.

The assignment:

Write a program in Python, which can always find the correct solution for this kind of problem.

import time
import itertools


def timeit(fn):
    def wrapper():
        start = time.clock()
        ret = fn()
        elapsed = time.clock() - start
        print("%s took %2.fs" % (fn.__name__, elapsed))
        return ret
    return wrapper


@timeit
def solve1():
    for s in range(1, 10):
        for e in range(0, 10):
            for n in range(0, 10):
                for d in range(0, 10):
                    for m in range(1, 10):
                        for o in range(0, 10):
                            for r in range(0, 10):
                                for y in range(0, 10):
                                    if distinct(s, e, n, d, m, o, r, y):
                                        send = 1000 * s + 100 * e + 10 * n + d
                                        more = 1000 * m + 100 * o + 10 * r + e
                                        money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
                                        if send + more == money:
                                            return send, more, money


def distinct(*args):
    return len(set(args)) == len(args)


@timeit
def solve2():
    #letters = input("Enter your string: ")
    #letters1 = list(letters)
    letters = ('s', 'h', 'o', 'w', 'm', 'e', 't')
    digits = range(10)
    for perm in itertools.permutations(digits, len(letters)):
        sol = dict(zip(letters, perm))
        if sol['s'] == 0 or sol['m'] == 0:
            continue
        send = 1000 * sol['s'] + 100 * sol['e'] + 10 * sol['n'] + sol['d']
        more = 1000 * sol['m'] + 100 * sol['o'] + 10 * sol['r'] + sol['e']
        money = 10000 * sol['m'] + 1000 * sol['o'] + 100 * sol['n'] + 10 * sol['e'] + sol['y']
        if send + more == money:
            return send, more, money


print(solve1())
print(solve2())

Answer 1

I took your solve2 method as a starting point and implemented a simple parser for equations 'word [+ word]*n = word'. The function get_value computes the resulting integer value after substituting all letters in word with their associated numbers. The rest is just going through the permutations like you did and comparing the sum of left words with the right word.

Here's the code:

import itertools


def get_value(word, substitution):
    s = 0
    factor = 1
    for letter in reversed(word):
        s += factor * substitution[letter]
        factor *= 10
    return s


def solve2(equation):
    # split equation in left and right
    left, right = equation.lower().replace(' ', '').split('=')
    # split words in left part
    left = left.split('+')
    # create list of used letters
    letters = set(right)
    for word in left:
        for letter in word:
            letters.add(letter)
    letters = list(letters)

    digits = range(10)
    for perm in itertools.permutations(digits, len(letters)):
        sol = dict(zip(letters, perm))

        if sum(get_value(word, sol) for word in left) == get_value(right, sol):
            print(' + '.join(str(get_value(word, sol)) for word in left) + " = {} (mapping: {})".format(get_value(right, sol), sol))

if __name__ == '__main__':
    solve2('SEND + MORE = MONEY')

If you're only interested in the maximum value for the right word, you can change the permutation that it starts with the highest number for the right word (e.g. 98765 for MONEY) and goes down one by one until it finds the first match.

Backtracking

OK, the idea here would be to build up the substitutions one by one and check if the equation can be fulfilled between each step.

For example:
1. set S = 9
2. check if equation can be fulfilled:
    2.1. if yes: set a value for the next letter and go to 2
    2.2. if no: select next value for S

in this case, checking whether the equation can be fulfilled is not so easy.

i'd try the following:

min: minimum value in range(10) that has not been used for a substitution so far

max: maximum value in range(10) that has not been used for a substitution so far

substitute every letter on the left side that has not been substituted so far with the min/max value and compare the sum with the number of the right side after substituting with the max/min value.

Example:
equation = 'SEND + MORE = MONEY'
1. substitute M = 2
2. check:
   max = 9, min = 0
   compare max on left side with min on right side: 9999 + 2999 = 20000
   compare min on left side with max on right side: 0000 + 2000 = 29999
   if max_left < min_right or min_left > max_right:
       the current chosen substitutions (M = 2 in this example) can not lead to a valid solution. 

Do you get the idea?