Send + More = Money Purpose: Brute Force, vectors, next permutation S E N D + M

Question

Send + More = Money

Purpose: Brute Force, vectors, next permutation

S

E

N

D

+      M

O

R

E

M      O

N

E

Y

Description

In this program you will write a program to solve puzzles like the one above. In the above puzzle you are to change the letters into digits chosen from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, such that all the same letters represent the same number which makes the above equation correct. Your program should be able to handle any three word puzzle with the operations addition, subtraction, division, multiplication and exponentiation.

Input

The input will come entirely from the keyboard (stdin) and will consist of typing a puzzle. A puzzle will be on a single line containing a three strings (in capital letters). The first two strings will be separated by an operator (+, - , *) and the last two strings will be separated by a = sign. There will be a space between each string and symbol.

Output

There should be one line of output. The output will be the equation repeated with digits replacing the letters. Leading zeros should not need to be printed. If more than one solution is possible then list the one, where the first word has the lowest value. If not solution is possible write no solution

Sample Input

TO + GET = HER

CAT * CAN = NATION

Corresponding Sample Output

91 + 249 = 340

no solution

S

E

N

D

+      M

O

R

E

M      O

N

E

Y

Explanation / Answer

From column 5, M = 1 since it is the only carry-over possible from the sum of two single digit numbers in column 4. Since there is a carry in column 5, O must be less than or equal to M (from column 4). But O cannot be equal to M, so O is less than M. Therefore O = 0. Since O is 1 less than M, S is either 8 or 9 depending on whether there is a carry in column 3. But if there were a carry in column 3, N would be less than or equal to O (from column 3). This is impossible since O = 0. Therefore there is no carry in column 3 and S = 9. If there were no carry in column 3 then E = N, which is impossible. Therefore there is a carry and N = E + 1. If there were no carry in column 2, then ( N + R ) mod 10 = E, and N = E + 1, so ( E + 1 + R ) mod 10 = E which means ( 1 + R ) mod 10 = 0, so R = 9. But S = 9, so there must be a carry in column 2 so R = 8. To produce a carry in column 2, we must have D + E = 10 + Y. Y is at least 2 so D + E is at least 12. The only two pairs of available numbers that sum to at least 12 are (5,7) and (6,7) so either E = 7 or D = 7. Since N = E + 1, E can't be 7 because then N = 8 = R so D = 7. E can't be 6 because then N = 7 = D so E = 5 and N = 6. D + E = 12 so Y = 2.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.