# 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.

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.

## 360 Assembly

The program uses two ASSIST macro (XDECO,XPRNT) to keep the code as short as possible.

`*        Topswops optimized        12/07/2016TOPSWOPS CSECT         USING  TOPSWOPS,R13       base register         B      72(R15)            skip savearea         DC     17F'0'             savearea         STM    R14,R12,12(R13)    prolog         ST     R13,4(R15)         " <-         ST     R15,8(R13)         " ->         LR     R13,R15            " addressability         MVC    N,=F'1'            n=1LOOPN    L      R4,N               n; do n=1 to 10  ===-------------==*         C      R4,=F'10'          "                                  *         BH     ELOOPN             .                                  *         MVC    P(40),PINIT        p=pinit         MVC    COUNTM,=F'0'       countm=0REPEAT   MVC    CARDS(40),P        cards=p  -------------------------+         SR     R11,R11            count=0                           |WHILE    CLC    CARDS,=F'1'        do while cards(1)^=1  ---------+         BE     EWHILE             .                              |         MVC    M,CARDS            m=cards(1)         L      R2,M               m         SRA    R2,1               m/2         ST     R2,MD2             md2=m/2         L      R3,M               @card(mm)=m         SLA    R3,2               *4         LA     R3,CARDS-4(R3)     @card(mm)         LA     R2,CARDS           @card(i)=0         LA     R6,1               i=1LOOPI    C      R6,MD2             do i=1 to m/2  -------------+         BH     ELOOPI             .                           |         L      R0,0(R2)           swap r0=cards(i)         MVC    0(4,R2),0(R3)      swap cards(i)=cards(mm)         ST     R0,0(R3)           swap cards(mm)=r0         AH     R2,=H'4'           @card(i)[email protected](i)+4         SH     R3,=H'4'           @card(mm)[email protected](mm)-4         LA     R6,1(R6)           i=i+1                       |         B      LOOPI              ----------------------------+ELOOPI   LA     R11,1(R11)         count=count+1                  |         B      WHILE              -------------------------------+EWHILE   C      R11,COUNTM         if count>countm         BNH    NOTGT              then         ST     R11,COUNTM           countm=countNOTGT    BAL    R14,NEXTPERM       call nextperm         LTR    R0,R0              until nextperm=0                 |         BNZ    REPEAT             ---------------------------------+         L      R1,N               n         XDECO  R1,XDEC            edit n         MVC    PG(2),XDEC+10      output n         MVI    PG+2,C':'          output ':'         L      R1,COUNTM          countm         XDECO  R1,XDEC            edit countm         MVC    PG+3(4),XDEC+8     output countm         XPRNT  PG,L'PG            print buffer         L      R1,N               n                                  *         LA     R1,1(R1)           +1                                 *         ST     R1,N               n=n+1                              *         B      LOOPN              ===------------------------------==*ELOOPN   L      R13,4(0,R13)       epilog          LM     R14,R12,12(R13)    " restore         XR     R15,R15            " rc=0         BR     R14                exitPINIT    DC     F'1',F'2',F'3',F'4',F'5',F'6',F'7',F'8',F'9',F'10'CARDS    DS     10F                cardsP        DS     10F                pCOUNTM   DS     F                  countmM        DS     F                  mN        DS     F                  nMD2      DS     F                  m/2PG       DC     CL20' '            bufferXDEC     DS     CL12               temp*------- ----   nextperm ----------{-----------------------------------NEXTPERM L      R9,N               nn=n         SR     R8,R8              jj=0         LR     R7,R9              nn         BCTR   R7,0               j=nn-1         LTR    R7,R7              if j=0         BZ     ELOOPJ1            then skip do loopLOOPJ1   LR     R1,R7              do j=nn-1 to 1 by -1; j ----+         SLA    R1,2               .                           |         L      R2,P-4(R1)         p(j)         C      R2,P(R1)           if p(j)<p(j+1)         BNL    PJGEPJP            then         LR     R8,R7                jj=j         B      ELOOPJ1              leave j                   |PJGEPJP  BCT    R7,LOOPJ1          j=j-1  ---------------------+ELOOPJ1  LA     R7,1(R8)           j=jj+1LOOPJ2   CR     R7,R9              do j=jj+1 while j<nn  ------+         BNL    ELOOPJ2            .                           |         LR     R2,R7              j         SLA    R2,2               .         LR     R3,R9              nn         SLA    R3,2               .         L      R0,P-4(R2)         swap p(j),p(nn)         L      R1,P-4(R3)         "         ST     R0,P-4(R3)         "         ST     R1,P-4(R2)         "         BCTR   R9,0               nn=nn-1         LA     R7,1(R7)           j=j+1                       |         B      LOOPJ2             ----------------------------+ELOOPJ2  LTR    R8,R8              if jj=0         BNZ    JJNE0              then         LA     R0,0                 return(0)         BR     R14                  "JJNE0    LA     R7,1(R8)           j=jj+1         LR     R2,R7              j         SLA    R2,2               [email protected](j)         LR     R3,R8              jj         SLA    R3,2               [email protected](jj)LOOPJ3   L      R0,P-4(R2)         p(j)  ----------------------+                              C      R0,P-4(R3)         do j=jj+1 while p(j)<p(jj)  |         BNL    ELOOPJ3         LA     R2,4(R2)           [email protected](j)[email protected](j)+4         LA     R7,1(R7)           j=j+1                       |         B      LOOPJ3             ----------------------------+ELOOPJ3  L      R1,P-4(R3)         swap p(j),p(jj)         ST     R0,P-4(R3)         "         ST     R1,P-4(R2)         "         LA     R0,1               return(1)         BR     R14 ---------------}-----------------------------------         YREGS         END    TOPSWOPS`
Output:
``` 1:   0
2:   1
3:   2
4:   4
5:   7
6:  10
7:  16
8:  22
9:  30
10:  38
```

This is a straightforward approach that counts the number of swaps for each permutation. To generate all permutations over 1 .. N, for each of N in 1 .. 10, the package Generic_Perm from the Permutations task is used [[1]].

