6

Say you are given the crypt-arithmetic puzzle:

SEND + MORE = MONEY

The goal is to substitute numbers (0-9) for letters, so that the addition works out.

I understand how to approach the problem mathematically, but I am not sure how to solve this with a Relational Database.

How would a schema be designed to approach this problem?

How would an SQL query look that would attempt to solve this problem?

EDIT: There are some constraints:

  1. The same number should be used for a given letter, throughout. For example, if you guess "5" for the letter E, then E should get the value "5" at all the places it occurs.
  2. Different letters should get different numbers, e.g., you cannot assign "4" to both E and to M.
  3. None of the numbers(words) may have any leading zeroes
9
  • Is there a max limit to the length of the words?
    – user849425
    Commented Feb 27, 2013 at 4:33
  • There will only be one puzzle to solve at a time so tables can be created/modified specifically for that attempt. The puzzles will all be of the format length(4) + length(4) = length(5)
    – wilco
    Commented Feb 27, 2013 at 4:41
  • 1
    Your first edit is impossible, there are more than 10 different letters. Each cannot have its own digit Commented Feb 27, 2013 at 5:02
  • The letters are not multiplied together. They are concatenated to form 1 long integer. O=1,V=2,E=3,R=4 ==> 1234
    – wilco
    Commented Feb 27, 2013 at 5:02
  • That stipulation may be impossible for the equation I provided because I altered the actual problem just for StackOverflow. The actual problem is SEND + MORE = MONEY
    – wilco
    Commented Feb 27, 2013 at 5:07

2 Answers 2

7

This answers the other problem posed by the user.

SEND + MORE = MONEY where each character has a unique digit and no word starts with zero.

select
    top 1
    S.num as S,
    E.num as E,
    N.num as N,
    D.num as D,
    M.num as M,
    O.num as O,
    R.num as R,
    Y.num as Y,
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num) as [SEND],
    (M.num * 1000 + O.num * 100 + R.num * 10 + E.num) as MORE,
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num) + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num) as SEND_plus_MORE,
    (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num) as [MONEY]

from
    Digits as S
    join digits as E on E.num <> S.num
    join digits as N on N.num <> S.num and N.num <> E.num
    join digits as D on D.num <> S.num and D.num <> E.num and D.num <> N.num
    join digits as M on M.num <> S.num and M.num <> E.num and M.num <> N.num and M.num <> D.num
    join digits as O on O.num <> S.num and O.num <> E.num and O.num <> N.num and O.num <> D.num and O.num <> M.num
    join digits as R on R.num <> S.num and R.num <> E.num and R.num <> N.num and R.num <> D.num and R.num <> M.num and R.num <> O.num
    join digits as Y on Y.num <> S.num and Y.num <> E.num and Y.num <> N.num and Y.num <> D.num and Y.num <> M.num and Y.num <> O.num and Y.num <> R.num

where
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num)
    + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num)
    = (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num)     
    and S.num <> 0 and M.num <> 0

I thought about something in the WHERE clause to enforce unique digits, but I believe this ends up processing too many permutations before the WHERE clause is checked.

Since we're only dealing with up to 10 digits, I think it is best to build the long ON clauses instead for speed concerns.

Here is the FROM + WHERE clause without the crazy ON clauses. This runs A LOT slower on my server.

from
    Digits as S
    cross join digits as E
    cross join digits as N
    cross join digits as D
    cross join digits as M
    cross join digits as O
    cross join digits as R
    cross join digits as Y

where
    (S.num * 1000 + E.num * 100 + N.num * 10 + D.num)
    + (M.num * 1000 + O.num * 100 + R.num * 10 + E.num)
    = (M.num * 10000 + O.num * 1000 + N.num * 100 + E.num * 10 + Y.num)     
    and S.num <> 0 and M.num <> 0

        and (select max(B.Count) from   
                (select COUNT(*) as Count from 
                    (select S.num, 's' as letter   -- the letters are included to make sure the unions do not merge equivalent rows
                    UNION select E.num, 'e'
                    UNION select N.num, 'n'
                    UNION select D.num, 'd'
                    UNION select M.num, 'm'
                    UNION select O.num, 'o'
                    UNION select R.num, 'r'
                    UNION select Y.num, 'y') as A
                    group by A.num
                ) as B
             ) = 1
0
5

The author poses two distinct problems.

This answers the problem that is posed, OVER + FLOW = STACK where each character does not necessarily have a unique digit and more than 10 characters may be involved

  • There is a stipulation that each character receive a unique digit, but that is impossible for OVER + FLOW + STACK as there are too many letters.

Something like this may work where Digits table contains one column, where earch record contains an integer between 1 and 9 (or 0 through 9 if you wish).

Cross joins are pretty nasty, performance-wise, but this may be a starting point.

select
    top 5 
    O.num as O,
    V.num as V,
    E.num as E,
    R.num as R,
    F.num as F,
    L.num as L,
    W.num as W,
    S.num as S,
    T.num as T,
    A.num as A,
    C.num as C,
    K.num as K,
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num) as [OVER],
    (F.num * 1000 + L.num * 100 + O.num * 10 + W.num) as FLOW,
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num) + (F.num * 1000 + L.num * 100 + O.num * 10 + W.num) as OVER_plus_FLOW,
    (S.num * 10000 + T.num * 1000 + A.num * 100 + C.num * 10 + K.num) as STACK
from
    Digits as O
    cross join digits as V
    cross join digits as E
    cross join digits as R
    cross join digits as F
    cross join digits as L
    cross join digits as W
    cross join digits as S
    cross join digits as T
    cross join digits as A
    cross join digits as C
    cross join digits as K
where
    (O.num * 1000 + V.num * 100 + E.num * 10 + R.num)
    + (F.num * 1000 + L.num * 100 + O.num * 10 + W.num)
    = (S.num * 10000 + T.num * 1000 + A.num * 100 + C.num * 10 + K.num)

Based upon my understanding of the problem, there are multiple solutions. Here's the first 5 that this code found:

enter image description here

I removed 0 because you can replace each letter with zero and get a cheap answer (based upon your initial question revision).

This is the only table Digits

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.