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

∇Z←SOLVE;CHARS;SEND;MORE;MONEY;SEL [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 ∇`∇Z←PERM N;I;S;T;⎕IO`

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