/* 

  Topswops (Rosetta Code) in Picat.

  From http://rosettacode.org/wiki/Topswops
  """
  Topswops is a card game created by John Conway in the 1970's.

  Assume you have a particular permutation of a set of n cards numbered 1..n 
  on both of their faces, for example the arrangement of four cards given 
  by [2, 4, 1, 3] where the leftmost card is on top. A round is composed 
  of reversing the first m cards where m is the value of the topmost card. 
  rounds are repeated until the topmost card is the number 1 and the number 
  of swaps is recorded. For our example the swaps produce:

    [2, 4, 1, 3]    # Initial shuffle
    [4, 2, 1, 3]
    [3, 1, 2, 4]
    [2, 1, 3, 4]
    [1, 2, 3, 4]

  For a total of four swaps from the initial ordering to produce the 
  terminating case where 1 is on top.


  For a particular number n of cards, topswops(n) is the maximum swaps needed 
  for any starting permutation of the n cards.

  Task

  The task is to generate and show here a table of n vs topswops(n) for n 
  in the range 1..10 inclusive.

  Note

  Topswops is also known as Fannkuch from the German Pfannkuchen meaning pancake.
  """

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

*/


import util.


main => time(go).


go =>
  foreach(N in 1..10)     
      Perm = 1..N,
      Rev = Perm.reverse(),
      Max = 0,
      MaxPerm = [],
      while(Perm != Rev)
         Perm := next_permutation(Perm),
         C = topswops(Perm),
         if C > Max then
           Max := C
         end
      end,
      println([N,Max])
  end,
  
  nl.

go1 => 
  N = 10,
  Perm = 1..N,
  Rev = Perm.reverse(),
  Max = 0,
  while(Perm != Rev)
    Perm := next_permutation(Perm),
    C = topswops(Perm),
    if C > Max then Max := C end
  end,
  nl.
  
/*
  The max number of swaps needed, and the permutations(s):

   [1,0,[[1]]]
   [2,1,[[2,1]]]
   [3,2,[[2,3,1],[3,1,2]]]
   [4,4,[[3,1,4,2],[2,4,1,3]]]
   [5,7,[[3,1,4,5,2]]]
   [6,10,[[4,1,5,2,6,3],[4,5,6,2,1,3],[5,6,4,1,3,2],[4,1,6,5,2,3],[3,6,5,1,4,2]]]
   [7,16,[[3,1,4,6,7,5,2],[4,7,6,2,1,5,3]]]
   [8,22,[[6,1,5,7,8,3,2,4]]]
   [9,30,[[6,1,5,9,7,2,8,3,4]]]
   [10,38,[[5,9,1,8,6,2,10,4,7,3]]]

*/
go2 =>
  foreach(N in 1..10) 
      Max = 0,
      MaxPerm = [],
      foreach(Perm in permutations(1..N))
         C = topswops(Perm),
         if C > Max then
            Max := C,
            MaxPerm := [Perm]
         elseif C == Max then
            MaxPerm := MaxPerm ++ [Perm]
         end
      end,
      println([N,Max,MaxPerm])
  end,
  
  nl.


go3 =>
  foreach(N in 1..10)     
      Max = max([topswops(Perm) : Perm in permutations(1..N)]),
      println([N,Max])
  end,  
  nl.

/*

Print all steps for a specific instance, here [4,9,3,6,7,5,2,1,8]:

   [4,9,3,6,7,5,2,1,8]
   [6,3,9,4,7,5,2,1,8]
   [5,7,4,9,3,6,2,1,8]
   [3,9,4,7,5,6,2,1,8]
   [4,9,3,7,5,6,2,1,8]
   [7,3,9,4,5,6,2,1,8]
   [2,6,5,4,9,3,7,1,8]
   [6,2,5,4,9,3,7,1,8]
   [3,9,4,5,2,6,7,1,8]
   [4,9,3,5,2,6,7,1,8]
   [5,3,9,4,2,6,7,1,8]
   [2,4,9,3,5,6,7,1,8]
   [4,2,9,3,5,6,7,1,8]
   [3,9,2,4,5,6,7,1,8]
   [2,9,3,4,5,6,7,1,8]
   [9,2,3,4,5,6,7,1,8]
   [8,1,7,6,5,4,3,2,9]
   [2,3,4,5,6,7,1,8,9]
   [3,2,4,5,6,7,1,8,9]
   [4,2,3,5,6,7,1,8,9]
   [5,3,2,4,6,7,1,8,9]
   [6,4,2,3,5,7,1,8,9]
   [7,5,3,2,4,6,1,8,9]
   [1,6,4,2,3,5,7,8,9]
   len = 24

*/
go4 ?=>
   Perm =  [4,9,3,6,7,5,2,1,8],
   topswops_steps(Perm) = Steps,
   foreach(Step in Steps)
      println(Step)
   end,
   println(len=Steps.len),
   nl.
go4 => true.

% Show all the steps
topswops_steps(Perm) = Steps => 
   P = Perm,
   Len = P.length,
   Count = 0,
   Ps = [Perm],
   while (P[1] > 1)
      Pos = P[1],
      P := [P[I] : I in 1..Pos].reverse() ++ [P[I] : I in Pos+1..Len],
      Ps := Ps ++ [P],
      Count := Count + 1 
   end,
   Steps = Ps.


topswops([]) = 0 => true.
topswops([1]) = 0 => true.
topswops([1|_]) = 0 => true.
topswops(Perm) = Count =>  
   P = Perm,
   Len = P.length,
   Count = 0,
   while (P[1] > 1)
      Pos = P[1],
      P := [P[I] : I in 1..Pos].reverse() ++ [P[I] : I in Pos+1..Len],
      Count := Count + 1 
   end.

all_placed(Perm) =>
  foreach(I in 1..Perm.length)
     Perm[I] = I
  end.


next_permutation(P) = Perm =>
   Perm1 = P,
   N = Perm1.length,
   K = N - 1,
   while (Perm1[K] > Perm1[K+1], K >= 0) 
      K := K - 1
   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.