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 word   Pfannkuchen   meaning   pancake.



Related tasks

   Number reversal game
   Sorting algorithms/Pancake sort


code ChOut=8, CrLf=9, IntOut=11;
int  N, Max, Card1(16), Card2(16);
 
proc Topswop(D);        \Conway's card swopping game
int  D;                 \depth of recursion
int  I, J, C, T;
[if D # N then                  \generate N! permutations of 1..N in Card1
     [for I:= 0 to N-1 do
        [for J:= 0 to D-1 do    \check if object (letter) already used
            if Card1(J) = I+1 then J:=100;
        if J < 100 then
            [Card1(D):= I+1;    \card number not used so append it
            Topswop(D+1);       \recurse next level deeper
            ];
        ];
     ]
else [\determine number of topswops to get card 1 at beginning
     for I:= 0 to N-1 do Card2(I):= Card1(I);   \make working copy of deck
        C:= 0;                  \initialize swop counter
        while Card2(0) # 1 do
            [I:= 0;  J:= Card2(0)-1;
            while I < J do
                [T:= Card2(I);  Card2(I):= Card2(J);  Card2(J):= T;
                I:= I+1;  J:= J-1;
                ];
            C:= C+1;
            ];  
     if C>Max then Max:= C;
     ];
];
 
[for N:= 1 to 10 do
    [Max:= 0;
    Topswop(0);
    IntOut(0, N);  ChOut(0, ^ );  IntOut(0, Max);  CrLf(0);
    ];
]