Topswops

Topswops is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.

Cf.

• Number reversal game
• Sorting algorithms/Pancake sort

Perl 6

Straightforward implementation. Very slow. <lang perl6>sub postfix:<!>(@a) {

   @a == 1 ?? [@a] !!
   gather for @a -> $a {
       take [ $a, @$_ ] for grep(none($a), @a)!
   }

}

sub shuffle(@a) {

   my $count = 0;
   until @a[0] == 1 {
       @a = (@a.shift xx @a[0]).reverse, @a;
       $count++;
   }
   return $count;

} sub topswops($n) { max map &shuffle, (1 .. $n)! }

say "$_ {topswops $_}" for 1 .. 10;</lang>

Python

This solution uses cards numbered from 0..n-1 and variable p0 is introduced as a speed optimisation <lang python>>>> from itertools import permutations >>> def f1(p): i, p0 = 0, p[0] while p0: i += 1 p0 += 1 p[:p0] = p[:p0][::-1] p0 = p[0] return i

>>> def fannkuch(n): return max(f1(list(p)) for p in permutations(range(n)))

>>> for n in range(1, 11): print(n,fannkuch(n))

1 0 2 1 3 2 4 4 5 7 6 10 7 16 8 22 9 30 10 38 >>> </lang>