% https://open.kattis.com/problems/cardtrick2
% 1s
% 1.8 Easy

/*
  Simulation in Picat to get some feelings for the problem.

  Here are the first 13 solutions, the only we need
  (it took 59s to generate 1..10, and 4.8s to generate 1..9)

n = 1
perm = [1]

n = 2
perm = [2,1]

n = 3
perm = [3,1,2]

n = 4
perm = [2,1,4,3]

n = 5
perm = [3,1,4,5,2]

n = 6
perm = [4,1,6,3,2,5]

n = 7
perm = [5,1,3,4,2,6,7]

n = 8
perm = [3,1,7,5,2,6,8,4]

n = 9
perm = [7,1,8,6,2,9,4,5,3]

n = 10
perm = [9,1,8,5,2,4,7,6,3,10]

n = 11
perm = [5,1,6,4,2,10,11,7,3,8,9]

n = 12
perm = [7,1,4,9,2,11,10,8,3,6,5,12]

n = 13
perm = [4,1,13,11,2,10,6,7,3,5,12,9,8]


Some improvements for N=2..10:
  * With the symmetry breaking Perm[2] == 1: 6.684s
  * And checking that the K'th card is K: 1.2s 
  * Checking that the 5'th number is 2 (for N >= 5): 0.8s

It takes 279.39s (4min39s) to generate 1..13
And I simply copied this into the SWI-Prolog program (card_trick.pl). 
Perhaps this is considered cheating?


TODO: I would like a more algorithmic approach of this. 
It seems to be some variation of Langford sequence:
  Let's take N = 7: 
    5,1,3,4,2,6,7
  and copy it

   1->2: Two positions between
   5 1 3 4 2 6 7 5 1 3 4 2 6 7
     1     2 
   2->3 skipping 1: three positions between
   5 3 4 2 6 7  5 3 4 2 6 7
         2        3      

  3->4 skipping 1 and 2.
   5 3 4 6 7  5 3 4 2 6 7
       4        3
 
Another idea: Study the positions of I
   N=(
   5,1,3,4,2,6,7
-> 
   2 5 3 4 1 6 7

NOPE!

OK, I skip this for now...


*/

import util, cp.
main :-
  go.

% Brute force / simulation
go :-
  foreach(N in 2..13)
    println(n=N),
    time(P=p(N)),
    println(P),
    nl
  end,
  nl.

p(N) = Perm => 
   permutation(1..N,Perm),
   

   % Some invariants
   Perm1[2] == 1, % Symmetry breaking
   if N >= 5 then
     Perm1[5] == 2    
   end,
   if N >= 9 then
     Perm1[9] == 3
   end,
   X = Perm1,
   foreach(K in 1..N)
     % Take K cards (one at a time) and place them
     % last in the deck    
     foreach(_ in 1..K)
       % writeln(x=X),
       % X := rotate_left(X,1)
       X := X[2..X.len] ++ [X[1]] % A little faster than rotate_left...
     end,
     % X := rotate_left(X,K), % Not correct
     [K|T] = X, % We know that the Kth card should be K
     X := T
   end,
   Perm = Perm1.


rotate_left(L,N) = slice(L,N+1,L.length) ++ slice(L,1,N).reverse.
  

ps(1,[1]).
ps(2,[2,1]).
ps(3,[3,1,2]).
ps(4,[2,1,4,3]).
ps(5,[3,1,4,5,2]).
ps(6,[4,1,6,3,2,5]).
ps(7,[5,1,3,4,2,6,7]).
ps(8,[3,1,7,5,2,6,8,4]).
ps(9,[7,1,8,6,2,9,4,5,3]).
ps(10,[9,1,8,5,2,4,7,6,3,10]).
ps(11,[5,1,6,4,2,10,11,7,3,8,9]).
ps(12,[7,1,4,9,2,11,10,8,3,6,5,12]).
ps(13,[4,1,13,11,2,10,6,7,3,5,12,9,8]).



/*
  An aside trying to Langfordizing the problem.
  But it's a model of a quite different problem:
  Place the integers 1..N so that each number I
  is I-1 positions apart from I+1. 
  There is only one solution (+ its reverse) to this problem.
  Nice separation of even and odd numbers.

2 = [1,2]
3 = [2,1,3]
4 = [3,1,2,4]
5 = [4,2,1,3,5]
6 = [5,3,1,2,4,6]
7 = [6,4,2,1,3,5,7]
8 = [7,5,3,1,2,4,6,8]
9 = [8,6,4,2,1,3,5,7,9]
10 = [9,7,5,3,1,2,4,6,8,10]
11 = [10,8,6,4,2,1,3,5,7,9,11]
12 = [11,9,7,5,3,1,2,4,6,8,10,12]
13 = [12,10,8,6,4,2,1,3,5,7,9,11,13]

(Found in 0.05s)

*/
go_test :-
  member(N,2..13),
  X = new_list(N),
  X :: 1..N,
  % X[2] #= 1, % NOPE
  all_different(X),
  X[1] #< X[N], % symmetry breaking
  foreach(I in 1..N-1)
    J = I+1,
    element(P1,X,I),
    element(P2,X,J),
    abs(P1-P2) #= I
  end,
  solve(X),
  println(N=X),
  fail,
  nl.