Tuesday, September 29, 2020

CryptArithmetic solver

 It had been a while since the last time I made anything. So, I took the opportunity to make a simple implementation of a CryptArithmetic problem solver in JavaScript. (Look it up on Google. Tonnes of resource on the topic) This kind of problem was brought to my attention by my brother who has to study it as part of his AI course.

The implementation is pretty basic. There's nothing fancy going on here - no clever algorithm, just pure bruteforce. It makes a list of all the unique letters of the three words given to it. Then, it assigns random digits to them with no repetitions allowed. So, there's a one-to-one correspondence between the letters and the digits. That is to say, each letter has a unique digit assigned to it - no other letter has the same digit. Also, a constraint that no letter that initiates any of the three words can be assigned 0 is imposed. Then, the letter-digit assignment is used to construct numbers for all three words and the sum is checked. If it matches, great - the process is stopped and the solution is assumed to have been found. If not, the process continues with another set of random assignments until a timeout is reached. The number crunching itself is done using a WebWorker so as to keep the UI thread responsive. The UI is basic too. I even forgot to put a textbox to specify the timeout. So that has be done in code right now. That's all there is to it.

Here's the GitHub repo and here's the demo