/*

  General alphametic (cryptarithmetic) solver in Picat.

  This version is a port of the ECLiPSe CLP model by Joachim Schimpf:
  http://eclipseclp.org/examples/cryptarith.ecl.txt
  """
  Examples:
  %
  % ?- cryptarith([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y], 10).
  % 
  % ?- cryptarith([D,O,N,A,L,D] + [G,E,R,A,L,D] = [R,O,B,E,R,T], 10).
  % 
  % ?- cryptarith([S,I,X] + [S,I,X] + [S,I,X] + [B,E,A,S,T] = [S,A,T,A,N], 10).
  % 
  % By Jim Gillogly, rec.puzzles 2003-09-05 (base 12, 2 solutions):
  % ?- cryptarith([[K,K,K] = [6,6,6],
  %                [K,K,K] = [G,E,O,R,G,E] - [W,A,L,K,E,R] + [B,U,S,H]], 12).
  """

  It is more general than 
     http://www.hakank.org/picat/alphametic2.pi
  and supports both subtraction and multiplication. 
  Simple usage of these extensions:

     cryptarith($([A,B]*[C,D]-[D]=[F,G,H]*[I]), 10).

  One solution (of many) is: 
     [1,0]*[7,4]-[4]=[3,6,8]*[2],
  i.e 10*74-4 = 368*2
  


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

*/

% import util.
import cp.

main => go.

go =>
  cryptarith($([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]), 10),
  fail,
  nl.

go2 =>
  cryptarith($[D,O,N,A,L,D] + [G,E,R,A,L,D] = [R,O,B,E,R,T], 10),
  fail,
  nl.

go3 =>
  cryptarith($[S,I,X] + [S,I,X] + [S,I,X] + [B,E,A,S,T] = [S,A,T,A,N], 10),
  fail,
  nl.

go4 =>
  cryptarith($[[K,K,K] = [6,6,6],
              [K,K,K] = [G,E,O,R,G,E] - [W,A,L,K,E,R] + [B,U,S,H]], 12),
  fail,
  nl.

% multiplication and subtraction.
% Note: single digits must be stated as a list, i.e. [D] and [I].
go5 =>
  cryptarith($([A,B]*[C,D]-[D]=[F,G,H]*[I]), 10),
  fail,
  nl.

% From Martin Chlond's Integer Programming Puzzles (Enigma puzzle, Herald Tribune Nov '79)
go6 =>
  cryptarith($[O,N,E] + [O,N,E] + [T,W,O] + [T,W,O] + [T,H,R,E,E] + [E,L,E,V,E,N] = [T,W,E,N,T,Y] , 10),
  fail,
  nl.

go7 =>
  cryptarith($[[B,O,B] * [B,O,B] = [M,A,R,L,E,Y], [B]*[B,O,B]=[M,E,O,Y]], 10),
  fail,
  nl.

cryptarith(Equations, Base) =>
  println(equations=Equations),
  % term_variables(Equations, Digits),
  Digits = Equations.vars,
  Len = Digits.length,
  println(num_digits=Len),
  if Len > Base then
    printf("Impossible. Number of variables (%d) > Base (%d).\n", Digits.length, Base)
    % halt
  end,
  println(digits=Digits),
  Digits :: 0..Base-1,
  all_different(Digits),
  constraint(Equations, Base),
  % println(digits=Digits),
  solve(Digits),
  nl,
  println(digits=Digits),
  println(Equations).

constraint([], _) ?=> 
  true.
constraint([C|Cs], Base) ?=>
  constraint(C, Base),
  constraint(Cs, Base).
constraint(Exp, Base) ?=>
  Exp = $(E1=E2),
  expression(E1, CE1, Base),
  expression(E2, CE2, Base),
  CE1 #= CE2.
  
expression(Exp1, Exp2, Base) ?=>
  Exp1 = $(E1+E2),
  Exp2 = $(CE1+CE2),
  expression(E1, CE1, Base),
  expression(E2, CE2, Base).
expression(Exp1, Exp2, Base) ?=>
  Exp1 = $(E1-E2),
  Exp2 = $(CE1-CE2),
  expression(E1, CE1, Base),
  expression(E2, CE2, Base).
expression(Exp1, Exp2, Base) ?=>
  Exp1 = $(E1*E2),
  Exp2 = $(CE1*CE2),
  expression(E1, CE1, Base),
  expression(E2, CE2, Base).
expression(Digits, WeightedDigits, Base) =>
  Digits = [First|_],
  First #!= 0,
  Len = length(Digits),
  % WeightedDigits #= sum([T : I in 1..Len, T #= Digits[I]*Base**(Len-I)]).
  WeightedDigits #= sum([Digits[I]*Base**(Len-I) : I in 1..Len]).


term_variables(L,Flatten) =>
   Flatten = vars(L).