`with Ada.Integer_Text_IO, Generic_Perm; procedure Topswaps is    function Topswaps(Size: Positive) return Natural is      package Perms is new Generic_Perm(Size);      P: Perms.Permutation;      Done: Boolean;      Max: Natural;       function Swapper_Calls(P: Perms.Permutation) return Natural is	 Q: Perms.Permutation := P;	 I: Perms.Element := P(1);      begin	 if I = 1 then 	    return 0;	 else	    for Idx in 1 .. I loop	       Q(Idx) := P(I-Idx+1);	    end loop;	    return 1 + Swapper_Calls(Q);	 end if;      end Swapper_Calls;    begin      Perms.Set_To_First(P, Done);      Max:= Swapper_Calls(P);      while not Done loop	 Perms.Go_To_Next(P, Done);	 Max := natural'Max(Max, Swapper_Calls(P));      end loop;      return Max;   end Topswaps; begin   for I in 1 .. 10 loop      Ada.Integer_Text_IO.Put(Item => Topswaps(I), Width => 3);   end loop;end Topswaps;`
Output:
`  0  1  2  4  7 10 16 22 30 38`

## AutoHotkey

`Topswops(Obj, n){	R := []	for i, val in obj{		if (i <=n)			res := val (A_Index=1?"":",") res		else			res .= "," val 	}	Loop, Parse, res, `,		R[A_Index]:= A_LoopField	return R}`
Examples:
`Cards := [2, 4, 1, 3]Res := Print(Cards)while (Cards[1]<>1){	Cards := Topswops(Cards, Cards[1])	Res .= "`n"Print(Cards)}MsgBox % Res Print(M){	for i, val in M			Res .= (A_Index=1?"":"`t") val	return Trim(Res,"`n")}`
Outputs:
```2	4	1	3
4	2	1	3
3	1	2	4
2	1	3	4
1	2	3	4```

## C

An algorithm that doesn't go through all permutations, per Knuth tAoCP 7.2.1.2 exercise 107 (possible bad implementation on my part notwithstanding):

`#include <stdio.h>#include <string.h> typedef struct { char v[16]; } deck;typedef unsigned int uint; uint n, d, best[16]; void tryswaps(deck *a, uint f, uint s) {#	define A a->v#	define B b.v	if (d > best[n]) best[n] = d;	while (1) {		if ((A[s] == s || (A[s] == -1 && !(f & 1U << s)))			&& (d + best[s] >= best[n] || A[s] == -1))			break; 		if (d + best[s] <= best[n]) return;		if (!--s) return;	} 	d++;	deck b = *a;	for (uint i = 1, k = 2; i <= s; k <<= 1, i++) {		if (A[i] != i && (A[i] != -1 || (f & k)))			continue; 		for (uint j = B[0] = i; 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++) {		tryswaps(&x, 1, n - 1);		printf("%2d: %d\n", n, best[n]);	} 	return 0;}`

The code contains critical small loops, which can be manually unrolled for those with OCD. POSIX thread support is useful if you got more than one CPUs.

`#define _GNU_SOURCE#include <stdio.h>#include <string.h>#include <pthread.h>#include <sched.h> #define MAX_CPUS 8 // increase this if you got more CPUs/cores typedef struct { char v[16]; } deck; int n, best[16]; // Update a shared variable by spinlock.  Since this program really only// enters locks dozens of times, a pthread_mutex_lock() would work// equally fine, but RC already has plenty of examples for that.#define SWAP_OR_RETRY(var, old, new)					\	if (!__sync_bool_compare_and_swap(&(var), old, new)) {		\		volatile int spin = 64;					\		while (spin--);						\		continue; } void tryswaps(deck *a, int f, int s, int d) {#define A a->v#define B b->v 	while (best[n] < d) {		int t = best[n];		SWAP_OR_RETRY(best[n], t, d);	} #define TEST(x)									\	case x: if ((A[15-x] == 15-x || (A[15-x] == -1 && !(f & 1<<(15-x))))	\			&& (A[15-x] == -1 || d + best[15-x] >= best[n]))	\			break;							\		if (d + best[15-x] <= best[n]) return;				\		s = 14 - x 	switch (15 - s) {		TEST(0);  TEST(1);  TEST(2);  TEST(3);  TEST(4);		TEST(5);  TEST(6);  TEST(7);  TEST(8);  TEST(9);		TEST(10); TEST(11); TEST(12); TEST(13); TEST(14);		return;	}#undef TEST 	deck *b = a + 1;	*b = *a;	d++; #define FLIP(x)							\	if (A[x] == x || ((A[x] == -1) && !(f & (1<<x)))) {	\		B[0] = x;					\		for (int j = x; j--; ) B[x-j] = A[j];		\		tryswaps(b, f|(1<<x), s, d); }			\	if (s == x) return; 	FLIP(1);  FLIP(2);  FLIP(3);  FLIP(4);  FLIP(5);	FLIP(6);  FLIP(7);  FLIP(8);  FLIP(9);  FLIP(10);	FLIP(11); FLIP(12); FLIP(13); FLIP(14); FLIP(15);#undef FLIP} int num_cpus(void) {	cpu_set_t ct;	sched_getaffinity(0, sizeof(ct), &ct); 	int cnt = 0;	for (int i = 0; i < MAX_CPUS; i++)		if (CPU_ISSET(i, &ct))			cnt++; 	return cnt;} struct work { int id; deck x[256]; } jobs[MAX_CPUS];int first_swap; void *thread_start(void *arg) {	struct work *job = arg;	while (1) {		int at = first_swap;		if (at >= n) return 0; 		SWAP_OR_RETRY(first_swap, at, at + 1); 		memset(job->x, -1, sizeof(deck));		job->x[0].v[at] = 0;		job->x[0].v[0] = at;		tryswaps(job->x, 1 | (1 << at), n - 1, 1);	}} int main(void) {	int n_cpus = num_cpus(); 	for (int i = 0; i < MAX_CPUS; i++)		jobs[i].id = i; 	pthread_t tid[MAX_CPUS]; 	for (n = 2; n <= 14; n++) {		int top = n_cpus;		if (top > n) top = n; 		first_swap = 1;		for (int i = 0; i < top; i++)			pthread_create(tid + i, 0, thread_start, jobs + i); 		for (int i = 0; i < top; i++)			pthread_join(tid[i], 0); 		printf("%2d: %2d\n", n, best[n]);	} 	return 0;}`

