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


import strformat
 
const maxBest = 32
var best: array[maxBest, int]
 
proc trySwaps(deck: seq[int], f, d, n: int) =
  if d > best[n]:
    best[n] = d
 
  for i in countdown(n - 1, 0):
    if deck[i] == -1 or deck[i] == i:
      break
    if d + best[i] <= best[n]:
      return
 
  var deck2 = deck
  for i in 1..<n:
    var k = 1 shl i
    if deck2[i] == -1:
      if (f and k) != 0:
        continue
    elif deck2[i] != i:
      continue
 
    deck2[0] = i
    for j in countdown(i - 1, 0):
      deck2[i - j] = deck[j]
    trySwaps(deck2, f or k, d + 1, n)
 
proc topswops(n: int): int =
  assert(n > 0 and n < maxBest)
  best[n] = 0
  var deck0 = newSeq[int](n + 1)
  for i in 1..<n:
    deck0[i] = -1
  trySwaps(deck0, 1, 0, n)
  best[n]
 
for i in 1..10:
  echo &"{i:2}: {topswops(i):2}"