Alphametics exercise - Need help with performance


I submitted a solution to this exercise (which passes all tests on my local) but fails on Exercism. If anyone has suggestions for improving the algorithm/performance I’d very much appreciate it. Thanks in advance. :smile:

What is the error on the website?

Your tests timed out. This might mean that there was an issue in our infrastructure, but more likely it suggests that your code is running slowly. Is there an infinite loop or something similar?

Please check your code, and if nothing seems to be wrong, try running the tests again.

One way to get a big speedup is to precompute the total “weight” of each letter instead of evaluating each addend on every permutation. For instance, in “SEND + MORE == MONEY”, the E in SEND contributes 100, the E in MORE contributes 1 and the E in MONEY contributes -10 (negative because it is on the RHS). So the total weight of E is 100 + 1 - 10 = 91. Then for each permutation, do the dot product of the weights and the letter values and see if the result is zero. This is especially helpful on the big puzzle with 199 addends. Knuth discusses this approach in TAOCP

Thank you so much for your suggestion! A few questions…

  1. I understand a dot product of x-y coordinates, but not of an alphametics puzzle. Would you please provide an example of what you mean?

  2. In your example, how do you know that the letter E in MORE is equal to 1?

  3. Said another way: E is not 1 because the total weight = 91. Is that a correct assumption?

Thanks again for your help!

I was probably a little too cryptic. When I say that E has a weight of 91, I mean that it contributes 91E to the sum, e.g., 91 if E = 1, 182 if E = 2, etc. In the word MORE, E is in the units place, so that occurrence contributes 1E. If we work out all of the weights for SEND + MORE == MONEY, we see that they are (S: 1000, E: 91, N: -90, D: 1, M: -9000, O: -900, R: 10, Y: -1) and when we try the assignments S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2, we find that 1000 * 9 + 91 * 5 - 90 * 6 + 1 * 7 - 9000 * 1 - 900 * 0 + 10 * 8 - 1 * 2 == 0,
so this is a solution. That is what I meant by computing the dot product.

Thank you, that makes a little bit more sense. However, I’m still struggling a bit. Would you mind giving me specific suggestions on how to get started using the Gist I posted originally? Anything would help. Thanks in advance.

The main thing is that instead of having make-equation assign a value to each word and then adding them up, you want to get the sum of all the words at once using the letter weights. This makes the cost proportional to the number of distinct letters. The cost of your current approach depends on the number of words, which will kill you when you try to solve the very long puzzle.

I also notice that you return the first solution that you find, but the problem actually requires that you only return a solution if there is exactly one of them.

If you are interested, my solution is here