/* 

  Second grade puzzle in Picat.

  MindYourDecisions:
  "Can you solve this 2nd grade problem that has baffled adults?"
  https://www.youtube.com/watch?v=2hLqEEdK3a4
  """
  Stretch Your Thinking Write an addition equation 
  The equation must have a 1-, a 2-, and a 3-digit addend
  and use all of these digits
    6 6 2 2 8 8 0 0 0

  """

  There are 18 solutions (not allowing leading zeros)

  0 + 20 + 608 = 628
  0 + 20 + 806 = 826
  0 + 26 + 800 = 826
  0 + 28 + 600 = 628
  0 + 60 + 208 = 268
  0 + 60 + 802 = 862
  0 + 62 + 800 = 862
  0 + 68 + 200 = 268
  0 + 80 + 206 = 286
  0 + 80 + 602 = 682
  0 + 82 + 600 = 682
  0 + 86 + 200 = 286
  2 + 60 + 800 = 862
  2 + 80 + 600 = 682
  6 + 20 + 800 = 826
  6 + 80 + 200 = 286
  8 + 20 + 600 = 628
  8 + 60 + 200 = 268


  Allowing leading zeros, there are 48 solutions:
  0 + 0 + 268 = 268  AL:[0] BL:[0,0] CL:[2,6,8] DL:[2,6,8]
  0 + 0 + 286 = 286  AL:[0] BL:[0,0] CL:[2,8,6] DL:[2,8,6]
  0 + 0 + 628 = 628  AL:[0] BL:[0,0] CL:[6,2,8] DL:[6,2,8]
  0 + 0 + 682 = 682  AL:[0] BL:[0,0] CL:[6,8,2] DL:[6,8,2]
  0 + 0 + 826 = 826  AL:[0] BL:[0,0] CL:[8,2,6] DL:[8,2,6]
  0 + 0 + 862 = 862  AL:[0] BL:[0,0] CL:[8,6,2] DL:[8,6,2]
  0 + 2 + 680 = 682  AL:[0] BL:[0,2] CL:[6,8,0] DL:[6,8,2]
  0 + 2 + 860 = 862  AL:[0] BL:[0,2] CL:[8,6,0] DL:[8,6,2]
  0 + 6 + 280 = 286  AL:[0] BL:[0,6] CL:[2,8,0] DL:[2,8,6]
  0 + 6 + 820 = 826  AL:[0] BL:[0,6] CL:[8,2,0] DL:[8,2,6]
  0 + 8 + 260 = 268  AL:[0] BL:[0,8] CL:[2,6,0] DL:[2,6,8]
  0 + 8 + 620 = 628  AL:[0] BL:[0,8] CL:[6,2,0] DL:[6,2,8]
  0 + 20 + 608 = 628  AL:[0] BL:[2,0] CL:[6,0,8] DL:[6,2,8]
  0 + 20 + 806 = 826  AL:[0] BL:[2,0] CL:[8,0,6] DL:[8,2,6]
  0 + 22 + 66 = 88  AL:[0] BL:[2,2] CL:[0,6,6] DL:[0,8,8]
  0 + 26 + 62 = 88  AL:[0] BL:[2,6] CL:[0,6,2] DL:[0,8,8]
  0 + 26 + 800 = 826  AL:[0] BL:[2,6] CL:[8,0,0] DL:[8,2,6]
  0 + 28 + 600 = 628  AL:[0] BL:[2,8] CL:[6,0,0] DL:[6,2,8]
  0 + 60 + 208 = 268  AL:[0] BL:[6,0] CL:[2,0,8] DL:[2,6,8]
  0 + 60 + 802 = 862  AL:[0] BL:[6,0] CL:[8,0,2] DL:[8,6,2]
  0 + 62 + 26 = 88  AL:[0] BL:[6,2] CL:[0,2,6] DL:[0,8,8]
  0 + 62 + 800 = 862  AL:[0] BL:[6,2] CL:[8,0,0] DL:[8,6,2]
  0 + 66 + 22 = 88  AL:[0] BL:[6,6] CL:[0,2,2] DL:[0,8,8]
  0 + 68 + 200 = 268  AL:[0] BL:[6,8] CL:[2,0,0] DL:[2,6,8]
  0 + 80 + 206 = 286  AL:[0] BL:[8,0] CL:[2,0,6] DL:[2,8,6]
  0 + 80 + 602 = 682  AL:[0] BL:[8,0] CL:[6,0,2] DL:[6,8,2]
  0 + 82 + 600 = 682  AL:[0] BL:[8,2] CL:[6,0,0] DL:[6,8,2]
  0 + 86 + 200 = 286  AL:[0] BL:[8,6] CL:[2,0,0] DL:[2,8,6]
  2 + 0 + 680 = 682  AL:[2] BL:[0,0] CL:[6,8,0] DL:[6,8,2]
  2 + 0 + 860 = 862  AL:[2] BL:[0,0] CL:[8,6,0] DL:[8,6,2]
  2 + 20 + 66 = 88  AL:[2] BL:[2,0] CL:[0,6,6] DL:[0,8,8]
  2 + 26 + 60 = 88  AL:[2] BL:[2,6] CL:[0,6,0] DL:[0,8,8]
  2 + 60 + 26 = 88  AL:[2] BL:[6,0] CL:[0,2,6] DL:[0,8,8]
  2 + 60 + 800 = 862  AL:[2] BL:[6,0] CL:[8,0,0] DL:[8,6,2]
  2 + 66 + 20 = 88  AL:[2] BL:[6,6] CL:[0,2,0] DL:[0,8,8]
  2 + 80 + 600 = 682  AL:[2] BL:[8,0] CL:[6,0,0] DL:[6,8,2]
  6 + 0 + 280 = 286  AL:[6] BL:[0,0] CL:[2,8,0] DL:[2,8,6]
  6 + 0 + 820 = 826  AL:[6] BL:[0,0] CL:[8,2,0] DL:[8,2,6]
  6 + 20 + 62 = 88  AL:[6] BL:[2,0] CL:[0,6,2] DL:[0,8,8]
  6 + 20 + 800 = 826  AL:[6] BL:[2,0] CL:[8,0,0] DL:[8,2,6]
  6 + 22 + 60 = 88  AL:[6] BL:[2,2] CL:[0,6,0] DL:[0,8,8]
  6 + 60 + 22 = 88  AL:[6] BL:[6,0] CL:[0,2,2] DL:[0,8,8]
  6 + 62 + 20 = 88  AL:[6] BL:[6,2] CL:[0,2,0] DL:[0,8,8]
  6 + 80 + 200 = 286  AL:[6] BL:[8,0] CL:[2,0,0] DL:[2,8,6]
  8 + 0 + 260 = 268  AL:[8] BL:[0,0] CL:[2,6,0] DL:[2,6,8]
  8 + 0 + 620 = 628  AL:[8] BL:[0,0] CL:[6,2,0] DL:[6,2,8]
  8 + 20 + 600 = 628  AL:[8] BL:[2,0] CL:[6,0,0] DL:[6,2,8]
  8 + 60 + 200 = 268  AL:[8] BL:[6,0] CL:[2,0,0] DL:[2,6,8]


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

*/

