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 "/fmt" for Fmt
 
var maxn = 10
var maxl = 50
 
var steps = Fn.new { |n|
    var a = List.filled(maxl, null)
    var b = List.filled(maxl, null)
    var x = List.filled(maxl, 0)
    for (i in 0...maxl) {
        a[i] = List.filled(maxn + 1, 0)
        b[i] = List.filled(maxn + 1, 0)
    }
    a[0][0] = 1
    var m = 0
    var l = 0
    while (true) {
        x[l] = x[l] + 1
        var k = x[l]
        var cont = false
        if (k >= n) {
            if (l <= 0) break
            l = l - 1
            cont = true
        } else if (a[l][k] == 0) {
            if (b[l][k+1] != 0) cont = true
        } else if (a[l][k] != k + 1) {
            cont = true
        }
        if (!cont) {
            a[l+1] = a[l].toList
            var j = 1
            while (j <= k) {
                a[l+1][j] = a[l][k-j]
                j = j + 1
            }
            b[l+1] = b[l].toList
            a[l+1][0] = k + 1
            b[l+1][k+1] = 1
            if (l > m - 1) {
                m = l + 1
            }
            l = l + 1
            x[l] = 0
        }
    }
    return m
}
 
for (i in 1..maxn) Fmt.print("$2d: $d", i, steps.call(i))