1 min read

Send + More = Money

After talking with Prof. Friedman, he gave me an interesting constraint problem. This is a well known example of a problem well suited to constrain based techniques. The goal is to figure out what number to assign to each letter to make the equation "send + more = money" true. Each letter represents a unique decimal digit, where no two letters represent the same digit.

I know the basic idea behind the constraint problems, and it's easy enough to figure this problem out even by hand using some of these techniques. However, formulating this together into a programming description is a little harder. This is a work in progress. The following code does it the brute force way, since this problem actually has a very small problem space.

[1]  ⍝ Solve the send + more = money constraint problem.
[2]  ⍝ We have eight letters to work with:
[3]  CHARS←'demnorsy'
[4]  ⍝ We represent our three words as index vectors into
[5]  ⍝ CHARS
[6]  SEND←CHARS⍳'send'
[7]  MORE←CHARS⍳'more'
[8]  MONEY←CHARS⍳'money'
[9]  ⍝ Start with a matrix of the possible assignments
[10] ⍝ to each of the eight letters, which is based on
[11] ⍝ the permutations of the decimal digits.
[12] SEL←(8⍴10)⊤∪10⊥¯1+⍉¯2↓[2]PERM 10
[13] ⍝ We remove any assignment that assigns
[14] ⍝ S or M to 0, since these violate our constraints.
[15] SEL←((0≠SEL[CHARS⍳'m';])^0≠SEL[CHARS⍳'s';])/[2]SEL
[16] ⍝ Now, we want to see which assignments for
[17] ⍝ SEND and MORE, when added up, will be equivalent
[18] ⍝ to the corresponding assignment to MONEY.
[19] Z←((10⊥SEL[MONEY;])=(10⊥SEL[SEND;])+10⊥SEL[MORE;])/[2]SEL
[20] Z←⎕A[⎕a⍳CHARS]⍪1 8⍴Z

[1] ⎕IO←1
[2] ⍝ Permutations by Ram Biyani
[3] Z←1 0⍴I←0
[4] L1:→(N<I←I+1)/L2
[5] S←I*2
[6] T←(⍳I),(I-0 1)⍴(S⍴0,I⍴1)/S⍴⍳I
[7] Z←T[;⎕IO,1+Z]
[8] →L1
[9] L2:Z←((×/¯1↓⍴Z),¯1↑⍴Z)⍴Z

The above is about the simplest brute force method that I can figure out. I'd be interested in knowing about simpler brute force methods, and how I might actually represent a constraint problem like this inside of APL.