% COSC 2P93 assignment 4: Question 3iii
% Author: Brian Ross
% March 2001

% This solution is not general - works only for SEND+MORE=MONEY
% It is a faster solution. Digits are selected right-to-left, rather
% than all at once. 
% This version does not permit M or S to be zero.

% define letters and words in terms of logical variables

puzzle([S,E,N,D],[M,O,R,E],[M,O,N,E,Y]).

% list of integers...

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

% puzzle_solver(A, B, C) solves the puzzle, where A, B, and C are
% SEND, MORE and MONEY resp. (lists of integers)

puzzle_solver(T1, T2, Sum) :-
	integers(Ints),
	puzzle(T1, T2, Sum),
	solution(Ints, T1, T2, Sum),
	write(T1), write('+'),write(T2), write('='), write(Sum),nl.

% remove(A, B, C) removes A from list B, resulting in list C

remove(A, [A|B], B).
remove(A, [B|C], [B|D]) :-
	remove(A, C, D).

% solution(A,B,C,D) removes digits from Ints into letters comprising
% numbers denoted in B, C, D, to solve the puzzle. Selection happens
% right-to-left, in a depth-first manner.

solution(Ints, [S,E,N,D], [M,O,R,E], [M,O,N,E,Y]) :-
	remove(D, Ints, Ints2),
	remove(E, Ints2, Ints3),
	add(D, E, 0, Y, C1),
	remove(Y, Ints3, Ints4),
	remove(N, Ints4, Ints5),
	remove(R, Ints5, Ints6),
	remove(O, Ints6, Ints7),
	add(N, R, C1, E, C2),
	add(E, O, C2, N, C3),
	remove(S, Ints7, Ints8),
	remove(M, Ints8, _),
	S \= 0,
	M \= 0,
	add(S, M, C3, O, M).

% add(I, J, OldCarry, Result, NewCarry) succeeds if I+J+OldCarry = Result,
% with resulting carry NewCarry

add(I, J, C0, R, C1) :-
	Sum is I + J + C0,
	R is mod(Sum, 10),
	C1 is integer(Sum/10).