/****************************************************************
	Criptarithmetic Puzzle
	LLP Example
	by Naoyuki Tamura (tamura@kobe-u.ac.jp)
	   Dept. CS, Kobe University
****************************************************************/
/*
  Examples
  send+more=money.
  logic+logic=prolog.
  lisp+lisp+logic+logic=prolog.
  linear+logic=prolog. (3 solutions)
  lolli+lolli+lolli+lolli+lolli+lolli+lolli+lolli=forum.
  forum+forum+forum+forum+forum+forum+forum=lolli.
  lolli+lolli+lolli+lolli+par+par+par=forum.
  llp+some+some+some+some+some+some+some+some+some+some+some+some+some=lolli.
*/
main :-
	repeat,
	  write('Please input a puzzle (bye. to quit)'), nl,
	  write('	Example: send+more=money.'), nl,
	  write('	Example: lisp+lisp+logic+logic=prolog.'), nl,
	  read(Equation),
	puzzle(Equation).

puzzle(end_of_file) :- !.
puzzle(bye) :- !.
puzzle(Equation) :-
	eq2list(Equation, List, []),
	put_variables(List, VList, VCount),
	nl, tab(4), write_list(List),
	write(' ('), write(VCount), write(' variables)'), nl,
	VCount =< 10,
	check_length(VList),
	non_zero_vars(VList, NonZeros),
	transpose(VList, Columns),
	!,
	statistics(runtime, _),
	crypt(Columns, NonZeros, VList),
	statistics(runtime, [_,T]),
	tab(4), write('CPU time = '), write(T), write(' msec'), nl, nl,
	fail.
puzzle(_) :-
	write('Illegal input'), nl,
	fail.

crypt(Columns, NonZeros, VList) :-
	solve(Columns),
	non_zero_check(NonZeros),
	tab(4), write_list(VList), nl,
	fail.
crypt(_, _, _).

non_zero_check([]).
non_zero_check([V|Vs]) :- V =\= 0, non_zero_check(Vs).

write_list([W1,W2]) :- !, write_word(W1), write('='), write_word(W2).
write_list([W|Ws]) :- write_word(W), write('+'), write_list(Ws).

write_word([]).
write_word([A|As]) :- write(A), write_word(As).

%
%  eq_list(Equation, List, [])
%  For example, when Equation = (send+more=money),
%  List = [[s,e,n,d],[m,o,r,e],[m,o,n,e,y]]
%
eq2list(A=B) --> {atomic(B)}, !, expr2list(A), expr2list(B).

expr2list(A) --> {atomic(A)}, !, {explode(A, Chars)}, [Chars].
expr2list(A+B) --> {atomic(B)}, !, expr2list(A), expr2list(B).

explode(A, Chars) :- name(A, List), list2chars(List, Chars).

list2chars([], []).
list2chars([N|Ns], [C|Cs]) :-name(C, [N]), list2chars(Ns, Cs).

%
%  put_variables(List, VList, VCount)
%  For example, when List = [[s,e,n,d],[m,o,r,e],[m,o,n,e,y]],
%  VList = [[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]]
%  VCount = 8
%
put_variables(List, VList, VCount) :-
	(var_count(VCount) -<>
	 put_var(List, VList, 0)).

put_var([], [], VC) :- !, var_count(VC).
put_var([[]|L], [[]|VL], VC) :- !, put_var(L, VL, VC).
put_var([[C|Cs]|L], [[C|Vs]|VL], VC) :- integer(C), !,
	put_var([Cs|L], [Vs|VL], VC).
put_var([[C|Cs]|L], [[V|Vs]|VL], VC) :- var_name(C, V), !,
	put_var([Cs|L], [Vs|VL], VC).
put_var([[C|Cs]|L], [[V|Vs]|VL], VC0) :- !,
	VC is VC0 + 1,
	(!var_name(C, V) -<>
	 put_var([Cs|L], [Vs|VL], VC)).

var_name(_, _) :- fail.

%
%  check_length
%
check_length(Words) :-
	check_length(Words, 0).

check_length([Word], Max) :- !,
	length(Word, N),
	N >= Max.
check_length([Word|Words], Max0) :-
	length(Word, N),
	Max is max(Max0, N),
	check_length(Words, Max).

%
%  non_zero_vars(VList, NonZeros)
%  For example, when VList = [[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]],
%  NonZeros = [S,M]
%
non_zero_vars(VL, NZ) :-
	non_zero_vars(VL, [], NZ).

non_zero_vars([], NZ, NZ) :- !.
non_zero_vars([[V|_]|VL], NZ0, NZ) :-
	var(V), \+ memq(V, NZ0),
	!,
	non_zero_vars(VL, [V|NZ0], NZ).
non_zero_vars([[X|_]|VL], NZ0, NZ) :-
	non_zero_vars(VL, NZ0, NZ).

%
%  transpose(Words, Columns)
%    For example, when Words = [[S,E,N,D],[M,O,R,E],[M,O,N,E,Y]],
%    Columns = [[D,E,Y],
%		[N,R,E],
%		[E,O,N],
%		[S,M,O],
%		    [M]]
%
transpose([Word], Cs) :- !,
	reverse(Word, R),
	list2columns(R, Cs).
transpose([Word|Words], Cs) :- !,
	transpose(Words, Cs0),
	reverse(Word, R),
	put_columns(R, Cs0, Cs).
	
list2columns([], []).
list2columns([X|Xs], [[X]|Zs]) :- list2columns(Xs, Zs).

put_columns([], Cs, Cs).
put_columns([X|Xs], [C|Cs0], [[X|C]|Cs]) :- put_columns(Xs, Cs0, Cs).

%
%  Solve Puzzle
%
solve(Columns) :-
	(d(0), d(1), d(2), d(3), d(4), 
	 d(5), d(6), d(7), d(8), d(9)) -<>
	(solve(Columns, 0), top).

solve([], 0).
solve([Column|Columns], Carry0) :-
	(c(Carry) -<>
	 solve_column(Column, Carry0)),
	solve(Columns, Carry).

solve_column([Sum], Sum0) :- var(Sum), !,
	Sum is Sum0 mod 10,
	d(Sum),
	Carry is Sum0//10,
	c(Carry).
solve_column([Sum], Sum0) :- !,
	Sum is Sum0 mod 10,
	Carry is Sum0//10,
	c(Carry).
solve_column([C|Column], Sum0) :- var(C), !,
	d(C),
	Sum is Sum0 + C,
	solve_column(Column, Sum).
solve_column([C|Column], Sum0) :- !,
	Sum is Sum0 + C,
	solve_column(Column, Sum).

%
% Utilities
%
memq(X, [Y|L]) :- X == Y, !.
memq(X, [_|L]) :- memq(X, L).

reverse(Xs, Zs) :- result(Zs) -<> rev(Xs, []).

rev([], Zs) :- result(Zs).
rev([X|Xs], Zs) :- rev(Xs, [X|Zs]).