0

Replace each symbol (letter) with a number so that the equations hold across all 3 equations. Solution should be able to solve the general case of any 3 equations. Can assume 2 terms summed to an answer. A recursive solution would be a bonus.

pot + pan = bib dog + cat = pig boy + girl = baby

I saw this in the book Data Structures and Algorithms in Java 6th Edition, tried to come up with a general solution, but couldn't figure it out. (Wasn't an example that would have a solution).

  • 2
    The simplest is a brute force with permutations. But you can do smarter with a few simple assumptions (like b must be ... because). – qwerty_so Dec 30 '16 at 1:25
  • 3
    What did you try? – Doc Brown Dec 30 '16 at 11:08
4
  boy
+girl
-----
 baby

You would algorithmically solve this type of problem by dividing it into 4 sets of equations: the first for the ones column, the second for the tens column, the third for the hundreds column, the forth for the thousands column. Each set would compute the sum using module-10 arithmetic (or the base of your choice), and compute the carry into the next column.

For each set of equations, you could have between 0 and 3 unknowns. With 0 unknowns, you would only check if the equation was valid. With one unknown, you could solve for the unknown directly. With 2 unknowns, you could loop through all possibilities for one of the unknowns, and compute the other. Finally, for 3 unknowns, you loop over the two unknowns and compute the third.

In the above example, the ones column has y+l=y, so we start with 2 unknowns. So you loop over the possibilities for y (0...9). Starting with y=0, solving the equation gives l=0, which doesn't work, since 0 has already been assigned, so we immediately advance to the next value y=1, and again solve l=0. At this point, we compute the carry (0), and recurse into the tens column. If that doesn't find a solution, advance to the next value of y=2 ... until y=9 is reached.

Then tens column is first entered withy=1, l=0, carry=0. The equation o+r+carry=b has 3 unknowns. So, loop over o={2,3,4,5,6,7,8,9} (8 possibilities), and r={2,3,4,5,6,7,8,9}-{o} (7 possibilities). For those 56 combinations, compute b. If b is a valid (unused) digit, compute the carry, and recurse into the hundreds.

The hundreds would first be entered with y=1, l=0, o=2, r=3, b=5, carry=0. The equation b+i+carry=a has 2 unknowns. Loop over i={4,6,7,8,9} and solve for a. If a is a valid (unused) digit, compute the carry, and recurse into the thousands.

The thousands would first be entered with y=1, l=0, o=2, r=3, b=5, i=4, a=9, carry=0. The equation g+carry=b has 1 unknown. Computing the unknown we find g=5, but that digit is already used, so we return to the previous level.

  • y has 10 possible values
  • l is computed, so
  • o then only has 8 possible values, and
  • r then only has 7 possible values,
  • b is computed, so
  • i then only has 5 possible values,
  • a is computed,
  • g is computed

This gives a maximum of 10 x 8 x 7 x 5 = 2800 loop iterations. In actuality, fewer iterations will occur as computed values result in already used digits. For example, y=0 was only explored as far as computing l=0 and immediately advancing to the next possible value for y.

You can impose further constraints on the variables, if necessary. Such as b != 0 and g != 0, since numbers generally begin with a non-zero digit.

  • @DocBrown A naive approach of 8 loops over 10 candidates would take up to 100,000,000 iterations. Iterating over all the permutations would take up to P(10,8)=1,814,400 iterations, which is roughly 100 times faster, but is more complicated. Why would you advocate your complex permutation approach over a naive implementation for a mere 100x speed up? The above approach is 1000 times faster than the permutation approach. And it is not all that complicated; the description is long because I did a verbal walk through of 4 levels of the algorithm. – AJNeufeld Dec 30 '16 at 15:54
0

Breaking it down

    left    right   
p   2   1   
a   2   1   
g   2   1   
b   1   2   
y   1   1   
ii  1   1   
y   1   1   

l   1   0   = 0
t   2   0   = 0
n   1   0   = b
o   3   0   
d   1   0   
c   1   0   
r   1   0   

Only need to solve for all combinations of o, d, c, r
Iterate through all values to see which satisfy the constraints

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.