% Cryptarithmetic puzzle in the form of:
% SEND + MORE = MONEY

% From source idea from crypt.m, originally written by Peter Van Roy
% author: Douglas M. Auclair
% added some optimizations to the algorithm to speed solution delivery
% (in particular, used Definite Clause Grammars (DCG) to ensure all
% variables are unified with unique digits).

:- module send_money_quickly.
:- interface.

:- import_module io.

:- pred main(state::di, state::uo) is cc_multi.

:- implementation.
:- import_module require, list, int, enum.

% Aha! An honest-to-God use for Peano numbers:
% deterministic dispatch on whole number!
:- type peano ---> zero; s(peano).
:- instance enum(peano) where [
   to_int(zero) = 0,
   to_int(s(Peano)) = 1 + to_int(Peano),
   func(from_int/1) is peano_from_int % I can't believe from_int is semidet!
].

:- func peano_from_int(int) = peano.
peano_from_int(X) = Peano :-
  X = 0 -> Peano = zero; Peano = s(peano_from_int(X - 1)).

main -->
	{ crypt([S, E, N, D, M, O, R, Y], 0 `..` 9, _) } ->
          { PrintList = (pred(List::in, di, uo) is det -->   % Too bad 
there's
		         write_list(List, "", print)) },     % no right curry!
                print("SEND + MORE = MONEY is\n"),
                PrintList([S, E, N, D]), print(" + "),
                PrintList([M, O, R, E]), print(" = "),
                PrintList([M, O, N, E, Y]), nl
	    ;
		io__write_string("No solution\n").

% These are originally Peter Van Roy's predicates:  sum is A + B = C
:- pred sum(list(int)::in, list(int)::in, list(int)::out) is det.

% but I changed Carry to be a bool to simplify program construction (it
% got rid of the (->) statements, but kept the predicates deterministic),
% and then I changed Carry to be a Peano number to keep the determinism
% and to eliminate the disconnect between booleans and numbers.
:- pred sum(list(int)::in, list(int)::in, peano::in, list(int)::out) is det.

% And this stuff is also Doug Auclair's:
:- func compute_sum(int, list(int), list(int), peano) = list(int).

% using DCG to assign and narrow digits.
:- pred crypt(list(int)::out, list(int)::in, list(int)::out) is nondet.
:- pred not_zero(peano::in) is semidet. % is this going too far?

% we're only doing natural and whole numbers up to 10 (exclusive), so
% I thought Peano need not apply here; but then, when I thought that,
% I thought wrongly.

:- pred natural(int, list(int), list(int)).
:- mode natural(in, in, out) is nondet.
:- mode natural(out, in, out) is nondet.

:- pred whole(int, list(int), list(int)).
:- mode whole(in, in, out) is nondet.
:- mode whole(out, in, out) is nondet.

crypt([S, E, N, D, M, O, R, Y]) -->
	natural(S), whole(E), whole(N), whole(D),
	natural(M), whole(O), whole(R), whole(Y),
        { sum([D, N, E, S, 0], [E, R, O, M, 0], [Y, E, N, O, M]) }.

sum(AL, BL, CL) :- sum(AL, BL, zero, CL).

sum([], [], zero, []).
sum([], [], s(Peano), [to_int(s(Peano))]).

sum([], [B | BL], zero, [B | BL]).
sum([], [B | BL], s(Peano), compute_sum(B, [], BL, s(Peano))).

sum([A | AL], [], zero, [A | AL]).
sum([A | AL], [], s(Peano), compute_sum(A, AL, [], s(Peano))).

sum([A | AL], [B | BL], Carry, compute_sum(A+B, AL, BL, Carry)).

% continuations make life so much easier ... see crypt.m or
% send_more_money.m for the versions without continuations to see
% why I say this -- 35 lines of code saved with this continuation:
compute_sum(Sum, Left, Right, Carry) = [X mod 10 | CL] :-
	X = Sum + to_int(Carry),
	sum(Left, Right, peano_from_int(X // 10), CL).

not_zero(s(_)). % or not_zero(X) :- X > 0 ... whatever!

natural(X) --> whole(X), { not_zero(peano_from_int(X)) }.

whole(_, [], _) :- error("Assigning whole number from empty list!").
whole(X, [H|T], Out) :- delete([H|T], X, Out).

