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:

use itertools::Itertools;

fn solve(deck: &[usize]) -> usize {
    let mut counter = 0_usize;
    let mut shuffle = deck.to_vec();
    loop {
        let p0 = shuffle[0];
        if p0 == 1 {
            break;
        }
        shuffle[..p0].reverse();
        counter += 1;
    }

    counter
}

// this is a naive method which tries all permutations and works up to ~12 cards
fn topswops(number: usize) -> usize {
    (1..=number)
        .permutations(number)
        .fold(0_usize, |mut acc, p| {
            let steps = solve(&p);
            if steps > acc {
                acc = steps;
            }
            acc
        })
}
fn main() {
    (1_usize..=10).for_each(|x| println!("{}: {}", x, topswops(x)));
}