/* 

  Project Euler #52 in Picat.

  https://projecteuler.net/problem=52
  """
  Permuted multiples

  It can be seen that the number, 125874, and its double, 251748, contain exactly 
  the same digits, but in a different order.

  Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, 
  contain the same digits.
  """

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

*/

import cp.

main => euler52.

% 0.31s
euler52 =>
  N = 1,
  Found = false,
  while(Found == false)
    if check52(2..6,N,N.to_string().sort()) then
       Found := N
    end,
    N := N + 1
  end,
  println(Found),
  nl.

check52([],_N,_S) => true.
check52([H|T],N,S) =>
  (N*H).to_string().sort() == S,
  check52(T,N,S).


% slightly slower: 0.34s
euler52b =>
  N = 1,
  Found = false,
  while(Found = false)
    Check = ok,
    foreach(M in 2..6, Check == ok)
      if (N*M).to_string().sort() != N.to_string().sort() then
        Check := not_ok
      end
    end,
    if Check = ok then
      Found := N
    end,
    N := N + 1
  end,
  println(Found),
  nl.

%
% CP approach, a magnitude faster (0.03s)
%
euler52c ?=>
  N = 6,
  D = 9,
  Base = 10, % generalized to any base
  
  Digits = new_array(N,D),
  Digits ::  0..Base-1,

  X = new_list(N),
  X :: 0..1000000,

  X[1] #> 0,
  foreach(I in 1..N)
    X[I] #>= 0,
    X[I] #= I * X[1],
    to_num([Digits[I, J] : J in 1..D], Base, X[I])
  end,
  foreach(I in 2..N) 
    % all digits must be the same (in some order)
    foreach(J in 1..D)
        contains(Digits[I,J], [Digits[I-1, K] : K in 1..D]),
        contains(Digits[I-1,J], [Digits[I, K] : K in 1..D])
    end
  end,

  Vars = X ++ Digits, %  ++ X,
  solve($[ffd,updown],Vars),

  println(x=X),
  % foreach(Row in Digits) println(Row) end,
  nl.

euler52c => true.


%
% 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]).

%
% does a contains e?
%
contains(E, A) =>
  sum([A[I] #= E : I in 1..A.len]) #>= 1.