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

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!

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!