import util.
import cp.

main => go.

%
% CP model: 0.009s
%
go ?=>
  L = [6,6,2,2,8,8,0,0,0],
  member(AllowLeadingZeros, [false,true]),
  nl,
  println(allow_leading_zeros=AllowLeadingZeros),

  AL = new_list(1), AL :: L,
  BL = new_list(2), BL :: L,
  CL = new_list(3), CL :: L,
  DL = new_list(3), DL :: L, % The result

  X = new_list(9),  X :: L,

  to_num(AL,A),
  to_num(BL,B),
  to_num(CL,C),
  to_num(DL,D),

  % Allowing leading zeros?
  if not AllowLeadingZeros then 
    B :: 10..99,
    C :: 100..999,
    D :: 100..999    
  end,
  
  XL = AL ++ BL ++ CL ++ DL,
  D #= A + B + C,

  % Ensure we have the proper number of digits
  foreach(Digit in L.remove_dups)
    count(Digit,XL) #= [1 : V in L, V == Digit].len
  end,
  
  solve(XL),
  % println(xl=XL),
  if AllowLeadingZeros then
    printf("%d + %d + %d = %d  AL:%w BL:%w CL:%w DL:%w\n",A,B,C,D, AL,BL,CL,DL)
  else 
    printf("%d + %d + %d = %d\n",A,B,C,D)
  end,
  fail,
  
  nl.
go => true.


%
% Imperative model with permutations/1
% Smaller than the CP model but significantly slower: 3.4s
%
go2 ?=>
  L = [6,6,2,2,8,8,0,0,0],
  member(AllowLeadingZeros, [false,true]),
  nl,
  println(allow_leading_zeros=AllowLeadingZeros),  
  Sols = [],
  foreach([A,B,C,D,E,F,G,H,I] in permutations(L))
    BC = 10*B + C,
    DEF = 100*D+10*E+F,
    GHI = 100*G + 10*H + I,
    if (A + BC + DEF == GHI),
       ( (AllowLeadingZeros == false,
          BC >= 10, BC <= 99,
          DEF >= 100, DEF <= 999,
          GHI >= 100, GHI <= 999
          ) ;
          AllowLeadingZeros == true
       ) then
      Sols := Sols ++ [[A,BC,DEF,GHI]]
    end
  end,
  Sols2 = Sols.remove_dups,
  foreach([A,BC,DEF,GHI] in Sols2)
    printf("%d + %d + %d = %d\n",A,BC,DEF,GHI)
  end,
  println(count=Sols2.len),
  nl,
  fail,
  nl.
go2 => true.
  
%
% to_num(List, Base, Num)
% Converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Num) =>
   to_num(List, 10, Num).

to_num(List, Base, Num) =>
   Len = length(List),
   Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).