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

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.

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.