/* 

  Euler #32 in Picat.

  Problem 32
  """
  We shall say that an n-digit number is pandigital if it makes use of 
  all the digits 1 to n exactly once; for example, the 5-digit number, 
  15234, is 1 through 5 pandigital.

  The product 7254 is unusual, as the identity, 39 × 186 = 7254, 
  containing multiplicand, multiplier, and product is 1 through 9 
  pandigital.

  Find the sum of all products whose multiplicand/multiplier/product 
  identity can be written as a 1 through 9 pandigital.
  HINT: Some products can be obtained in more than one way so be sure 
  to only include it once in your sum.
  """

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

*/

import cp,util.

main => go.

go => time(euler32).

% using CP: 0.02s
euler32 =>
  L = findall(Res, pandigital(Res)).remove_dups(),
  writeln(sum(L)).


% % 1.5s
euler32b => 
  Sum = 0,
  ProdHash = new_map(),
  foreach (A in 2..98, B in A+1..9876)
     Prod = A*B,
     L = A.to_string() ++ B.to_string() ++ Prod.to_string(),
     if L.length == 9, not(membchk('0',L)) then
        Hash = new_map([(I.to_int()=1) : I in L]),
        if Hash.keys().length == 9, not ProdHash.has_key(Prod) then
           % println([a=A, b=B, prod=Prod,l=L]),
           Sum := Sum + Prod,
           ProdHash.put(Prod,1)
        end
     end
  end,
  println(Sum).

% slightly different version: skipping Sum
euler32c => 
  ProdHash = new_map(),
  foreach (A in 2..98, B in A+1..9876)
     Prod = A*B,
     L = A.to_string() ++ B.to_string() ++ Prod.to_string(),
     if L.length == 9, not(membchk('0',L)) then
        Hash = new_map([(I.to_int()=1) : I in L]),
        if Hash.keys().length == 9, not ProdHash.has_key(Prod) then
           % println([a=A, b=B, prod=Prod,l=L]),
           ProdHash.put(Prod,1)
        end
     end
  end,
  println(ProdHash.keys().sum()).


% 3.282s
euler32d =>
   Perm = permutations("123456789"),   
   Ps = [],
   foreach(P in Perm,Pos1 in 1..4)
      P1 = P[1..Pos1].to_int,
      P2 = P[Pos1+1..5].to_int,
      P3 = P[6..9].to_int,
      if P1*P2 == P3 then
        Ps := Ps ++ [P3]
      end
   end,
   println(sum(Ps.remove_dups)),
   nl.

% 0.843s
euler32e => 
  [Prod : A in 2..98, B in A+1..9876,
          Prod = A*B,
          L = A.to_string ++ B.to_string ++ Prod.to_string,
          L.length == 9, L.remove_dups.len==9, not membchk('0',L)
  ].remove_dups.sum.println().

%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
  Len = length(List),
  Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).

% cp approach: Find a proper pandigial number
pandigital(Res) =>

  % the different lengths
  Len1 :: 1..2,
  Len2 :: 3..4,
  Len3 #= 4,

  % must be a 9 digit number
  Len1 + Len2 + Len3 #= 9,

  indomain(Len1), % must be instantiated

  X1 = new_list(Len1),
  X1 :: 1..9,

  X2 = new_list(Len2),
  X2 :: 1..9,

  X3 = new_list(Len3), % the result
  X3 :: 1..9,

  Vars = X1 ++ X2 ++ X3,
  all_different(Vars),

  % convert to number
  Base = 10,
  to_num(X1, Base, Num1),
  to_num(X2, Base, Num2),
  to_num(X3, Base, Res),

  % calculate result
  Num1 * Num2 #= Res,


  solve([ff,split],Vars),
  println([Num1,Num2,Res]).