-module(sendmory).
-author(patai@iit.bme.hu).
-vsn('2009-11-20').
-compile(export_all).

%      S E N D
%  +   M O R E
%  -----------
%  = M O N E Y

% @spec num(Ns::[integer()]) -> N::integer().
% The value of the digit list Ns, interpreted as a decimal number, is N.
num(Ns)->
    lists:foldl(fun(X,E) -> E*10+X end, 0, Ns).

% @spec smm0() -> ().
% All the checks are after the generators (generate and test).
smm0() ->
    Ds = lists:seq(0, 9),
    {A,B,C} = hd([{Send,More,Money} ||
	S <- Ds, E <- Ds, N <- Ds, D <- Ds,
	M <- Ds, O <- Ds, R <- Ds, Y <- Ds,
	all_different([S,E,N,D,M,O,R,Y]),
	S > 0, M > 0,
	begin Send = num([S,E,N,D]),
	      More = num([M,O,R,E]),
	      Money = num([M,O,N,E,Y]),
              Send+More == Money
	end]),
    io:format('~p+~p=~p~n', [A,B,C]).

% @spec all_different(Xs::[any()]) -> B::bool()
% B is true, if there is no repeated value in the list Xs.
all_different([]) ->
    true;
all_different([X|Xs]) ->
    not lists:member(X,Xs) andalso all_different(Xs).

% all_different(L) -> length(L) == length(lists:usort(L)).

% @spec smm1() -> ().
% Checking inequalities on the way.
smm1() ->
    Ds = lists:seq(0, 9),
    {A,B,C} = hd([{Send,More,Money} ||
	S <- Ds,
	E <- Ds, E /= S,
	N <- Ds, not lists:member(N, [S,E]),
	D <- Ds, not lists:member(D, [S,E,N]),
	M <- Ds, not lists:member(M, [S,E,N,D]),
	O <- Ds, not lists:member(O, [S,E,N,D,M]),
	R <- Ds, not lists:member(R, [S,E,N,D,M,O]),
	Y <- Ds, not lists:member(Y, [S,E,N,D,M,O,R]),
	S > 0, M > 0,
	begin Send = num([S,E,N,D]),
	      More = num([M,O,R,E]),
	      Money = num([M,O,N,E,Y]),
              Send+More == Money
	end]),
    io:format('~p+~p=~p~n', [A,B,C]).

% @spec smm2() -> ().
% Handling inequalities by construction (which is actually slower...).
smm2() ->
    {A,B,C} = hd([{Send,More,Money} ||
	{[S,E,N,D,M,O,R,Y],_} <- select_n(8, lists:seq(0, 9)),
	S > 0, M > 0,
	begin Send = num([S,E,N,D]),
	      More = num([M,O,R,E]),
	      Money = num([M,O,N,E,Y]),
	      Send+More == Money
	end]),
    io:format('~p+~p=~p~n', [A,B,C]).

%% This version of select_n, needed for smm2, doesn't have to return
%% the remaining elements.
% @spec select_n(N::integer(),Xs::[any()] -> Yss::[[any()]].
% Elements of Yss are Ys::[any()] lists of length N, where each Ys
% contains all possible permutations of N distinct elements of Xs.
% Fails miserably unless (N > 0 andalso N =< length(Xs)) holds;
%%% select_n(N, Xs) ->
%%%     [[Y|Ys] ||
%%% 	{Y,More} <- select(Xs),
%%% 	Ys <- case N of
%%% 		  1 -> [[]];
%%% 		  _ -> select_n(N-1, More)
%%% 	      end].

% @spec select_n(N::integer(),Xs::[any()] -> Zs::[{[any()],[any()]}].
% Elements of Zs are {Ys::[any()],Rs::[any()]} pairs, where Ys, a list of
% length N, contains all possible permutations of N distinct elements of Xs,
% and Rs contains all other elements of Xs not contained in Ys.
% Fails miserably unless (N > 0 andalso N =< length(Xs)) holds;
% it returns remaining elements for later use.
select_n(N, Xs) ->
    [{[Y|Ys],Rest} ||
	{Y,More} <- select(Xs),
	{Ys,Rest} <- case N of
			 1 -> [{[],More}];
			 _ -> select_n(N-1, More)
		     end].

% @spec select(Xs::[any()] -> Zs::[{any(),[any()]}].
% Elements of Zs are {X::any(),Rs::[any()]} pairs, where each X is a distinct
% element of Xs and Rs contains all other elements of Xs different from X,
% while length(Zs) == length(Xs), i.e. all elements of Xs occur as X in Zs.
select([X]) ->
    [{X,[]}];
select([X|Xs]) ->
    [{X,Xs}|[{Y,[X|Ys]} || {Y,Ys} <- select(Xs)]].

% @spec smm2() -> ().
% Building from right to left, checking the partial sums.
smm3() ->
    Ds0 = lists:seq(0, 9),
    {A,B,C} = hd([{Send,More,Money} ||
	{[D,E,Y],Ds1} <- select_n(3, Ds0),
        (D+E) rem 10 == Y,
	{[R,N],Ds2} <- select_n(2, Ds1),
        (num([N,D])+num([R,E])) rem 100 == num([E,Y]),
	{[O],Ds3} <- select_n(1, Ds2),
        (num([E,N,D])+num([O,R,E])) rem 1000 == num([N,E,Y]),
	{[S,M],_} <- select_n(2, Ds3),
	S > 0, M > 0,
	begin Send = num([S,E,N,D]),
	      More = num([M,O,R,E]),
	      Money = num([M,O,N,E,Y]),
              Send+More == Money
	end]),
    io:format('~p+~p=~p~n', [A,B,C]).

% exercise: generalise the task to specifications given in strings:
%
% smm_gen("send","more","money")  ==>
% [{9567,1085,10652}]
%
% smm_gen("four","five","nine")  ==>
% [{2970,2381,5351},{2970,2481,5451},...,{1970,1568,3538}]