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


V best = [0] * 16
 
F try_swaps(&deck, f, =s, d, n)
   I d > :best[n]
      :best[n] = d
 
   V i = 0
   V k = 1 << s
   L s != 0
      k >>= 1
      s--
      I deck[s] == -1 | deck[s] == s
         L.break
      i [|]= k
      I (i [&] f) == i & d + :best[s] <= :best[n]
         R d
   s++
 
   V deck2 = copy(deck)
   k = 1
   L(i2) 1 .< s
      k <<= 1
      I deck2[i2] == -1
         I (f [&] k) != 0
            L.continue
      E I deck2[i2] != i2
         L.continue
 
      deck[i2] = i2
      L(j) 0 .. i2
         deck2[j] = deck[i2 - j]
      try_swaps(&deck2, f [|] k, s, 1 + d, n)
 
F topswops(n)
   :best[n] = 0
   V deck0 = [-1] * 16
   deck0[0] = 0
   try_swaps(&deck0, 1, n, 0, n)
   R :best[n]
 
L(i) 1..12
   print(‘#2: #.’.format(i, topswops(i)))