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


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
	end
end