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


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]")
}