# 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
  ⍝ Solve the send + more = money constraint problem.
  ⍝ We have eight letters to work with:
  CHARS←'demnorsy'
  ⍝ We represent our three words as index vectors into
  ⍝ CHARS
  SEND←CHARS⍳'send'
  MORE←CHARS⍳'more'
  MONEY←CHARS⍳'money'
 ⍝ to each of the eight letters, which is based on
 ⍝ the permutations of the decimal digits.
 SEL←(8⍴10)⊤∪10⊥¯1+⍉¯2↓PERM 10
 ⍝ We remove any assignment that assigns
 ⍝ S or M to 0, since these violate our constraints.
 SEL←((0≠SEL[CHARS⍳'m';])^0≠SEL[CHARS⍳'s';])/SEL
 ⍝ Now, we want to see which assignments for
 ⍝ SEND and MORE, when added up, will be equivalent
 ⍝ to the corresponding assignment to MONEY.
 Z←((10⊥SEL[MONEY;])=(10⊥SEL[SEND;])+10⊥SEL[MORE;])/SEL
 Z←⎕A[⎕a⍳CHARS]⍪1 8⍴Z
∇
```∇Z←PERM N;I;S;T;⎕IO
```
 ⎕IO←1
 ⍝ Permutations by Ram Biyani
 Z←1 0⍴I←0
 L1:→(N<I←I+1)/L2
 S←I*2
 T←(⍳I),(I-0 1)⍴(S⍴0,I⍴1)/S⍴⍳I
 Z←T[;⎕IO,1+Z]
 →L1
 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.