## C++

` #include <iostream>#include <vector>#include <numeric>#include <algorithm> int topswops(int n) {  std::vector<int> list(n);  std::iota(std::begin(list), std::end(list), 1);  int max_steps = 0;  do {    auto temp_list = list;    for (int steps = 1; temp_list[0] != 1; ++steps) {      std::reverse(std::begin(temp_list), std::begin(temp_list) + temp_list[0]);      if (steps > max_steps) max_steps = steps;    }  } while (std::next_permutation(std::begin(list), std::end(list)));  return max_steps;} int main() {  for (int i = 1; i <= 10; ++i) {    std::cout << i << ": " << topswops(i) << std::endl;  }  return 0;}`
Output:
```1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38```

## D

Permutations generator from: http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version

`import std.stdio, std.algorithm, std.range, permutations2; int topswops(in int n) pure @safe {    static int flip(int[] xa) pure nothrow @safe @nogc {        if (!xa[0]) return 0;        xa[0 .. xa[0] + 1].reverse();        return 1 + flip(xa);    }    return n.iota.array.permutations.map!flip.reduce!max;} void main() {    foreach (immutable i; 1 .. 11)        writeln(i, ": ", i.topswops);}`
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
`import std.stdio, std.typecons; __gshared uint[32] best; uint topswops(size_t n)() nothrow @nogc {    static assert(n > 0 && n < best.length);    size_t d = 0;     alias T = byte;    alias Deck = T[n];     void trySwaps(in ref Deck deck, in uint f) nothrow @nogc {        if (d > best[n])            best[n] = d;         foreach_reverse (immutable i; staticIota!(0, n)) {            if ((deck[i] == i || (deck[i] == -1 && !(f & (1U << i))))                && (d + best[i] >= best[n] || deck[i] == -1))            break;            if (d + best[i] <= best[n])                return;        }         Deck deck2 = void;        foreach (immutable i; staticIota!(0, n)) // Copy.            deck2[i] = deck[i];         d++;        foreach (immutable i; staticIota!(1, n)) {            enum uint k = 1U << i;            if (deck[i] != i && (deck[i] != -1 || (f & k)))                continue;             deck2[0] = T(i);            foreach_reverse (immutable j; staticIota!(0, i))                deck2[i - j] = deck[j]; // Reverse copy.            trySwaps(deck2, f | k);        }        d--;    }     best[n] = 0;    Deck deck0 = -1;    deck0[0] = 0;    trySwaps(deck0, 1);    return best[n];} void main() {    foreach (immutable i; staticIota!(1, 14))        writefln("%2d: %d", i, topswops!i());}`
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
13: 80```

With templates to speed up the computation, using the DMD compiler it's almost as fast as the second C version.

## Eiffel

` class	TOPSWOPS create	make feature 	make (n: INTEGER)			-- Topswop game.		local			perm, ar: ARRAY [INTEGER]			tcount, count: INTEGER		do			create perm_sol.make_empty			create solution.make_empty			across				1 |..| n as c			loop				create ar.make_filled (0, 1, c.item)				across					1 |..| c.item as d				loop					ar [d.item] := d.item				end				permute (ar, 1)				across					1 |..| perm_sol.count as e				loop					tcount := 0					from					until						perm_sol.at (e.item).at (1) = 1					loop						perm_sol.at (e.item) := reverse_array (perm_sol.at (e.item))						tcount := tcount + 1					end					if tcount > count then						count := tcount					end				end				solution.force (count, c.item)			end		end 	solution: ARRAY [INTEGER] feature {NONE} 	perm_sol: ARRAY [ARRAY [INTEGER]] 	reverse_array (ar: ARRAY [INTEGER]): ARRAY [INTEGER]			-- Array with 'ar[1]' elements reversed.		require			ar_not_void: ar /= Void		local			i, j: INTEGER		do			create Result.make_empty			Result.deep_copy (ar)			from				i := 1				j := ar [1]			until				i > j			loop				Result [i] := ar [j]				Result [j] := ar [i]				i := i + 1				j := j - 1			end		ensure			same_elements: across ar as a all Result.has (a.item) end		end 	permute (a: ARRAY [INTEGER]; k: INTEGER)			-- All permutations of array 'a' stored in perm_sol.		require			ar_not_void: a.count >= 1			k_valid_index: k > 0		local			i, t: INTEGER			temp: ARRAY [INTEGER]		do			create temp.make_empty			if k = a.count then				across					a as ar				loop					temp.force (ar.item, temp.count + 1)				end				perm_sol.force (temp, perm_sol.count + 1)			else				from					i := k				until					i > a.count				loop					t := a [k]					a [k] := a [i]					a [i] := t					permute (a, k + 1)					t := a [k]					a [k] := a [i]					a [i] := t					i := i + 1				end			end		end end `

Test:

` class	APPLICATION create	make feature 	make		do			create topswop.make (10)			across				topswop.solution as t			loop				io.put_string (t.item.out + "%N")			end		end 	topswop: TOPSWOPS end `
Output:
```0
1
2
4
7
10
16
22
30
38
```

## Elixir

Translation of: Erlang
`defmodule Topswops do  def get_1_first( [1 | _t] ), do: 0  def get_1_first( list ), do: 1 + get_1_first( swap(list) )   defp swap( [n | _t]=list ) do    {swaps, remains} = Enum.split( list, n )    Enum.reverse( swaps, remains )  end   def task do    IO.puts "N\ttopswaps"    Enum.map(1..10, fn n -> {n, permute(Enum.to_list(1..n))} end)    |> Enum.map(fn {n, n_permutations} -> {n, get_1_first_many(n_permutations)} end)    |> Enum.map(fn {n, n_swops} -> {n, Enum.max(n_swops)} end)    |> Enum.each(fn {n, max} -> IO.puts "#{n}\t#{max}" end)  end   def get_1_first_many( n_permutations ), do: (for x <- n_permutations, do: get_1_first(x))   defp permute([]), do: [[]]  defp permute(list), do: for x <- list, y <- permute(list -- [x]), do: [x|y]end Topswops.task`
Output:
```N       topswaps
1       0
2       1
3       2
4       4
5       7
6       10
7       16
8       22
9       30
10      38
```

## Erlang

This code is using the permutation code by someone else. Thank you.

` -module( topswops ). -export( [get_1_first/1, swap/1, task/0] ). get_1_first( [1 | _T] ) -> 0;get_1_first( List ) -> 1 + get_1_first( swap(List) ). swap( [N | _T]=List ) ->	{Swaps, Remains} = lists:split( N, List ),	lists:reverse( Swaps ) ++ Remains. task() ->	Permutations = [{X, permute:permute(lists:seq(1, X))} || X <- lists:seq(1, 10)],	Swops = [{N, get_1_first_many(N_permutations)} || {N, N_permutations} <- Permutations],	Topswops = [{N, lists:max(N_swops)} || {N, N_swops} <- Swops],	io:fwrite( "N	topswaps~n" ),	[io:fwrite("~p	~p~n", [N, Max]) || {N, Max} <- Topswops].   get_1_first_many( N_permutations ) -> [get_1_first(X) ||  X <- N_permutations]. `
Output:
```42> topswops:task().
N       topswaps
1       0
2       1
3       2
4       4
5       7
6       10
7       16
8       22
9       30
10      38
```

## Fortran

`module topimplicit nonecontains recursive function f(x) result(m)  integer :: n, m, x(:),y(size(x)), fst  fst = x(1)  if (fst == 1) then    m = 0  else    y(1:fst) = x(fst:1:-1)    y(fst+1:) = x(fst+1:)    m = 1 + f(y)  end ifend function recursive function perms(x) result(p)integer, pointer     :: p(:,:), q(:,:)integer              :: x(:), n, k, in = size(x)if (n == 1) then  allocate(p(1,1))  p(1,:) = xelse  q => perms(x(2:n))  k = ubound(q,1)  allocate(p(k*n,n))  p = 0  do i = 1,n    p(1+k*(i-1):k*i,1:i-1) = q(:,1:i-1)    p(1+k*(i-1):k*i,i) = x(1)    p(1+k*(i-1):k*i,i+1:) = q(:,i:)  end doend ifend functionend module program topswortuse topimplicit noneinteger :: x(10)integer, pointer  :: p(:,:)integer :: i, j, m forall(i=1:10)  x(i) = iend forall do i = 1,10  p=>perms(x(1:i))  m = 0  do j = 1, ubound(p,1)    m = max(m, f(p(j,:)))  end do  print "(i3,a,i3)", i,": ",mend do  end program `

## 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}`
Output:
```1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38
```

