Alphametics exercise - Need help with performance

chip · February 8, 2023, 6:09pm

Hello!

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.

gist.github.com

https://gist.github.com/chip/e0a4c276d8ac2ba3b9ea860b0084bfbd

alphametics.rkt

#lang racket

(provide solve)

(define (solve puzzle)
  (define words (regexp-split #rx"==|[+]" (string-replace puzzle " " "")))
  
  (define number-set (range 10))
  
  (define individual-letters

This file has been truncated. show original

MatthijsBlom · February 8, 2023, 6:21pm

What is the error on the website?

chip · February 8, 2023, 6:40pm

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.

alterpatzer · March 12, 2023, 7:49pm

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 7.2.1.2.

chip · March 13, 2023, 2:58pm

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

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?
In your example, how do you know that the letter E in MORE is equal to 1?
Said another way: E is not 1 because the total weight = 91. Is that a correct assumption?

Thanks again for your help!

alterpatzer · March 13, 2023, 3:51pm

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.

chip · March 13, 2023, 10:46pm

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.

alterpatzer · March 14, 2023, 12:44am

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