Revisiting Send + More = Money

In my last post I attempted to solve the Send + More = Money Cryptarithmetic problem. I didn't quite understand how I could do this quickly using a better algorithm, so I tried to find a simple brute force solution. As it turns out, that solution is actually reasonably fast, and finds the answer reliably in about 15 seconds on my machine.

Of course, I don't like computer response times that are in the seconds rather than the sub-seconds range, so I had to find a better way to get the answer. I did some searching, and I saw a lot of references to various approaches. None of them seems to be appropriate for me as a suitable solution for encoding into APL, until I found a paper on using a genetic algorithm. That gave me some inspiration based on the Hill climbing algorithms that are used in things like the N-queens problem.

Basically, I used the fitness function from the genetic algorithm paper to do a greedy local search (hill climbing) algorithm; the approach actually matches pretty closely to the genetic algorithm, but the genetic algorithm uses parallelism and a number of other things, such as multiple agents and populations. Instead, I did a straightforward local search weighted on the fitness function. To deal with the possibility of local but not global maxima, I again borrowed from the genetic algorithm to choose any random swap of two assignments.

And without further ado, here's the algorithm in a simple APL program.

     ∇Z←SOLVE∆SMM;CHARS;X;B;SEND;MORE;MONEY;OLD;CONFLICTS;SWAP;I;J;GOOD;MS
[1]  ⍝ Solve the SEND+MORE=MONEY Cryptarithmetic problem
[2]  ⍝ using local search and minimum conflict heuristics.
[3]  ⍝
[4]  ⍝ Create selection vectors for the elements
[5]  CHARS←'demnorsy'
[6]  SEND←CHARS⍳'send' ⋄ MORE←CHARS⍳'more' ⋄ MONEY←CHARS⍳'money'
[7]  MS←CHARS⍳'ms'
[8]  ⍝
[9]  ⍝ Choose a variable assignment X randomly to start with.
[10] X←(10?10)-⎕IO
[11] ⍝
[12] ⍝ Fix fitness, swap, and correctness functions
[13] ⊣⎕FX 'Z←CONFLICTS X' 'Z←(10⊥X[MONEY])-(10⊥X[MORE])+10⊥X[SEND]'
[14] ⊣⎕FX 'Z←I (X SWAP) J' 'Z←X' 'Z[I J]←Z[J I]'
[15] ⊣⎕FX 'Z←GOOD X' 'Z←0^.≠X[MS]'
[16] ⍝
[17] ⍝ Check for finished product
[18] LP:→((0^.≠X[MS])^0=CONFLICTS X)/XT
[19] ⍝
[20] ⍝ Compute the possible choices
[21] B←(GOOD¨B)/B←∪,(⍳10)∘.(X SWAP)⍳10
[22] ⍝
[23] ⍝ Take the swap that minimizes the conflicts
[24] OLD←X ⋄ X←⊃B[↑⍋|CONFLICTS¨B]
[25] →(OLD≢X)/LP ⋄ (I J)←(2?10) ⋄ X[I J]←X[J I] ⋄ →LP
[26] ⍝
[27] ⍝ We are done and complete
[28] XT:Z←2 8⍴'DEMNORSY',X[⍳8]
     ∇

Now, the real question is, how fast does this thing go? Is it faster than my brute force algorithm? I mean, they are both basically search algorithms. The answer: Yes! On this one, the timings jump because of the randomization that I use, but consistently, I get the answer back in under 100ms, and often under 50ms. Not bad!