#### Searching permutations

`import Data.List (permutations) topswops :: Int -> Inttopswops n = maximum \$ map tops \$ permutations [1 .. n]    where        tops    (1 : _) = 0        tops xa@(x : _) = 1 + tops reordered            where                reordered = reverse (take x xa) ++ drop x xa main = mapM_        (\x -> putStrLn \$ show x ++ ":\t" ++ show (topswops x))        [1 .. 10]`
Output:
```1:	0
2:	1
3:	2
4:	4
5:	7
6:	10
7:	16
8:	22
9:	30
10:	38```

#### Searching derangements

Alternate version
Uses only permutations with all elements out of place.

`import Data.List (permutations, inits) import Control.Arrow (first) derangements :: [Int] -> [[Int]]derangements = (filter . (and .) . zipWith (/=)) <*> permutations topswop :: Int -> [a] -> [a]topswop = ((uncurry (++) . first reverse) .) . splitAt topswopIter :: [Int] -> [[Int]]topswopIter = takeWhile ((/= 1) . head) . iterate (topswop =<< head) swops :: [Int] -> [Int]swops = fmap (length . topswopIter) . derangements topSwops :: [Int] -> [(Int, Int)]topSwops = zip [1 ..] . fmap (maximum . (0 :) . swops) . tail . inits main :: IO ()main = mapM_ print \$ take 10 \$ topSwops [1 ..]`

Output

```*Main> mapM_ print \$ take 10 \$ topSwops [1..]
(1,0)
(2,1)
(3,2)
(4,4)
(5,7)
(6,10)
(7,16)
(8,22)
(9,30)
(10,38)```

## Icon and Unicon

This doesn't compile in Icon only because of the use of list comprehension to build the original list of 1..n values.

`procedure main()    every n := 1 to 10 do {        ts := 0        every (ts := 0) <:= swop(permute([: 1 to n :]))        write(right(n, 3),": ",right(ts,4))        }end procedure swop(A)    count := 0    while A[1] ~= 1 do {        A := reverse(A[1+:A[1]]) ||| A[(A[1]+1):0]        count +:= 1        }    return countend procedure permute(A)    if *A <= 1 then return A    suspend [(A[1]<->A[i := 1 to *A])] ||| permute(A[2:0])end`

Sample run:

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

## J

Solution:
`   swops =:  ((|[email protected]:{. , }.)~ {.)^:a:`
`   swops 2 4 1 32 4 1 34 2 1 33 1 2 42 1 3 41 2 3 4`
Example (topswops of all permutations of the integers 1..10):
`   (,. _1 + ! >./@:(#@[email protected] >:)&i. ])&> 1+i.10 1  0 2  1 3  2 4  4 5  7 6 10 7 16 8 22 9 3010 38`

Notes: Readers less familiar with array-oriented programming may find an alternate solution written in the structured programming style more accessible.

## Java

