%% File:  money.pl
%% Author:  Robert Keller
%% Purpose:  Solves the SEND MORE MONEY puzzle.

/*    S E N D
    + M O R E
    ---------
    M O N E Y
*/

%% says SENDMORY is a solution
solution([S, E, N, D, M, O, R, Y]) :-        
    digits(Digits),           /* set of usable digits       */

    element(D, Digits, D1),   /* D E Y column */
    element(E, D1, D2),
    sum(D, E, 0, Y, C1),
    element(Y, D2, D3),

    element(N, D3, D4),       /* N R E column */
    element(R, D4, D5),
    sum(N, R, C1, E, C2),

    element(O, D5, D6),       /* E O N column */
    sum(E, O, C2, N, C3),

    element(S, D6, D7),       /* S M O column */
    element(M, D7, _),
    sum(S, M, C3, O, M),

    M =\= 0.                  /* constrain M to be non-zero */


%%says Sum and Carry are from adding A, B, C

sum(A, B, C, Sum, Carry) :-    
    Sum is (A + B + C) mod 10,
    Carry is (A + B + C) // 10.

%%  element(A, X, Y) says A is an element of X, residue Y

element(A, [A | X], X). 
element(B, [A | X], [A | Y]) :-
    element(B, X, Y).

%% says digits are 0,...,9

digits([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).