/* 

  Sequence puzzle in Picat.

  From 
  http://stackoverflow.com/questions/27089772/whats-a-more-efficient-implementation-of-this-puzzle
  """
  The puzzle

  For every input number n (n < 10) there is an output number m such that:

      m's first digit is n
      m is an n digit number
      every 2 digit sequence inside m must be a different prime number

  The output should be m where m is the smallest number that fulfils the conditions above. 
  If there is no such number, the output should be -1;

  Examples

  n = 3 -> m = 311

  n = 4 -> m = 4113 (note that this is not 4111 as that would be repeating 11)

  n = 9 -> m = 971131737
  """


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

*/


import cp,utils.

main => go.

go =>
  nolog,
  foreach(N in 2..10) 
    println(n=N),
    if seq(N,X,M) then
      println(ok)
    else
      println(not_ok)
    end
  end,

  nl.

go2 =>
  foreach(N in 2..10) 
    seq2(N,X,M)
  end,
  
  nl.



seq(N, X, M) =>
  if N > 17 then 
    println("Picat can't handle N larger than 17."),
    halt
  end,

  % 2 digit primes
  Primes = [P : P in primes(99), P>10],

  % decision variables
  X = new_list(N),
  X :: 0..9,

  M :: 10**(N-1)..(10**N)-1,

  P = new_list(N-1),
  P :: Primes,

  X[1] #= N,
  to_num(X,10,M),

  foreach(I in 1..N-1)
    % each 2-digit sequence is a prime
    to_num([X[J] : J in I..I+1], 10, P[I])
  end,


  % all prime sequences are distinct
  all_different(P),

  Vars = X ++ P ++ [M],
  solve(Vars),

  println(x=X),
  println(p=P),
  println(m=M),
  nl.

% No CP
seq2(N, X, M) =>

  % 2 digit primes
  Primes = [P : P in primes(99), P>10],

  % decision variables
  X = new_list(N),
  foreach(I in 1..N)
    member(X[I],0..9)
  end,
  between(10**(N-1),(10**N)-1,M),

  P = new_list(N-1),
  P :: Primes,

  X[1] = N,
  to_num2(X,10,M),

  foreach(I in 1..N-1)
    % each 2-digit sequence is a prime
    to_num2([X[J] : J in I..I+1], 10, P[I])
  end,

  % all prime sequences are distinct
  all_different(P),

  solve(X),

  println(x=X),
  println(p=P),
  println(m=M),
  nl.


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

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