Translation of: D
`public class Topswops {    static final int maxBest = 32;    static int[] best;     static private void trySwaps(int[] deck, int f, int d, int n) {        if (d > best[n])            best[n] = d;         for (int i = n - 1; i >= 0; i--) {            if (deck[i] == -1 || deck[i] == i)                break;            if (d + best[i] <= best[n])                return;        }         int[] deck2 = deck.clone();        for (int i = 1; i < n; i++) {            final int k = 1 << i;            if (deck2[i] == -1) {                if ((f & k) != 0)                    continue;            } else if (deck2[i] != i)                continue;             deck2[0] = i;            for (int j = i - 1; j >= 0; j--)                deck2[i - j] = deck[j]; // Reverse copy.            trySwaps(deck2, f | k, d + 1, n);        }    }     static int topswops(int n) {        assert(n > 0 && n < maxBest);        best[n] = 0;        int[] deck0 = new int[n + 1];        for (int i = 1; i < n; i++)            deck0[i] = -1;        trySwaps(deck0, 1, 0, n);        return best[n];    }     public static void main(String[] args) {        best = new int[maxBest];        for (int i = 1; i < 11; i++)            System.out.println(i + ": " + topswops(i));    }}`
Output:
```1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38```

## jq

The following uses permutations and is therefore impractical for n>10 or so.

Infrastructure:

`# "while" as defined here is included in recent versions (>1.4) of jq:def until(cond; next):  def _until:    if cond then . else (next|_until) end;  _until; # Generate a stream of permutations of [1, ... n].# This implementation uses arity-0 filters for speed.def permutations:  # Given a single array, insert generates a stream by inserting (length+1) at different positions  def insert: # state: [m, array]     .[0] as \$m | (1+(.[1]|length)) as \$n     | .[1]     | if \$m >= 0 then (.[0:\$m] + [\$n] + .[\$m:]), ([\$m-1, .] | insert) else empty end;   if .==0 then []  elif . == 1 then [1]  else    . as \$n | (\$n-1) | permutations | [\$n-1, .] | insert  end;`

Topswops:

`# Input: a permutation; output: an integerdef flips:  # state: [i, array]  [0, .]  | until( .[1][0] == 1;           .[1] as \$p | \$p[0] as \$p0	   | [.[0] + 1,  (\$p[:\$p0] | reverse) + \$p[\$p0:] ] )  | .[0]; # input: n, the number of itemsdef fannkuch:  reduce permutations as \$p    (0; [., (\$p|flips) ] | max);`

Example:

`range(1; 11) | [., fannkuch ]`
Output:
`\$ jq -n -c -f topswops.jq[1,0][2,1][3,2][4,4][5,7][6,10][7,16][8,22][9,30][10,38]`

## Julia

Fast, efficient version

`function fannkuch(n)	n == 1 && return 0	n == 2 && return 1	p = [1:n]	q = copy(p)	s = copy(p)	sign = 1; maxflips = sum = 0	while true		q0 = p[1]		if q0 != 1			for i = 2:n				q[i] = p[i]			end			flips = 1			while true				qq = q[q0] #??				if qq == 1					sum += sign*flips					flips > maxflips && (maxflips = flips)					break				end				q[q0] = q0				if q0 >= 4					i = 2; j = q0-1					while true						t = q[i]						q[i] = q[j]						q[j] = t						i += 1						j -= 1						i >= j && break					end				end				q0 = qq				flips += 1			end		end		#permute		if sign == 1			t = p[2]			p[2] = p[1]			p[1] = t			sign = -1		else			t = p[2]			p[2] = p[3]			p[3] = t			sign = 1			for i = 3:n				sx = s[i]				if sx != 1					s[i] = sx-1					break				end				i == n && return maxflips				s[i] = i				t = p[1]				for j = 1:i					p[j] = p[j+1]				end				p[i+1] = t			end		end	endend`
Output:
```julia> function main()
for i = 1:10
println(fannkuch(i))
end
end
# methods for generic function main
main() at none:2

julia> @time main()
0
1
2
4
7
10
16
22
30
38
elapsed time: 0.299617582 seconds```

## Kotlin

Translation of: Java
`// version 1.1.2 val best = IntArray(32) fun trySwaps(deck: IntArray, f: Int, d: Int, n: Int) {    if (d > best[n]) best[n] = d    for (i in n - 1 downTo 0) {        if (deck[i] == -1 || deck[i] == i) break        if (d + best[i] <= best[n]) return    }    val deck2 = deck.copyOf()    for (i in 1 until n) {        val k = 1 shl i        if (deck2[i] == -1) {            if ((f and k) != 0) continue        }        else if (deck2[i] != i) continue        deck2[0] = i        for (j in i - 1 downTo 0) deck2[i - j] = deck[j]          trySwaps(deck2, f or k, d + 1, n)    }} fun topswops(n: Int): Int {    require(n > 0 && n < best.size)    best[n] = 0    val deck0 = IntArray(n + 1)    for (i in 1 until n) deck0[i] = -1    trySwaps(deck0, 1, 0, n)    return best[n]} fun main(args: Array<String>) {    for (i in 1..10) println("\${"%2d".format(i)} : \${topswops(i)}")}`
Output:
``` 1 : 0
2 : 1
3 : 2
4 : 4
5 : 7
6 : 10
7 : 16
8 : 22
9 : 30
10 : 38
```

## Lua

`-- Return an iterator to produce every permutation of listfunction permute (list)    local function perm (list, n)        if n == 0 then coroutine.yield(list) end        for i = 1, n do            list[i], list[n] = list[n], list[i]            perm(list, n - 1)            list[i], list[n] = list[n], list[i]        end    end    return coroutine.wrap(function() perm(list, #list) end)end -- Perform one topswop round on table tfunction swap (t)    local new, limit = {}, t[1]    for i = 1, #t do        if i <= limit then            new[i] = t[limit - i + 1]        else            new[i] = t[i]        end    end    return newend -- Find the most swaps needed for any starting permutation of n cardsfunction topswops (n)    local numTab, highest, count = {}, 0    for i = 1, n do numTab[i] = i end    for numList in permute(numTab) do        count = 0        while numList[1] ~= 1 do            numList = swap(numList)            count = count + 1        end        if count > highest then highest = count end    end    return highestend -- Main procedurefor i = 1, 10 do print(i, topswops(i)) end`
Output:
```1       0
2       1
3       2
4       4
5       7
6       10
7       16
8       22
9       30
10      38```

## Mathematica

An exhaustive search of all possible permutations is done

`flip[a_] := Block[{a1 = [email protected]},  If[a1 == [email protected], Reverse[a],    Join[Reverse[a[[;; a1]]], a[[a1 + 1 ;;]]]]] swaps[a_] := [email protected][flip, a] - 2 Print[#, ": ", Max[swaps /@ Permutations[[email protected]#]]] & /@ Range[10];`
Output:
```1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38```

