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


#include <stdio.h>
#include <string.h>
 
typedef struct { char v[16]; } deck;
typedef unsigned int uint;
 
uint n, d, best[16];
 
void tryswaps(deck *a, uint f, uint s) {
#	define A a->v
#	define B b.v
	if (d > best[n]) best[n] = d;
	while (1) {
		if ((A[s] == s || (A[s] == -1 && !(f & 1U << s)))
			&& (d + best[s] >= best[n] || A[s] == -1))
			break;
 
		if (d + best[s] <= best[n]) return;
		if (!--s) return;
	}
 
	d++;
	deck b = *a;
	for (uint i = 1, k = 2; i <= s; k <<= 1, i++) {
		if (A[i] != i && (A[i] != -1 || (f & k)))
			continue;
 
		for (uint j = B[0] = i; j--;) B[i - j] = A[j];
		tryswaps(&b, f | k, s);
	}
	d--;
}
 
int main(void) {
	deck x;
	memset(&x, -1, sizeof(x));
	x.v[0] = 0;
 
	for (n = 1; n < 13; n++) {
		tryswaps(&x, 1, n - 1);
		printf("%2d: %d\n", n, best[n]);
	}
 
	return 0;
}