/*

  SEND+MORE=MONEY in Picat.

  Solve the alphametic problem 
    SEND+MORE=MONEY
  using distinct digits for the letters.

  sendmore and sendmore2 are using base 10, and sendmore_base
  use "any" base.

  Also some non-CP variants.

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.
import ordset.


main => go.

% 0.02s
go =>
  time2(sendmore(Digits)),
  println(Digits).

% 0.02s 
go2 => 
  sendmore2(Digits),
  println(Digits).

% 0.02s
go3 =>
  Base = 10,
  sendmore_base(Digits, Base),
  println(Digits).

%
% Check the number of solutions for different bases.
% 0.024s
go4 =>
  Lens = [],
  foreach(Base in 2..30)
    printf("Base: %d\n", Base),
    All = findall(Digits, sendmore_base(Digits, Base)),
    Len = length(All),
    Lens := Lens ++ [Len]
  end,
  printf("All lengths: %w\n", Lens).

% 0.02s
go5 => 
  sendmore_carry(_Digits,_Carry),
  nl.

% 0.45s
go6 => 
  sendmore_no_cp1(Digits),
  println(Digits),
  nl.

% 0.7s
go6b => 
  sendmore_no_cp1b(Digits),
  println(Digits),
  nl.


% 1.2s
go7 => 
  sendmore_no_cp2(Digits),
  println(Digits),
  nl.

% 4.5s
go8 => 
  sendmore_no_cp3(Digits),
  println(Digits),
  nl.

% 1.1s
go9 => 
  sendmore_no_cp4(Digits),
  println(Digits),
  nl.


scalar_product(A, X,Product)  => 
  Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).


%
% Standard problem (in base 10)
%
sendmore(Digits) =>

  Digits = [S,E,N,D,M,O,R,Y],
  Digits :: 0..9,

  % all_different(Digits),
  all_distinct(Digits),
  S #> 0,
  M #> 0,
         1000*S + 100*E + 10*N + D
  +      1000*M + 100*O + 10*R + E
  #= 10000*M + 1000*O + 100*N + 10*E + Y,
  
  println([s=S,e=E,n=N,d=D,m=M,o=O,r=R,y=Y]),
  println([s=S.fd_dom(),e=E.fd_dom(),n=N.fd_dom(),d=D.fd_dom(),m=M.fd_dom(),o=O.fd_dom(),r=R.fd_dom(),y=Y.fd_dom()]),
  % println(1000*S + 100*E + 10*N + D
  %  +      1000*M + 100*O + 10*R + E
  % #= 10000*M + 1000*O + 100*N + 10*E + Y),

  solve([ffd],Digits).


%
% Using scalar_product
%
sendmore2(Digits) =>

  Digits = [S,E,N,D,M,O,R,Y],
  Digits :: 0..9,

  all_different(Digits),

  S #> 0,
  M #> 0,

  Base4 = [1000,100,10,1],
  Base5 = [10000,1000,100,10,1],
  scalar_product(Base4, [S,E,N,D], SEND),
  scalar_product(Base4, [M,O,R,E], MORE),
  scalar_product(Base5, [M,O,N,E,Y], MONEY),
  SEND + MORE #= MONEY,
  println([s=S,e=E,n=N,d=D,m=M,o=O,r=R,y=Y]),

  solve(Digits).


%
% Solve the SEND + MORE = MONEY problem in base Base
%
sendmore_base(Digits, Base) =>

  Digits = [S,E,N,D,M,O,R,Y],
  Base2 = Base - 1,
  Digits :: 0..Base2,

  all_different(Digits),
  S #> 0,
  M #> 0,
           Base**3*S + Base**2*E + Base*N + D
  +        Base**3*M + Base**2*O + Base*R + E
  #= Base**4*M + Base**3*O + Base**2*N + Base*E + Y,
  println([s=S,e=E,n=N,d=D,m=M,o=O,r=R,y=Y]),
  
  solve(Digits).


%
% With carry
%
%   C4 C3 C2 C1
%       S  E  N  D
%  +    M  O  R  E
%  ---------------
%  = M  O  N  E  Y
% 

sendmore_carry(Digits, Carry) =>
  Digits = [S,E,N,D,M,O,R,Y],
  Digits :: 0..9,

  Carry = [C1,C2,C3,C4],
  Carry :: 0..1,

  all_different(Digits),

  S #> 0,
  M #> 0,
  
  C4 #= M,
  C3 + S + M #= O + 10 * C4,
  C2 + E + O #= N + 10 * C3,
  C1 + N + R #= E + 10 * C2,
  D + E #= Y + 10 * C1,

  println(digits=Digits), % inferred domains before search
  println(carry=Carry),

  solve([], Digits ++ Carry),
  println(digits=Digits),
  println(carry=Carry),
  nl.


% without CP, using select: 0.44s
sendmore_no_cp1(Digits) =>
  Digits = [S,E,N,D,M,O,R,Y],
  SS = 0..9,
  % ensure that all numbers are different
  select(S,SS,Rest1),
  S != 0,
  select(E,Rest1,Rest2),
  select(N,Rest2,Rest3),
  select(D,Rest3,Rest4),
  select(M,Rest4,Rest5),
  M != 0,
  select(O,Rest5,Rest6),
  select(R,Rest6,Rest7),
  select(Y,Rest7,_Rest8),
  (S * 1000 + E * 100 + N * 10 + D) +
  (M * 1000 + O * 100 + R * 10 + E) == 
  (M * 10000 + O * 1000 + N * 100 + E * 10 + Y ).


% assign( Digits, Vars):  
% Assign chosen distinct digits from list Digits to variables in list Vars
assign(_,[])           => true.
assign(Digs,[D|Vars])  =>	
  select(D, Digs,Digs1),
  assign(Digs1,Vars).

% variant where the selects are moved to assign/2
sendmore_no_cp1b(Digits) =>
  Digits = [S,E,N,D,M,O,R,Y],
  assign([0,1,2,3,4,5,6,7,8,9],[S,E,N,D,M,O,R,Y]),
  S != 0,
  M != 0,
  (S * 1000 + E * 100 + N * 10 + D) +
  (M * 1000 + O * 100 + R * 10 + E) == 
  (M * 10000 + O * 1000 + N * 100 + E * 10 + Y ).
  
 
% without CP, permutation/2: 1.2s
sendmore_no_cp2(Digits2) =>
  Digits = [S,E,N,D,M,O,R,Y, A,B],
  permutation(0..9,Digits),
  A < B, % symmetry breaking of the two unused digits
  S > 0, M > 0,
  (S * 1000 + E * 100 + N * 10 + D) +
  (M * 1000 + O * 100 + R * 10 + E) == 
  (M * 10000 + O * 1000 + N * 100 + E * 10 + Y),
  Digits2 = [S,E,N,D,M,O,R,Y].
  
 
% without CP, permutations/1: 3.97s
sendmore_no_cp3(Digits) =>
  foreach([S,E,N,D,M,O,R,Y, A,B] in permutations(0..9))
    if S > 0, 
       M > 0, 
       A < B,
       (S * 1000 + E * 100 + N * 10 + D) +
       (M * 1000 + O * 100 + R * 10 + E) == 
       (M * 10000 + O * 1000 + N * 100 + E * 10 + Y) 
       then
       Digits = [S,E,N,D,M,O,R,Y]
    end
  end.


% without CP, ordset/1: 1.1s
sendmore_no_cp4(Digits) =>
  Digits = [S,E,N,D,M,O,R,Y],
  SS = new_ordset(0..9),
  member(S,subtract(SS,new_ordset([0]))), % > 0
  member(E,subtract(SS,new_ordset([S]))),
  member(N,subtract(SS,new_ordset([S,E]))),
  member(D,subtract(SS,new_ordset([S,E,N]))),
  member(M,subtract(SS,new_ordset([S,E,N,D, 0]))), % > 0
  member(O,subtract(SS,new_ordset([S,E,N,D,M]))),
  member(R,subtract(SS,new_ordset([S,E,N,D,M,O]))),
  member(Y,subtract(SS,new_ordset([S,E,N,D,M,O,R]))),
  (S * 1000 + E * 100 + N * 10 + D) +
  (M * 1000 + O * 100 + R * 10 + E) == 
  (M * 10000 + O * 1000 + N * 100 + E * 10 + Y ).