Problem Statement

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

Topswops   is also known as   Fannkuch   from the German word   Pfannkuchen   meaning   pancake.

Let's start with the solution:

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