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 timeimport itertoolsdef timeit(fn):def wrapper():start = time.clock()ret = fn()elapsed = time.clock() - startprint("%s took %2.fs" % (fn.__name__, elapsed))return retreturn wrapper@timeitdef 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 + dmore = 1000 * m + 100 * o + 10 * r + emoney = 10000 * m + 1000 * o + 100 * n + 10 * e + yif send + more == money:return send, more, moneydef distinct(*args):return len(set(args)) == len(args)@timeitdef 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:continuesend = 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, moneyprint(solve1())print(solve2())Best Answer
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 itertoolsdef get_value(word, substitution):s = 0factor = 1for letter in reversed(word):s += factor * substitution[letter]factor *= 10return sdef solve2(equation):# split equation in left and rightleft, right = equation.lower().replace(' ', '').split('=')# split words in left partleft = left.split('+')# create list of used lettersletters = 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 = 92. check if equation can be fulfilled:2.1. if yes: set a value for the next letter and go to 22.2. if no: select next value for Sin 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 = 22. check:max = 9, min = 0compare max on left side with min on right side: 9999 + 2999 = 20000compare min on left side with max on right side: 0000 + 2000 = 29999if 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?
def isCryptSolution(crypt, solution):newsol = list(zip(*reversed(solution)))newstring1 = ''total = 0for word in range(len(crypt)-1):subtotal, sol_total = 0, 0newstring = ''for char in crypt[word]:idx = newsol[0].index(char)newstring = newstring + newsol[1][idx]subtotal = int(newstring)# if newstring[0] == '0':# return Falsetotal = total + subtotalfor char1 in crypt[-1]:nidx = newsol[0].index(char1)newstring1 = newstring1 + newsol[1][nidx]sol_total = int(newstring1)if total == sol_total and newstring[0] != '0':return Trueelif total == 0 and newstring[0] == '0' and len(newstring) == 1:return Trueelse:return Falsecrypt = ["SEND", "MORE", "MONEY"]solution = [['O', '0'],['M', '1'],['Y', '2'],['E', '5'],['N', '6'],['D', '7'],['R', '8'],['S', '9']]isCryptSolution(crypt, solution)