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())
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?