## PARI/GP

Naive solution:

`flip(v:vec)={  my(t=v[1]+1);  if (t==2, return(0));  for(i=1,t\2, [v[t-i],v[i]]=[v[i],v[t-i]]);  1+flip(v)}topswops(n)={  my(mx);  for(i=0,n!-1,    mx=max(flip(Vecsmall(numtoperm(n,i))),mx)  );  mx;}vector(10,n,topswops(n))`
Output:
`%1 = [0, 1, 2, 4, 7, 10, 16, 22, 30, 38]`

An efficient solution would use PARI, following the C solution.

## Perl

Recursive backtracking solution, starting with the final state and going backwards.

` sub next_swop {  my( \$max, \$level, \$p, \$d ) = @_;  my \$swopped = 0;  for( 2..@\$p ){ # find possibilities    my @now = @\$p;    if( \$_ == \$now[\$_-1] ) {      splice @now, 0, 0, reverse splice @now, 0, \$_;      \$swopped = 1;      next_swop( \$max, \$level+1, \@now, [ @\$d ] );    }  }  for( 1..@\$d ) { # create possibilities    my @now = @\$p;    my \$next = shift @\$d;    if( not \$now[\$next-1] ) {      \$now[\$next-1] = \$next;      splice @now, 0, 0, reverse splice @now, 0, \$next;      \$swopped = 1;      next_swop( \$max, \$level+1, \@now, [ @\$d ] );    }    push @\$d, \$next;  }  \$\$max = \$level if !\$swopped and \$level > \$\$max;} sub topswops {  my \$n = shift;  my @d = 2..\$n;  my @p = ( 1, (0) x (\$n-1) );  my \$max = 0;  next_swop( \\$max, 0, \@p, \@d );  return \$max;} printf "Maximum swops for %2d cards: %2d\n", \$_, topswops \$_ for 1..10; `
Output:
```Maximum swops for  1 cards:  0
Maximum swops for  2 cards:  1
Maximum swops for  3 cards:  2
Maximum swops for  4 cards:  4
Maximum swops for  5 cards:  7
Maximum swops for  6 cards: 10
Maximum swops for  7 cards: 16
Maximum swops for  8 cards: 22
Maximum swops for  9 cards: 30
Maximum swops for 10 cards: 38
```

## Perl 6

`sub swops(@a is copy) {    my int \$count = 0;    until @a[0] == 1 {        @a[ ^@a[0] ] .= reverse;        ++\$count;    }    \$count} sub topswops(\$n) { max (1..\$n).permutations.race(:8degree).map: *.&swops } say "\$_ {topswops \$_}" for 1 .. 10;`
Output:
```1 0
2 1
3 2
4 4
5 7
6 10
7 16
8 22
9 30
10 38```

## Phix

Originally contributed by Jason Gade as part of the Euphoria version of the Great Computer Language Shootout benchmarks.

`function fannkuch(integer n)sequence start = tagset(n),         perm,         perm1 = start,         count = startinteger maxFlipsCount = 0, r = n+1integer perm0, flipsCount, k, k2, j, j2     while 1 do        while r!=1 do count[r-1] = r r -= 1 end while        if not (perm1[1]=1 or perm1[n]=n) then            perm = perm1            flipsCount = 0            k = perm[1]            while k!=1 do                k2 = floor((k+1)/2)                perm = reverse(perm[1..k]) & perm[k+1..n]                flipsCount += 1                k = perm[1]            end while            if flipsCount>maxFlipsCount then                maxFlipsCount = flipsCount            end if        end if        -- Use incremental change to generate another permutation        while 1 do            if r>n then return maxFlipsCount end if            perm0 = perm1[1]            j2 = 1            while j2<r do                j = j2+1                perm1[j2] = perm1[j]                j2 = j            end while            perm1[r] = perm0            count[r] = count[r]-1            if count[r]>1 then exit else r += 1 end if        end while    end whileend function -- fannkuch for i=1 to 10 do    ? fannkuch(i)end for`
Output:
```0
1
2
4
7
10
16
22
30
38
```

## PicoLisp

`(de fannkuch (N)   (let (Lst (range 1 N)  L Lst  Max)      (recur (L)  # Permute         (if (cdr L)            (do (length L)               (recurse (cdr L))               (rot L) )            (zero N)  # For each permutation            (for (P (copy Lst)  (> (car P) 1)  (flip P (car P)))               (inc 'N) )            (setq Max (max N Max)) ) )      Max ) ) (for I 10   (println I (fannkuch I)) )`

Output:

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

## PL/I

 This example is incorrect. Please fix the code and remove this message.Details: Shown output is incorrect at the very least.
` (subscriptrange):topswap: procedure options (main); /* 12 November 2013 */   declare cards(*) fixed (2) controlled, t fixed (2);   declare dealt(*) bit(1) controlled;   declare (count, i, m, n, c1, c2) fixed binary;   declare random builtin;    do n = 1 to 10;      allocate cards(n), dealt(n);      /* Take the n cards, in order ... */      do i = 1 to n; cards(i) = i; end;      /* ... and shuffle them. */      do i = 1 to n;         c1 = random*n+1; c2 = random*n+1;         t = cards(c1); cards(c1) = cards(c2); cards(c2) = t;      end;      /* If '1' is the first card, game is trivial; swap it with another. */      if cards(1) = 1 & n > 1 then         do; t = cards(1); cards(1) = cards(2); cards(2) = t; end;       count = 0;      do until (cards(1) = 1);         /* take the value of the first card, M, and reverse the first M cards. */         m = cards(1);         do i = 1 to m/2;            t = cards(i); cards(i) = cards(m-i+1); cards(m-i+1) = t;         end;         count = count + 1;      end;      put skip edit (n, ':', count) (f(2), a, f(4));   end;end topswap; `
``` 1:   1
2:   1
3:   2
4:   2
5:   4
6:   2
7:   1
8:   9
9:  16
10:   1
```

## Potion

