/* 

  Perfect shuffle (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Perfect_shuffle
  """
  The Task

  - Write a function that can perform a perfect shuffle on an even-sized list of values.
  - Call this function repeatedly to count how many shuffles are needed to get a deck 
    back to its original order, for each of the deck sizes listed under "Test Cases" below.
    You can use a list of numbers (or anything else that's convenient) to represent a deck; 
    just make sure that all "cards" are unique within each deck.
    Print out the resulting shuffle counts, to demonstrate that your program passes 
    the test-cases.

   Test Cases

                    input (deck size) 	output (number of shuffles required)
                    8 	3
                    24 	11
                    52 	8
                    100 	30
                    1020 	1018
                    1024 	10
                    10000 	300 
  """


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

*/


main => go.

/*
  A perfect shuffle can be done in two ways:
  - in: first card in top half is the first card in the new deck
  - out: first card in bottom half is the first card in the new deck

  The method here supports both versions. The task states an out shuffling. 

*/

go => 
   member(N,[8,24,52,100,1020,1024,10_000]),
   println(n=N),
   InOut = out, % in/out shuffling
   println(inOut=InOut),
   Print = cond(N < 100, true,false),
   if Print then
     println(1..N),
   end,
   Count = show_all_shuffles(N,InOut,Print),
   println(count=Count),
   nl,
   fail,
   nl.

go2 => 
   N = 8,
   println(1..N),
   InOut = in, % in shuffling
   Count = show_all_shuffles(N,InOut,true),
   println(count=Count),
   nl.


% Also, the method supports decks of uneven lengths.
go3 => 
   N = 11,
   InOut = out, % in/out shuffling
   Count = show_all_shuffles(N,InOut,true),
   println(count=Count),
   nl.

%
% Show all the shuffles
%
show_all_shuffles(N,InOut) = show_all_shuffles(N,InOut,false).
show_all_shuffles(N,InOut,Print) = Count =>
   Order = 1..N,
   Perfect1 = perfect_shuffle(1..N,InOut),   
   Perfect = copy_term(Perfect1),
   if Print == true then
     println(Perfect)
   end,
   Count = 1,
   while (Perfect != Order) 
     Perfect := [Perfect1[Perfect[I]] : I in 1..N],
     if Print == true then
       println(Perfect)
     end,
     Count := Count + 1
   end.

%
% Perfect shuffle a list
%
% InOut = in|out
%  in: first card in Top half is the first card in the new deck
%  out: first card in Bottom half is the first card in the new deck
%
perfect_shuffle(List,InOut) = Perfect =>
   [Top,Bottom] = split_deck(List,InOut),
   if InOut = out then
     Perfect = zip2(Top,Bottom)
   else
     Perfect = zip2(Bottom,Top)
   end.

%
% split the deck in two "halves"
% 
% For odd out shuffles, we have to adjust the
% range of the top and bottom.
%
split_deck(L,InOut) = [Top,Bottom] => 
  N = L.len,
  if InOut = out, N mod 2 = 1 then 
    Top = 1..(N div 2)+1,
    Bottom = (N div 2)+2..N
  else
    Top = 1..(N div 2),
    Bottom = (N div 2)+1..N
  end.


%
% If L1 and L2 has uneven lengths, we add the odd element last 
% in the resulting list.
%
zip2(L1,L2) = R => 
  L1Len = L1.len,
  L2Len = L2.len,
  R1 = [],
  foreach(I in 1..min(L1Len,L2Len))
    R1 := R1 ++ [L1[I],L2[I]]
  end,
  if L1Len < L2Len then
    R1 := R1 ++ [L2[L2Len]]
  elseif L1Len > L2Len then
    R1 := R1 ++ [L1[L1Len]]
  end,
  R = R1.