Topswops

Topswops
You are encouraged to solve this task according to the task description, using any language you may know.

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 Pfannkuchen meaning pancake.

Cf.

• Number reversal game
• Sorting algorithms/Pancake sort

C

I don't remember how this code actually works, being an old posting and all, but the results seem right: <lang c>#include <stdio.h>

typedef unsigned char elem;

elem s[16], t[16]; size_t max_n, maxflips;

int flip() { register int i; register elem *x, *y, c;

for (i = 0; i < max_n; i++) if (s[i] == i) return 0;

for (x = t, y = s; i--;) *x++ = *y++;

i = 1; do { for (x = t, y = t + t[0]; x < y; ) c = *x, *x++ = *y, *y-- = c; i++; } while (t[t[0]]);

return i; }

inline void rotate(int n) { elem c; register int i; c = s[0]; for (i = 1; i <= n; i++) s[i-1] = s[i]; s[n] = c; }

/* Tompkin-Paige iterative perm generation */ void tk(int n) { int i = 0, f; maxflips = 0;

elem c[16] = { 0 };

while (i < n) { rotate(i); if (c[i] >= i) { c[i++] = 0; continue; }

c[i]++; i = 1; if (*s) { f = s[s[0]] ? flip() : 1; if (f > maxflips) maxflips = f; } } }

int main(void) { int i; for (max_n = 1; max_n <= 12; max_n++) { for (i = 0; i < max_n; i++) s[i] = i; tk(max_n); printf("Pfannkuchen(%d) = %d\n", max_n, maxflips); }

return 0; }</lang>

Output:

Pfannkuchen(1) = 0
Pfannkuchen(2) = 1
Pfannkuchen(3) = 2
Pfannkuchen(4) = 4
Pfannkuchen(5) = 7
Pfannkuchen(6) = 10
Pfannkuchen(7) = 16
Pfannkuchen(8) = 22
Pfannkuchen(9) = 30
Pfannkuchen(10) = 38
Pfannkuchen(11) = 51
Pfannkuchen(12) = 65

A much faster algorithm that doesn't go through all permutations, per Knuth tAoCP 7.2.1.2 exercise 107 (possible bad implementation on my part notwithstanding): <lang c>#include <stdio.h>

1. include <string.h>

typedef struct { char v[16]; } deck;

int n, d, best[16];