`range = (a, b):  i = 0, l = list(b-a+1)  while (a + i <= b):    l (i) = a + i++.  l. fannkuch = (n):  flips = 0, maxf = 0, k = 0, m = n - 1, r = n  perml = range(0, n), count = list(n), perm = list(n)   loop:    while (r != 1):      count (r-1) = r      r--.     if (perml (0) != 0 and perml (m) != m):      flips = 0, i = 1      while (i < n):        perm (i) = perml (i)        i++.      k = perml (0)      loop:        i = 1, j = k - 1        while (i < j):          t = perm (i), perm (i) = perm (j), perm (j) = t          i++, j--.        flips++        j = perm (k), perm (k) = k, k = j        if (k == 0): break.      .      if (flips > maxf): maxf = flips.    .     loop:      if (r == n):        (n, maxf) say        return (maxf).       i = 0, j = perml (0)      while (i < r):        k = i + 1        perml (i) = perml (k)        i = k.      perml (r) = j       j = count (r) - 1      count (r) = j      if (j > 0): break.      r++_ n n = argv(1) numberif (n<1): n=10.fannkuch(n) `

Output follows that of Perl6 and Python, ~2.5x faster than perl5

## Python

This solution uses cards numbered from 0..n-1 and variable p0 is introduced as a speed optimisation

`>>> from itertools import permutations>>> def f1(p):	i = 0	while True:		p0  = p[0]		if p0 == 1: break		p[:p0] = p[:p0][::-1]		i  += 1	return i >>> def fannkuch(n):	return max(f1(list(p)) for p in permutations(range(1, n+1))) >>> for n in range(1, 11): print(n,fannkuch(n)) 1 02 13 24 45 76 107 168 229 3010 38>>> `

### Python: Faster Version

Translation of: C
`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[:i2 + 1] = reversed(deck[: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))`
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```

## R

Using iterpc package for optimization

` topswops <- function(x){   i <- 0  while(x[1] != 1){    first <- x[1]    if(first == length(x)){      x <- rev(x)    } else{      x <- c(x[first:1], x[(first+1):length(x)])    }    i <- i + 1  }  return(i)} library(iterpc) result <- NULL for(i in 1:10){  I <- iterpc(i, labels = 1:i, ordered = T)  A <- getall(I)  A <- data.frame(A)  A\$flips <- apply(A, 1, topswops)  result <- rbind(result, c(i, max(A\$flips)))} `

Output:

```      [,1] [,2]
[1,]    1    0
[2,]    2    1
[3,]    3    2
[4,]    4    4
[5,]    5    7
[6,]    6   10
[7,]    7   16
[8,]    8   22
[9,]    9   30
[10,]   10   38
```

## Racket

Simple search, only "optimization" is to consider only all-misplaced permutations (as in the alternative Haskell solution), which shaves off around 2 seconds (from ~5).

` #lang racket (define (all-misplaced? l)  (for/and ([x (in-list l)] [n (in-naturals 1)]) (not (= x n)))) (define (topswops n)  (for/fold ([m 0]) ([p (in-permutations (range 1 (add1 n)))]                     #:when (all-misplaced? p))    (let loop ([p p] [n 0])      (if (= 1 (car p))        (max n m)        (loop (let loop ([l '()] [r p] [n (car p)])                (if (zero? n) (append l r)                    (loop (cons (car r) l) (cdr r) (sub1 n))))              (add1 n)))))) (for ([i (in-range 1 11)]) (printf "~a\t~a\n" i (topswops i))) `

Output:

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

## REXX

The   decks   function is a modified permSets (permutation sets) subroutine,
and is optimized somewhat to take advantage by eliminating one-swop "decks".

`/*REXX program generates  N  decks of  numbered cards  and  finds the maximum  "swops". */parse arg things .;          if things=='' then things=10       do n=1  for things;          #=decks(n, n) /*create a (things) number of "decks". */      mx= (n\==1)                                /*handle the case of a  one-card  deck.*/                  do i=1  for #;   p=swops(!.i)  /*compute the SWOPS for this iteration.*/                  if p>mx  then mx=p             /*This a new maximum?   Use a new max. */                  end   /*i*/      say '──────── maximum swops for a deck of'   right(n,2)   ' cards is'    right(mx,4)      end   /*n*/exit                                             /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/decks:  procedure expose !.; parse arg x,y,,\$ @. /*   X  things  taken   Y   at a time. */        #=0;                 call .decks 1       /* [↑]  initialize  \$  &   @.  to null.*/        return #                                 /*return number of permutations (decks)*/.decks: procedure expose !. @. x y \$ #;          parse arg ?        if ?>y  then do;  [email protected].1;  do j=2  for y-1;  _=_ @.j;  end  /*j*/;    #=#+1;  !.#=_                     end                else do;           qm=? - 1                     if ?==1  then qs=2          /*don't use 1-swops that start with  1 */                              else if @.1==?  then qs=2  /*skip the 1-swops: 3 x 1 x ···*/                                              else qs=1                       do q=qs  to x             /*build the permutations recursively.  */                             do k=1  for qm;  if @.k==q  then iterate q                             end  /*k*/                       @.?=q;                 call .decks ? + 1                       end        /*q*/                     end        return/*──────────────────────────────────────────────────────────────────────────────────────*/ swops:  parse arg z;   do u=1;    parse var z t .;     if \datatype(t, 'W')  then t=x2d(t)                       if word(z, t)==1  then return u            /*found unity at  T. */                               do h=10  to things;     if pos(h, z)==0  then iterate                               z=changestr(h, z, d2x(h) )         /* [↑]  any H's in Z?*/                               end   /*h*/                       z=reverse( subword(z, 1, t) )      subword(z, t + 1)                       end   /*u*/`

Some older REXXes don't have a changestr bif, so one is included here   ───►   CHANGESTR.REX.

output   when using the default input:
```──────── maximum swops for a deck of  1  cards is    0
──────── maximum swops for a deck of  2  cards is    1
──────── maximum swops for a deck of  3  cards is    2
──────── maximum swops for a deck of  4  cards is    4
──────── maximum swops for a deck of  5  cards is    7
──────── maximum swops for a deck of  6  cards is   10
──────── maximum swops for a deck of  7  cards is   16
──────── maximum swops for a deck of  8  cards is   22
──────── maximum swops for a deck of  9  cards is   30
──────── maximum swops for a deck of 10  cards is   38
```

