/* 

  Euler #43 in Picat.

  """  
  The number, 1406357289, is a 0 to 9 pandigital number because it is made up of 
  each of the digits 0 to 9 in some order, but it also has a rather interesting 
  sub-string divisibility property.
  
  Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we 
  note the following:
  
      * d2d3d4=406 is divisible by 2
      * d3d4d5=063 is divisible by 3
      * d4d5d6=635 is divisible by 5
      * d5d6d7=357 is divisible by 7
      * d6d7d8=572 is divisible by 11
      * d7d8d9=728 is divisible by 13
      * d8d9d10=289 is divisible by 17
  
  Find the sum of all 0 to 9 pandigital numbers with this property.
  """

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

*/

import util.

import cp.

main => go.

go => time(euler43). % , time(euler43b).

% using CP is fast: 0.05s
euler43 => 
   Primes = [2,3,5,7,11,13,17],
   X = new_array(10),
   X :: 0..9,
   
   all_different(X),
   foreach({I,P} in zip(2..8, Primes))
      (100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0
   end,
   All=solve_all($[ffd,split],X),
   println(sum([Num : A in All, to_num(A, 10,Num)])).


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


% Here is Neng-Fa's simplification of euler43/0:
euler43b => 
   Primes = [2,3,5,7,11,13,17],
   X = new_list(10),
   X :: 0..9,

   all_different(X),
   foreach({I,P} in zip(2..8, Primes))
      (100*X[I]+10*X[I+1]+X[I+2]) mod P #= 0
   end,

   All=solve_all(X),
   writeln(sum([to_num2(A) : A in All])),
   nl.

to_num2(List) = Num =>
   Str = [Char : D in List, D.to_string()=[Char]],
   Num = Str.to_integer().

% 3.8s
% Same idea as euler43 but without CP.
euler43c =>
  garbage_collect(400_000_000),
  Primes = [2,3,5,7,11,13,17],
  Perms = permutations(0..9),
  Sum = 0,
  foreach(P in Perms) 
    I = 1,
    Found = true,
    while(I <= 7, Found == true)
      if (100*(P[I+1]).to_int() + 10*(P[I+2]).to_int() + P[I+3].to_int()) mod Primes[I] != 0 then
         Found := false
      end,
      I := I+1
    end,
    if Found then
      % println(found=P),
      Sum := Sum + [X.to_string() : X in P].flatten().to_int()
    end
  end,
  println(Sum),
  nl.


%
% using next_permutation/1 instead of permutations/1: 4.6s
%
euler43d =>
  garbage_collect(400_000_000),
  Primes = [2,3,5,7,11,13,17],
  P = [1,0,2,3,4,5,6,7,8,9],
  Stop = (0..9).reverse(),
  Sum = 0,
  while (P != Stop)  
    I = 1,
    Found = true,
    while(I <= 7, Found == true)
      if (100*(P[I+1]).to_int() + 10*(P[I+2]).to_int() + P[I+3].to_int()) mod Primes[I] != 0 then
         Found := false
      end,
      I := I+1
    end,
    if Found then
      % println(found=P),
      Sum := Sum + [X.to_string() : X in P].flatten().to_int()
    end,
    P := next_permutation(P)
  end,
  println(Sum),
  nl.


/* 
% Notes:
% 
%   - got this error/warning ** Error  : assignment_in_condition:while
%   - it eats a lot of memory
%   - it's very slow
% 
% 34.7s
euler43d =>
  PP = [2, 3, 5, 7, 11, 13, 17],
  % skipping all permutations that starts with [0,..]
  S = [1, 0, 2, 3, 4, 5, 6, 7, 8, 9],
  Sum = 0,
  Sdown = S.sort_down(),
  while (S != Sdown)
    S2 = S.to_string(),
    I = 1,
    % it's here the "assignment_in_condition:while" error come
    while (I =< 7, [S[J].to_string() : J in 1+I..I+3].flatten().to_integer() mod PP[I] == 0)
      I := I + 1
    end,
    if I == 8 then
      println(s2=S2),
      Sum := Sum + [S[J].to_string() : J in 1..S.length].flatten().to_integer()
    end,
    S := next_permutation(S)
  end,

  println(Sum)
*/

next_permutation(P) = Perm =>
   Perm1 = P,
   N = Perm1.length,
   K = N - 1,
   if K == 0 then Perm1 := []  end,  % return
   while (Perm1[K] > Perm1[K+1], K >= 0) 
      K := K - 1,
      if K == 0 then Perm1 := []  end  % return
   end,
   if K > 0 then
      J = N,
      while (Perm1[K] > Perm1[J])  J := J - 1 end,      
      Tmp := Perm1[K],
      Perm1[K] := Perm1[J],
      Perm1[J] := Tmp,
      R = N, 
      S = K + 1,
      while (R > S) 
         Tmp := Perm1[R],
         Perm1[R] := Perm1[S],
         Perm1[S] := Tmp,
         R := R - 1, 
         S := S + 1
      end
   end,
   Perm = Perm1.