void tryswaps(deck *a, int f, int s) { deck b = *a; char*const A = a->v; char*const B = b.v; register int i, j, k;

if (d > best[n]) best[n] = d;

do { if (A[s] == -1 || A[s] == s) break; if (d + best[s] <= best[n]) return; } while (s--);

d++; for (i = 1, k = 2; i <= s; i++, k <<= 1) { if (B[i] == -1) { if (f & k) continue; } else if (B[i] != i) continue;

B[0] = j = i; while (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++) { d = 0; tryswaps(&x, 1, n - 1); printf("%2d: %d\n", n, best[n]); }

return 0; }</lang>

D

Permutations generator from: http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version <lang d>import std.stdio, std.algorithm, std.range, permutations2;

uint topswops(in uint n) in {

   assert (n > 0 && n < 32);

} body {

   static uint flip(uint[] deck) pure nothrow {
       uint[32] temp = void;
       temp[0 .. deck.length] = deck[];
       uint count = 0;
       for (auto t0 = temp[0]; t0; t0 = temp[0]) {
           temp[0 .. t0 + 1].reverse(); // Slow with DMD.
           count++;
       }
       return count;
   }

   return iota(n).array().permutations!0().map!flip().reduce!max();

}

void main() {

   foreach (i; 1 .. 11)
       writefln("%d => %d", i, topswops(i));

}</lang>

Output:

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

D: Faster Version

Translation of: C

<lang d>uint topswops(in size_t n) nothrow {

   size_t d = 0;
   __gshared uint[16] best;

   alias T = byte;
   alias Deck = T[16];

   void trySwaps(in ref Deck deck, in uint f, in uint s) nothrow {
       if (d > best[n])
           best[n] = d;

       foreach_reverse (immutable i; 0 .. s + 1) {
           if (deck[i] == -1 || deck[i] == i)
               break;
           if (d + best[i] <= best[n])
               return;
       }

       Deck deck2 = deck;

       d++;
       uint k = 1;
       foreach (immutable i; 1 .. s + 1) {
           k <<= 1;
           if (deck2[i] == -1) {
               if (f & k)
                   continue;
           } else if (deck2[i] != i)
               continue;

           deck2[0] = cast(T)i;
           foreach_reverse (immutable j; 0 .. i)
               deck2[i - j] = deck[j];
           trySwaps(deck2, f | k, s);
       }
       d--;
   }

   best[n] = 0;
   Deck deck0 = -1;
   deck0[0] = 0;
   trySwaps(deck0, 1, n - 1);
   return best[n];

}

import std.stdio;

void main() {

   foreach (i; 1 .. 13)
       writefln("%2d: %d", i, topswops(i));

}</lang>

Output:

 1: 0
 2: 1
 3: 2
 4: 4
 5: 7
 6: 10
 7: 16
 8: 22
 9: 30
10: 38
11: 51
12: 65

Go

<lang go>// Adapted from http://www-cs-faculty.stanford.edu/~uno/programs/topswops.w // at Donald Knuth's web site. Algorithm credited there to Pepperdine // and referenced to Mathematical Gazette 73 (1989), 131-133. package main

import "fmt"

const ( // array sizes

   maxn = 10 // max number of cards
   maxl = 50 // upper bound for number of steps

)

func main() {

   for i := 1; i <= maxn; i++ {
       fmt.Printf("%d: %d\n", i, steps(i))
   }

}

func steps(n int) int {

   var a, b [maxl][maxn + 1]int
   var x [maxl]int
   a[0][0] = 1
   var m int
   for l := 0; ; {
       x[l]++
       k := int(x[l])
       if k >= n {
           if l <= 0 {
               break
           }
           l--
           continue
       }
       if a[l][k] == 0 {
           if b[l][k+1] != 0 {
               continue
           }
       } else if a[l][k] != k+1 {
           continue
       }
       a[l+1] = a[l]
       for j := 1; j <= k; j++ {
           a[l+1][j] = a[l][k-j]
       }
       b[l+1] = b[l]
       a[l+1][0] = k + 1
       b[l+1][k+1] = 1
       if l > m-1 {
           m = l + 1
       }
       l++
       x[l] = 0
   }
   return m

}</lang>

Output:

1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38

J

Solution:<lang j> swops =: ((|.@:{. , }.)~ {.)^:a:</lang> Example (from task introduction):<lang j> swops 2 4 1 3 2 4 1 3 4 2 1 3 3 1 2 4 2 1 3 4 1 2 3 4</lang> Example (topswops of all permutations of the integers 1..10):<lang j> (,. _1 + ! >./@:(#@swops@A. >:)&i. ])&> 1+i.10

1  0
2  1
3  2
4  4
5  7
6 10
7 16
8 22
9 30

10 38</lang>

Java

Works with: Java version 1.5+

Some of this code was copied from Utils.java. It uses a lot of memory and should probably be replaced with something that works better, but it's a start. <lang java5>import java.util.ArrayList; import java.util.Collections;

public class Topswops{ private static <T extends Comparable<? super T>> boolean nextPerm(ArrayList<T> data){ // find the swaps int c = -1, d = data.size(); for(int i = d - 2; i >= 0; i--) if(data.get(i).compareTo(data.get(i + 1)) < 0){ c = i; break; }

if(c < 0) return false;

int s = c + 1; for(int j = c + 2; j < d; j++) if(data.get(j).compareTo(data.get(s)) < 0 && data.get(j).compareTo(data.get(c)) > 0) s = j;

// do the swaps Collections.swap(data, c, s); while (--d > ++c) Collections.swap(data, c, d);

return true; }

private static <T extends Comparable<? super T>> ArrayList<ArrayList<T>> permutations(ArrayList<T> d){ ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); Collections.sort(d); do{ result.add(new ArrayList<T>(d)); }while(nextPerm(d)); return result; }

public static int topswops(int n){ int retVal = 0; ArrayList<Integer> orig = new ArrayList<Integer>(n); for(int i = 1; i <= n; i++){ orig.add(i); //build the original list } ArrayList<ArrayList<Integer>> perms = permutations(orig); for(ArrayList<Integer> perm : perms){ int swaps = run(perm); if(swaps > retVal) retVal = swaps; }

return retVal; }

private static int run(ArrayList<Integer> perm){ int count = 0; int first = perm.get(0); while(first != 1){ count++; ArrayList<Integer> swapMe = new ArrayList<Integer>(); for(int i = 0; i < first; i++){ swapMe.add(perm.remove(0)); //grab the section that needs to be reversed } Collections.reverse(swapMe); perm.addAll(0, swapMe); //put it back at the start first = perm.get(0); //get the new first element } return count; }

public static void main(String[] args){ for(int i = 1; i <= 10; i++){ System.out.println(i + ": " + topswops(i)); } }

}</lang> Output:

1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38

Perl 6

<lang perl6>sub postfix:<!>(@a) {

   @a == 1
       ?? [@a]
       !! do for @a -> $a {
               [ $a, @$_ ] for @a.grep(* != $a)!
          }

}

sub swops(@a is copy) {

   my $count = 0;
   until @a[0] == 1 {
       @a[ ^@a[0] ] .= reverse;
       $count++;
   }
   return $count;

} sub topswops($n) { [max] map &swops, (1 .. $n)! }

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

Output follows that of Python.

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>

Python: Faster Version

Translation of: C

<lang python>try:

   import psyco
   psyco.full()

except ImportError:

   pass

best = [0] * 16

def try_swaps(deck, f, s, d, n):

   if d > best[n]:
       best[n] = d

   i = 0
   k = 1 << s
   while s:
       k >>= 1
       s -= 1
       if deck[s] == -1 or deck[s] == s:
           break
       i |= k
       if (i & f) == i and d + best[s] <= best[n]:
           return d
   s += 1

   deck2 = list(deck)
   k = 1
   for i2 in xrange(1, s):
       k <<= 1
       if deck2[i2] == -1:
           if f & k: continue
       elif deck2[i2] != i2:
           continue

       deck[i2] = i2
       deck2[0:i2+1] = reversed(deck[0:i2+1])
       try_swaps(deck2, f | k, s, 1 + d, n)

def topswops(n):

   best[n] = 0
   deck0 = [-1] * 16
   deck0[0] = 0
   try_swaps(deck0, 1, n, 0, n)
   return best[n]

for i in xrange(1, 13):

   print "%2d: %d" % (i, topswops(i))</lang>

Output:

 1: 0
 2: 1
 3: 2
 4: 4
 5: 7
 6: 10
 7: 16
 8: 22
 9: 30
10: 38
11: 51
12: 65

XPL0

<lang XPL0>code ChOut=8, CrLf=9, IntOut=11; int N, Max, Card1(16), Card2(16);

proc Topswop(D); \Conway's card swopping game int D; \depth of recursion int I, J, C, T; [if D # N then \generate N! permutations of 1..N in Card1

    [for I:= 0 to N-1 do
       [for J:= 0 to D-1 do    \check if object (letter) already used
           if Card1(J) = I+1 then J:=100;
       if J < 100 then
           [Card1(D):= I+1;    \card number not used so append it
           Topswop(D+1);       \recurse next level deeper
           ];
       ];
    ]

else [\determine number of topswops to get card 1 at beginning

    for I:= 0 to N-1 do Card2(I):= Card1(I);   \make working copy of deck
       C:= 0;                  \initialize swop counter
       while Card2(0) # 1 do
           [I:= 0;  J:= Card2(0)-1;
           while I < J do
               [T:= Card2(I);  Card2(I):= Card2(J);  Card2(J):= T;
               I:= I+1;  J:= J-1;
               ];
           C:= C+1;
           ];  
    if C>Max then Max:= C;
    ];

];

[for N:= 1 to 10 do

   [Max:= 0;
   Topswop(0);
   IntOut(0, N);  ChOut(0, ^ );  IntOut(0, Max);  CrLf(0);
   ];

]</lang>

Output:

1 0
2 1
3 2
4 4
5 7
6 10
7 16
8 22
9 30
10 38