## Ruby

Translation of: Python
`def f1(a)  i = 0  while (a0 = a[0]) > 1    a[0...a0] = a[0...a0].reverse    i += 1  end  iend def fannkuch(n)  [*1..n].permutation.map{|a| f1(a)}.maxend for n in 1..10  puts "%2d : %d" % [n, fannkuch(n)]end`
Output:
``` 1 : 0
2 : 1
3 : 2
4 : 4
5 : 7
6 : 10
7 : 16
8 : 22
9 : 30
10 : 38
```

Faster Version

Translation of: Java
`def try_swaps(deck, f, d, n)  @best[n] = d  if d > @best[n]  (n-1).downto(0) do |i|    break  if deck[i] == -1 || deck[i] == i    return if d + @best[i] <= @best[n]  end  deck2 = deck.dup  for i in 1...n    k = 1 << i    if deck2[i] == -1      next  if f & k != 0    elsif deck2[i] != i      next    end    deck2[0] = i    deck2[1..i] = deck[0...i].reverse    try_swaps(deck2, f | k, d+1, n)  endend def topswops(n)  @best[n] = 0  deck0 = [-1] * (n + 1)  try_swaps(deck0, 1, 0, n)  @best[n]end @best = [0] * 16for i in 1..10  puts "%2d : %d" % [i, topswops(i)]end`

## Scala

Library: Scala
`object Fannkuch extends App {   def fannkuchen(l: List[Int], n: Int, i: Int, acc: Int): Int = {    def flips(l: List[Int]): Int = (l: @unchecked) match {      case 1 :: ls => 0      case (n :: ls) =>        val splitted = l.splitAt(n)        flips(splitted._2.reverse_:::(splitted._1)) + 1    }     def rotateLeft(l: List[Int]) =      l match {        case Nil => List()        case x :: xs => xs ::: List(x)      }     if (i >= n) acc    else {      if (n == 1) acc.max(flips(l))      else {        val split = l.splitAt(n)        fannkuchen(rotateLeft(split._1) ::: split._2, n, i + 1, fannkuchen(l, n - 1, 0, acc))      }    }  } // def fannkuchen(   val result = (1 to 10).map(i => (i, fannkuchen(List.range(1, i + 1), i, 0, 0)))  println("Computing results...")  result.foreach(x => println(s"Pfannkuchen(\${x._1})\t= \${x._2}"))  assert(result == Vector((1, 0), (2, 1), (3, 2), (4, 4), (5, 7), (6, 10), (7, 16), (8, 22), (9, 30), (10, 38)), "Bad results")  println(s"Successfully completed without errors. [total \${scala.compat.Platform.currentTime - executionStart} ms]")}`
Output:
```Computing results...
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
Successfully completed without errors. [total 7401 ms]

Process finished with exit code 0
```

## Tcl

Library: Tcllib (Package: struct::list)
Probably an integer overflow at n=10.
`package require struct::list proc swap {listVar} {    upvar 1 \$listVar list    set n [lindex \$list 0]    for {set i 0; set j [expr {\$n-1}]} {\$i<\$j} {incr i;incr j -1} {	set tmp [lindex \$list \$i]	lset list \$i [lindex \$list \$j]	lset list \$j \$tmp    }} proc swaps {list} {    for {set i 0} {[lindex \$list 0] > 1} {incr i} {	swap list    }    return \$i} proc topswops list {    set n 0    ::struct::list foreachperm p \$list {	set n [expr {max(\$n,[swaps \$p])}]    }    return \$n} proc topswopsTo n {    puts "n\ttopswops(n)"    for {set i 1} {\$i <= \$n} {incr i} {	puts \$i\t[topswops [lappend list \$i]]    }}topswopsTo 10`
Output:
```n	topswops(n)
1	0
2	1
3	2
4	4
5	7
6	10
7	16
8	22
9	30
10	38
```

## XPL0

`code ChOut=8, CrLf=9, IntOut=11;int  N, Max, Card1(16), Card2(16); proc Topswop(D);        \Conway's card swopping gameint  D;                 \depth of recursionint  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);    ];]`
Output:
```1 0
2 1
3 2
4 4
5 7
6 10
7 16
8 22
9 30
10 38
```

### XPL0: Faster Version

Translation of: C
`code CrLf=9, IntOut=11, Text=12;int  N, D, Best(16); proc TrySwaps(A, F, S);int  A, F, S;int  B(16), I, J, K;[if D > Best(N) then Best(N):= D;loop    [if A(S)=-1 ! A(S)=S then quit;        if D+Best(S) <= Best(N) then return;        if S = 0 then quit;        S:= S-1;        ];D:= D+1;for I:= 0 to S do B(I):= A(I);K:= 1;for I:= 1 to S do        [K:= K<<1;        if B(I)=-1 & (F&K)=0 ! B(I)=I then                [J:= I;  B(0):= J;                while J do [J:= J-1;  B(I-J):= A(J)];                TrySwaps(B, F!K, S);                ];        ];D:= D-1;]; int  I, X(16);[for I:= 0 to 16-1 do        [X(I):= -1;  Best(I):= 0];X(0):= 0;for N:= 1 to 13 do        [D:= 0;        TrySwaps(X, 1, N-1);        IntOut(0, N);  Text(0, ": ");  IntOut(0, Best(N));  CrLf(0);        ];]`
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
13: 80
```

## zkl

Translation of: D

Slow version

`fcn topswops(n){   flip:=fcn(xa){      if (not xa[0]) return(0);      xa.reverse(0,xa[0]+1);  // inplace, ~4x faster than making new lists      return(1 + self.fcn(xa));   };   (0).pump(n,List):Utils.Helpers.permute(_).pump(List,"copy",flip).reduce("max");} foreach n in ([1 .. 10]){ println(n, ": ", topswops(n)) }`
Output:
```1: 0
2: 1
3: 2
4: 4
5: 7
6: 10
7: 16
8: 22
9: 30
10: 38
```