I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Pancake numbers

Pancake numbers
You are encouraged to solve this task according to the task description, using any language you may know.

Adrian Monk has problems and an assistant, Sharona Fleming. Sharona can deal with most of Adrian's problems except his lack of punctuality paying her remuneration. 2 pay checks down and she prepares him pancakes for breakfast. Knowing that he will be unable to eat them unless they are stacked in ascending order of size she leaves him only a skillet which he can insert at any point in the pile and flip all the above pancakes, repeating until the pile is sorted. Sharona has left the pile of n pancakes such that the maximum number of flips is required. Adrian is determined to do this in as few flips as possible. This sequence n->p(n) is known as the Pancake numbers.

The task is to determine p(n) for n = 1 to 9, and for each show an example requiring p(n) flips.

Sorting_algorithms/Pancake_sort actually performs the sort some giving the number of flips used. How do these compare with p(n)?

Few people know p(20), generously I shall award an extra credit for anyone doing more than p(16).

References

## AWK

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
` # syntax: GAWK -f PANCAKE_NUMBERS.AWK# converted from CBEGIN {    for (i=0; i<4; i++) {      for (j=1; j<6; j++) {        n = i * 5 + j        printf("p(%2d) = %2d  ",n,main(n))      }      printf("\n")    }    exit(0)}function main(n,  adj,gap,sum) {    gap = 2    sum = 2    adj = -1    while (sum < n) {      adj++      gap = gap * 2 - 1      sum += gap    }    return(n + adj)} `
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23
```

## C

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: Go
`#include <stdio.h> int pancake(int n) {    int gap = 2, sum = 2, adj = -1;    while (sum < n) {        adj++;        gap = gap * 2 - 1;        sum += gap;    }    return n + adj;} int main() {    int i, j;    for (i = 0; i < 4; i++) {        for (j = 1; j < 6; j++) {            int n = i * 5 + j;            printf("p(%2d) = %2d  ", n, pancake(n));        }        printf("\n");    }    return 0;}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23```

## C++

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
`#include <iomanip>#include <iostream> int pancake(int n) {    int gap = 2, sum = 2, adj = -1;    while (sum < n) {        adj++;        gap = gap * 2 - 1;        sum += gap;    }    return n + adj;} int main() {    for (int i = 0; i < 4; i++) {        for (int j = 1; j < 6; j++) {            int n = i * 5 + j;            std::cout << "p(" << std::setw(2) << n << ") = " << std::setw(2) << pancake(n) << "  ";        }        std::cout << '\n';    }    return 0;}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23```

## Cowgol

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
`include "cowgol.coh"; sub pancake(n: uint8): (r: uint8) is    var gap: uint8 := 2;    var sum: uint8 := 2;    var adj: int8 := -1;     while sum < n loop        adj := adj + 1;        gap := gap * 2 - 1;        sum := sum + gap;    end loop;     r := n + adj as uint8;end sub; # print 2-digit numbersub print2(n: uint8) is    if n<10 then        print_char(' ');    else        print_char(n/10 + '0');    end if;    print_char(n%10 + '0');end sub; # print itemsub print_item(n: uint8) is    print("p(");    print2(n);    print(") = ");    print2(pancake(n));    print("  ");end sub; var i: uint8 := 0;while i < 4 loop    var j: uint8 := 1;    while j < 6 loop        print_item(i*5 + j);        j := j + 1;    end loop;    print_nl();    i := i + 1;end loop;`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23```

## D

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
`import std.stdio; int pancake(int n) {    int gap = 2, sum = 2, adj = -1;    while (sum < n) {        adj++;        gap = 2 * gap - 1;        sum += gap;    }    return n + adj;} void main() {    foreach (i; 0..4) {        foreach (j; 1..6) {            int n = 5 * i + j;            writef("p(%2d) = %2d  ", n, pancake(n));        }        writeln;    }}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23```

## F#

` // Pancake numbers. Nigel Galloway: October 28th., 2020let pKake z=let n=[for n in 1..z-1->Array.ofList([n.. -1..0]@[n+1..z-1])]            let e=let rec fG n g=match g with 0->n |_->fG (n*g) (g-1) in fG 1 z            let rec fN i g l=match (Set.count g)-e with 0->(i,List.last l)                                                       |_->let l=l|>List.collect(fun g->[for n in n->List.permute(fun g->n.[g]) g])|>Set.ofList                                                           fN (i+1) (Set.union g l) (Set.difference l g|>Set.toList)            fN 0 (set[[1..z]]) [[1..z]] [1..9]|>List.iter(fun n->let i,g=pKake n in printfn "Maximum number of flips to sort %d elements is %d. e.g %A->%A" n i g [1..n]) `
Output:
```Maximum number of flips to sort 1 elements is 0. e.g ->
Maximum number of flips to sort 2 elements is 1. e.g [2; 1]->[1; 2]
Maximum number of flips to sort 3 elements is 3. e.g [1; 3; 2]->[1; 2; 3]
Maximum number of flips to sort 4 elements is 4. e.g [4; 2; 3; 1]->[1; 2; 3; 4]
Maximum number of flips to sort 5 elements is 5. e.g [5; 3; 1; 4; 2]->[1; 2; 3; 4; 5]
Maximum number of flips to sort 6 elements is 7. e.g [5; 3; 6; 1; 4; 2]->[1; 2; 3; 4; 5; 6]
Maximum number of flips to sort 7 elements is 8. e.g [7; 3; 1; 5; 2; 6; 4]->[1; 2; 3; 4; 5; 6; 7]
Maximum number of flips to sort 8 elements is 9. e.g [8; 6; 2; 4; 7; 3; 5; 1]->[1; 2; 3; 4; 5; 6; 7; 8]
Maximum number of flips to sort 9 elements is 10. e.g [9; 7; 5; 2; 8; 1; 4; 6; 3]->[1; 2; 3; 4; 5; 6; 7; 8; 9]
```

## FreeBASIC

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.

### Maximum number of flips only

Translation of: C
` Function pancake(n As Integer) As Integer    Dim As Integer gap = 2, sum = 2, adj = -1    While (sum < n)        adj += 1        gap = gap * 2 - 1        sum += gap    Wend    Return n + adjEnd Function For n As Integer = 1 To 20    Print Using "p(##) = ##  "; n; pancake(n);     If n Mod 5 = 0 Then ?Next nSleep `
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 2
```

## Go

### Maximum number of flips only

Translation of: Phix
`package main import "fmt" func pancake(n int) int {    gap, sum, adj := 2, 2, -1    for sum < n {        adj++        gap = gap*2 - 1        sum += gap    }    return n + adj} func main() {    for i := 0; i < 4; i++ {        for j := 1; j < 6; j++ {            n := i*5 + j            fmt.Printf("p(%2d) = %2d  ", n, pancake(n))        }        fmt.Println()    }}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23
```

### Maximum number of flips plus examples using exhaustive search

Translation of: Wren

And hence indirectly of Julia. Go has the same problem as Wren in not supporting slices as map keys and therefore having to convert them to/from strings.

Map order iteration is also undefined in Go even between individual runnings.

Not particularly fast - Julia is about 3 seconds faster on the same machine.

`package main import (    "fmt"    "strconv"    "strings"    "time") type assoc map[string]int // Converts a string of the form "[1 2]" into a slice of ints: {1, 2}func asSlice(s string) []int {    split := strings.Split(s[1:len(s)-1], " ")    le := len(split)    res := make([]int, le)    for i := 0; i < le; i++ {        res[i], _ = strconv.Atoi(split[i])    }    return res} // Merges two assocs into one. If the same key is present in both assocs// its value will be the one in the second assoc.func merge(m1, m2 assoc) assoc {    m3 := make(assoc)    for k, v := range m1 {        m3[k] = v    }    for k, v := range m2 {        m3[k] = v    }    return m3} // Finds the maximum value in 'dict' and returns the first key// it finds (iteration order is undefined) with that value.func findMax(dict assoc) string {    max := -1    maxKey := ""    for k, v := range dict {        if v > max {            max = v            maxKey = k        }    }    return maxKey} // Creates a new slice of ints by reversing an existing one.func reverse(s []int) []int {    le := len(s)    rev := make([]int, le)    for i := 0; i < le; i++ {        rev[i] = s[le-1-i]    }    return rev} func pancake(n int) (string, int) {    numStacks := 1    gs := make([]int, n)    for i := 0; i < n; i++ {        gs[i] = i + 1    }    goalStack := fmt.Sprintf("%v", gs)    stacks := assoc{goalStack: 0}    newStacks := assoc{goalStack: 0}    for i := 1; i <= 1000; i++ {        nextStacks := assoc{}        for key := range newStacks {            arr := asSlice(key)            for pos := 2; pos <= n; pos++ {                t := append(reverse(arr[0:pos]), arr[pos:len(arr)]...)                newStack := fmt.Sprintf("%v", t)                if _, ok := stacks[newStack]; !ok {                    nextStacks[newStack] = i                }            }        }        newStacks = nextStacks        stacks = merge(stacks, newStacks)        perms := len(stacks)        if perms == numStacks {            return findMax(stacks), i - 1        }        numStacks = perms    }    return "", 0} func main() {    start := time.Now()    fmt.Println("The maximum number of flips to sort a given number of elements is:")    for i := 1; i <= 10; i++ {        example, steps := pancake(i)        fmt.Printf("pancake(%2d) = %-2d  example: %s\n", i, steps, example)    }    fmt.Printf("\nTook %s\n", time.Since(start))}`
Output:
```The maximum number of flips to sort a given number of elements is:
pancake( 1) = 0   example: 
pancake( 2) = 1   example: [2 1]
pancake( 3) = 3   example: [1 3 2]
pancake( 4) = 4   example: [3 1 4 2]
pancake( 5) = 5   example: [4 2 5 1 3]
pancake( 6) = 7   example: [5 3 6 1 4 2]
pancake( 7) = 8   example: [1 5 7 3 6 4 2]
pancake( 8) = 9   example: [3 7 1 5 8 2 6 4]
pancake( 9) = 10  example: [7 2 9 5 1 8 3 6 4]
pancake(10) = 11  example: [7 5 9 4 10 1 8 2 6 3]

Took 57.512153273s
```

## Java

### Fast approximation

Translation of: Go – Original algorithm from Phix
`public class Pancake {    private static int pancake(int n) {        int gap = 2;        int sum = 2;        int adj = -1;        while (sum < n) {            adj++;            gap = 2 * gap - 1;            sum += gap;        }        return n + adj;    }     public static void main(String[] args) {        for (int i = 0; i < 4; i++) {            for (int j = 1; j < 6; j++) {                int n = 5 * i + j;                System.out.printf("p(%2d) = %2d  ", n, pancake(n));            }            System.out.println();        }    }}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  ```

### With exhaustive search

Translation of: Kotlin

Uses a standard breadth-first search using a queue. Note that because java is very verbose at defining classes, we instead had `pancake` return a `Map.Entry<List<Integer>, Integer>` directly, rather than a dedicated named class. This is arguably bad practice, but keeps the snippet terse.

`import static java.util.Comparator.comparing;import static java.util.stream.Collectors.toList; import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Queue;import java.util.stream.IntStream;  public class Pancake {     private static List<Integer> flipStack(List<Integer> stack, int spatula) {        List<Integer> copy = new ArrayList<>(stack);        Collections.reverse(copy.subList(0, spatula));        return copy;    }     private static Map.Entry<List<Integer>, Integer> pancake(int n) {        List<Integer> initialStack = IntStream.rangeClosed(1, n).boxed().collect(toList());        Map<List<Integer>, Integer> stackFlips = new HashMap<>();        stackFlips.put(initialStack, 1);        Queue<List<Integer>> queue = new ArrayDeque<>();        queue.add(initialStack);        while (!queue.isEmpty()) {            List<Integer> stack = queue.remove();            int flips = stackFlips.get(stack) + 1;            for (int i = 2; i <= n; ++i) {                List<Integer> flipped = flipStack(stack, i);                if (stackFlips.putIfAbsent(flipped, flips) == null) {                    queue.add(flipped);                }            }        }        return stackFlips.entrySet().stream().max(comparing(e -> e.getValue())).get();    }     public static void main(String[] args) {        for (int i = 1; i <= 10; ++i) {            Map.Entry<List<Integer>, Integer> result = pancake(i);            System.out.printf("pancake(%s) = %s. Example: %s\n", i, result.getValue(), result.getKey());        }    }}`
Output:
```pancake(1) = 1. Example: 
pancake(2) = 2. Example: [2, 1]
pancake(3) = 4. Example: [1, 3, 2]
pancake(4) = 5. Example: [2, 4, 1, 3]
pancake(5) = 6. Example: [4, 1, 3, 5, 2]
pancake(6) = 8. Example: [4, 6, 2, 5, 1, 3]
pancake(7) = 9. Example: [1, 4, 7, 3, 6, 2, 5]
pancake(8) = 10. Example: [4, 8, 6, 3, 1, 7, 2, 5]
pancake(9) = 11. Example: [8, 3, 5, 7, 9, 1, 6, 2, 4]
```

## Julia

Translation of: Phix
`function pancake(len)    gap, gapsum, adj = 2, 2, -1    while gapsum < len        adj += 1        gap = gap * 2 - 1        gapsum += gap    end    return len + adjend for i in 1:25    print("pancake(", lpad(i, 2), ") = ", rpad(pancake(i), 5))     i % 5 == 0 && println()end `
Output:

Note that pancake(20) and above are guesswork

```pancake( 1) = 0    pancake( 2) = 1    pancake( 3) = 3    pancake( 4) = 4    pancake( 5) = 5
pancake( 6) = 7    pancake( 7) = 8    pancake( 8) = 9    pancake( 9) = 10   pancake(10) = 11
pancake(11) = 13   pancake(12) = 14   pancake(13) = 15   pancake(14) = 16   pancake(15) = 17
pancake(16) = 18   pancake(17) = 19   pancake(18) = 20   pancake(19) = 21   pancake(20) = 23
pancake(21) = 24   pancake(22) = 25   pancake(23) = 26   pancake(24) = 27   pancake(25) = 28
```

### with examples

`function pancake(len)    goalstack = collect(1:len)    stacks, numstacks = Dict(goalstack => 0), 1    newstacks = deepcopy(stacks)    for i in 1:1000        nextstacks = Dict()        for (arr, steps) in newstacks, pos in 2:len            newstack = vcat(reverse(arr[1:pos]), arr[pos+1:end])            haskey(stacks, newstack) || (nextstacks[newstack] = i)        end        newstacks = nextstacks        stacks = merge(stacks, newstacks)        perms = length(stacks)        perms == numstacks && return findmax(stacks)        numstacks = perms    endend for i in 1:10    steps, example = pancake(i)    println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example) end `
Output:
```pancake( 1) = 0     example: 
pancake( 2) = 1     example: [2, 1]
pancake( 3) = 3     example: [1, 3, 2]
pancake( 4) = 4     example: [2, 4, 1, 3]
pancake( 5) = 5     example: [5, 2, 4, 1, 3]
pancake( 6) = 7     example: [4, 6, 2, 5, 1, 3]
pancake( 7) = 8     example: [5, 1, 7, 3, 6, 2, 4]
pancake( 8) = 9     example: [6, 4, 8, 2, 5, 7, 1, 3]
pancake( 9) = 10    example: [8, 1, 4, 6, 9, 3, 7, 2, 5]
pancake(10) = 11    example: [1, 3, 8, 6, 9, 4, 2, 5, 10, 7]
```

## Kotlin

### Fast approximation

Translation of: Go – Original algorithm from Phix. The printing in main was adapted to use something more idiomatic.
`fun pancake(n: Int): Int {    var gap = 2    var sum = 2    var adj = -1    while (sum < n) {        adj++        gap = gap * 2 - 1        sum += gap    }    return n + adj} fun main() {    (1 .. 20).map {"p(%2d) = %2d".format(it, pancake(it))}    val lines = results.chunked(5).map { it.joinToString("  ") }    lines.forEach { println(it) }}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23  ```

### Using exhaustive search

Using classic breadth-first search with running queue.

`data class PancakeResult(val example: List<Int>, val depth: Int) fun pancake(n: Int): PancakeResult {  fun List<Int>.copyFlip(spatula: Int) = toMutableList().apply { subList(0, spatula).reverse() }  val initialStack = List(n) { it + 1 }  val stackFlips = mutableMapOf(initialStack to 1)  val queue = ArrayDeque(listOf(initialStack))  while (queue.isNotEmpty()) {    val stack = queue.removeFirst()    val flips = stackFlips[stack]!! + 1    for (spatula in 2 .. n) {      val flipped = stack.copyFlip(spatula)      if (stackFlips.putIfAbsent(flipped, flips) == null) {        queue.addLast(flipped)      }    }  }  return stackFlips.maxByOrNull { it.value }!!.run { PancakeResult(key, value) }} fun main() {  for (i in 1 .. 10) {    with (pancake(i)) { println("pancake(\$i) = \$depth. Example: \$example") }  }} `
Output:
```pancake(1) = 1. Example: 
pancake(2) = 2. Example: [2, 1]
pancake(3) = 4. Example: [1, 3, 2]
pancake(4) = 5. Example: [4, 2, 3, 1]
pancake(5) = 6. Example: [5, 1, 3, 2, 4]
pancake(6) = 8. Example: [5, 3, 6, 1, 4, 2]
pancake(7) = 9. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 10. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 11. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]
pancake(10) = 12. Example: [1, 3, 2, 4, 6, 8, 10, 5, 7, 9]
```

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
`            NORMAL MODE IS INTEGER            VECTOR VALUES ROW = \$5(2HP[,I2,4H] = ,I2,S2)*\$             INTERNAL FUNCTION(N)            ENTRY TO P.            GAP = 2            ADJ = -1            THROUGH LOOP, FOR SUM=2, GAP, SUM.GE.N            ADJ = ADJ + 1LOOP        GAP = GAP * 2 - 1            FUNCTION RETURN N + ADJ            END OF FUNCTION             THROUGH OUTP, FOR R=1, 5, R.G.20OUTP        PRINT FORMAT ROW, R,P.(R), R+1,P.(R+1), R+2,P.(R+2),          0     R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5)             END OF PROGRAM`
Output:
```P[ 1] =  0  P[ 2] =  1  P[ 3] =  3  P[ 4] =  4  P[ 5] =  5
P[ 6] =  7  P[ 7] =  8  P[ 8] =  9  P[ 9] = 10  P = 11
P = 13  P = 14  P = 15  P = 16  P = 17
P = 18  P = 19  P = 20  P = 21  P = 23```

## Nim

### Maximum number of flips only

Translation of: Phix

This is the translation of the second version (5th dec 2020). It differs from the first version for p(19).

`import strformat, strutils func pancake(n: int): int =  var    gap, sumGaps = 2    pg = 1    adj = -1  while sumGaps < n:    inc adj    inc pg, gap    swap pg, gap    inc sumGaps, gap  result = n + adj var line = ""for n in 1..20:  line.addSep("   ")  line.add &"p({n:>2}) = {pancake(n):>2}"  if n mod 5 == 0: (echo line; line.setLen(0))`
Output:
```p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 22   p(20) = 23```

### Exhaustive search with examples

Translation of: Julia

We used a "TableRef" rather than a "Table" to optimize some assignments (Nim uses copy semantic when assigning). We also defined a function "partialReversed" rather than using the "reversed" function and a concatenation. These optimizations reduce the running time from about 21 seconds to about 17 seconds on our small laptop.

`import sequtils, strformat, strutils, tables type  StepTable = TableRef[seq[int], int]  Result = tuple[steps: int; example: seq[int]] func findMax(t: StepTable): Result =  result.steps = -1  for example, steps in t.pairs:    if steps > result.steps:      result = (steps, example) func partialReversed(arr: openArray[int]; pos: int): seq[int] =  result.setlen(arr.len)  for i in 0..<pos:    result[i] = arr[pos - 1 - i]  for i in pos..arr.high:    result[i] = arr[i] func pancake(n: int): Result =  var goalStack = toSeq(1..n)  var stacks, newStacks: StepTable = newTable({goalStack: 0})  var numStacks = 1  for i in 1..1000:    var nextStacks = new(StepTable)    for arr, steps in newStacks.pairs:      for pos in 2..n:        let newStack = partialReversed(arr, pos)        if newStack notin stacks:          nextStacks[newStack] = i    newStacks = nextStacks    for key, value in newStacks:      stacks[key] = value    let perms = stacks.len    if perms == numStacks:      return stacks.findMax()    numStacks = perms for n in 1..10:  let (steps, example) = pancake(n)  echo &"p({n:>2}) = {steps:>2}    example: ", example.join(", ")`
Output:
```p( 1) =  0    example: 1
p( 2) =  1    example: 2, 1
p( 3) =  3    example: 1, 3, 2
p( 4) =  4    example: 3, 1, 4, 2
p( 5) =  5    example: 2, 5, 3, 1, 4
p( 6) =  7    example: 5, 3, 6, 1, 4, 2
p( 7) =  8    example: 3, 6, 1, 4, 7, 2, 5
p( 8) =  9    example: 1, 7, 5, 3, 6, 8, 4, 2
p( 9) = 10    example: 8, 2, 7, 9, 5, 3, 1, 6, 4
p(10) = 11    example: 9, 6, 3, 5, 7, 4, 10, 1, 8, 2```

## Perl

`use strict;use warnings;use feature 'say'; sub pancake {    my(\$n) = @_;    my (\$gap, \$sum, \$adj) = (2, 2, -1);    while (\$sum < \$n) { \$sum += \$gap = \$gap * 2 - 1 and \$adj++ }    \$n + \$adj;} my \$out;\$out .= sprintf "p(%2d) = %2d ", \$_, pancake \$_ for 1..20;say \$out =~ s/.{1,55}\K /\n/gr; # Maximum number of flips plus examples using exhaustive searchsub pancake2 {    my (\$n) = @_;    my \$numStacks = 1;    my @goalStack = 1 .. \$n;    my %newStacks = my %stacks = (join(' ',@goalStack), 0);    for my \$k (1..1000) {        my %nextStacks;        for my \$pos (2..\$n) {            for my \$key (keys %newStacks) {                my @arr = split ' ', \$key;                my \$cakes = join ' ', (reverse @arr[0..\$pos-1]), @arr[\$pos..\$#arr];                \$nextStacks{\$cakes} = \$k unless \$stacks{\$cakes};            }        }        %stacks = (%stacks, (%newStacks = %nextStacks));        my \$perms    = scalar %stacks;        my %inverted = reverse %stacks;        return \$k-1, \$inverted{(sort keys %inverted)[-1]} if \$perms == \$numStacks;        \$numStacks = \$perms;   }} say "\nThe maximum number of flips to sort a given number of elements is:";for my \$n (1..9) {    my (\$a,\$b) = pancake2(\$n);    say "pancake(\$n) = \$a example: \$b";}`
Output:
```p( 1) =  0 p( 2) =  1 p( 3) =  3 p( 4) =  4 p( 5) =  5
p( 6) =  7 p( 7) =  8 p( 8) =  9 p( 9) = 10 p(10) = 11
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23

The maximum number of flips to sort a given number of elements is:
pancake(1) = 0 example: 1
pancake(2) = 1 example: 1 2
pancake(3) = 3 example: 1 3 2
pancake(4) = 4 example: 2 4 1 3
pancake(5) = 5 example: 5 3 1 4 2
pancake(6) = 7 example: 5 3 6 1 4 2
pancake(7) = 8 example: 5 7 3 4 1 6 2
pancake(8) = 9 example: 3 8 5 2 7 4 1 6
pancake(9) = 10 example: 7 5 9 6 2 4 1 8 3```

## Phix

### fast estimate

Extra credit to anyone who can prove that this is in any way wrong?
(Apart from the lack of examples, that is)
The algorithm was freshly made up, from scratch, by yours truly.
It agrees with https://oeis.org/A058986/b058986.txt which would put p(20) as either 22 or 23.
(ie the p(20) shown below is actually pure guesswork, with a 50:50 chance of being correct)
Note that several other references/links disagree on p(17) and up.

`function pancake(integer n)    integer gap = 2, sum_gaps = gap, adj = -1    while sum_gaps<n do        adj += 1        gap = gap*2-1        sum_gaps += gap    end while    n += adj    return nend functionsequence t = tagset(20),         r = columnize({t,apply(t,pancake)}),         p = apply(true,sprintf,{{"p(%2d) = %2d"},r})printf(1,"%s\n",join_by(p,1,5))`
Output:
```p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 21   p(20) = 23
```

vs. max() of ten runs each of pancake_sort(shuffle(tagset(n))), modified to return the number of flips it made:

```p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  5   p( 5) =  6
p( 6) =  9   p( 7) = 10   p( 8) = 11   p( 9) = 12   p(10) = 15
p(11) = 16   p(12) = 17   p(13) = 20   p(14) = 22   p(15) = 25
p(16) = 28   p(17) = 28   p(18) = 31   p(19) = 33   p(20) = 34
```

Obviously the sort focuses on getting one pancake at a time into place, and therefore runs closer to 2n flips.

### modified (5th Dec 2020)

It seems someone has recently modified A058986/b058986.txt so here is a matching modified version, which would make p(20) either 23 or 24.

`function pancake(integer n)    integer gap = 2, pg = 1, sum_gaps = gap, adj = -1    while sum_gaps<n do        adj += 1        {pg,gap} = {gap,gap+pg}        sum_gaps += gap    end while    n += adj    return nend functionsequence t = tagset(20),         r = columnize({t,apply(t,pancake)}),         p = apply(true,sprintf,{{"p(%2d) = %2d"},r})printf(1,"%s\n",join_by(p,1,5))`
Output:
```p( 1) =  0   p( 2) =  1   p( 3) =  3   p( 4) =  4   p( 5) =  5
p( 6) =  7   p( 7) =  8   p( 8) =  9   p( 9) = 10   p(10) = 11
p(11) = 13   p(12) = 14   p(13) = 15   p(14) = 16   p(15) = 17
p(16) = 18   p(17) = 19   p(18) = 20   p(19) = 22   p(20) = 23
```

### exhaustive search, with examples

Translation of: Julia
`function visitor(sequence stack, integer /*unused*/, sequence stacks)    for pos=2 to length(stack) do--  for pos=0 to length(stack)-2 do        sequence newstack = reverse(stack[1..pos])&stack[pos+1..\$]--      sequence newstack = stack[1..pos]&reverse(stack[pos+1..\$])        if getd_index(newstack,stacks)=NULL then            setd(newstack,0,stacks[\$]) -- (next round)            setd(newstack,0,stacks) -- (the master)        end if    end for    return 1end function function pancake(integer len)    sequence goalstack = tagset(len),             stacks = {new_dict({{goalstack,0}})}    while true do        stacks &= new_dict()        -- add any flips of stacks[\$-1]        --   not already in stacks        --               to stacks[\$]        traverse_dict(visitor,stacks,stacks[\$-1])        if dict_size(stacks[\$])=0 then exit end if    end while    sequence eg = getd_partial_key(0,stacks[\$-1],true)    integer sz = dict_size(stacks[\$-1])    papply(stacks,destroy_dict)    return {length(stacks)-2,eg,sz}end function atom t0 = time()for n=1 to 8 do -- (for <2s)    {integer pn, sequence eg, integer sz} = pancake(n)    printf(1,"p(%d) = %d, example: %v (of %,d, %s)\n",{n,pn,eg,sz,elapsed(time()-t0)})end for`
Output:

Note that we are only allowed to flip the left hand side, so [eg] we cannot solve p(3) by flipping the right hand pair.
lhs-only flips, the "of nn" shows how many unique stacks we found that required p(n) flips.

```p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {1,3,2} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,3,1,5,2,6,4} (of 35, 0.2s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.6s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 7s)
```

After p(7), each subsequent p(n) takes about n times as long to complete.

rhs-only flips, using the two commented-out alternative lines in visitor(), and again showing the last one found, is more similar than I expected.

```p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {2,1,3} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,2,4,1,6,3,5} (of 35, 0.3s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.2s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)
```

## Python

Translation of: Java
Works with: Python version 3.7
`"""Pancake numbers. Requires Python>=3.7."""import time from collections import dequefrom operator import itemgetterfrom typing import Tuple Pancakes = Tuple[int, ...]  def flip(pancakes: Pancakes, position: int) -> Pancakes:    """Flip the stack of pancakes at the given position."""    return tuple([*reversed(pancakes[:position]), *pancakes[position:]])  def pancake(n: int) -> Tuple[Pancakes, int]:    """Return the nth pancake number."""    init_stack = tuple(range(1, n + 1))    stack_flips = {init_stack: 0}    queue = deque([init_stack])     while queue:        stack = queue.popleft()        flips = stack_flips[stack] + 1         for i in range(2, n + 1):            flipped = flip(stack, i)            if flipped not in stack_flips:                stack_flips[flipped] = flips                queue.append(flipped)     return max(stack_flips.items(), key=itemgetter(1))  if __name__ == "__main__":    start = time.time()     for n in range(1, 10):        pancakes, p = pancake(n)        print(f"pancake({n}) = {p:>2}. Example: {list(pancakes)}")     print(f"\nTook {time.time() - start:.3} seconds.") `
Output:
```pancake(1) =  0. Example: 
pancake(2) =  1. Example: [2, 1]
pancake(3) =  3. Example: [1, 3, 2]
pancake(4) =  4. Example: [4, 2, 3, 1]
pancake(5) =  5. Example: [5, 1, 3, 2, 4]
pancake(6) =  7. Example: [5, 3, 6, 1, 4, 2]
pancake(7) =  8. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) =  9. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 10. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]

Took 2.89 seconds.```

## Raku

### Maximum number of flips only

Translation of: C
`# 20201110 Raku programming solution sub pancake(\n) {   my (\$gap,\$sum,\$adj) = 2, 2, -1;   while (\$sum < n) { \$sum += \$gap = \$gap * 2 - 1 and \$adj++ }   return n + \$adj;} for (1..20).rotor(5) { say [~] @_».&{ sprintf "p(%2d) = %2d ",\$_,pancake \$_ } }`
Output:
```p( 1) =  0 p( 2) =  1 p( 3) =  3 p( 4) =  4 p( 5) =  5
p( 6) =  7 p( 7) =  8 p( 8) =  9 p( 9) = 10 p(10) = 11
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23```

### Maximum number of flips plus examples using exhaustive search

Translation of: Go
`sub pancake(\n) {   my @goalStack = (my \numStacks = \$ = 1)..n ;    my %newStacks = my %stacks = @goalStack.Str, 0 ;   for 1..1000 -> \k {       my %nextStacks = ();       for %newStacks.keys».split(' ') X 2..n -> (@arr, \pos) {         given flat @arr[0..^pos].reverse, @arr[pos..*-1] {            %nextStacks{\$_.Str} = k unless %stacks{\$_.Str}:exists         }      }      %stacks ,= (%newStacks = %nextStacks);      my \$perms    = %stacks.elems;      my %inverted = %stacks.antipairs;      # this causes loss on examples       my \max_key  = %inverted.keys.max;     # but not critical for our purpose      \$perms == numStacks ?? return %inverted{max_key}, k-1 !! numStacks=\$perms   }   return '', 0} say "The maximum number of flips to sort a given number of elements is:";for 1..9 -> \$j { given pancake(\$j) { say "pancake(\$j) = \$_ example: \$_" }}`
Output:
```The maximum number of flips to sort a given number of elements is:
pancake(1) = 0 example: 1
pancake(2) = 1 example: 2 1
pancake(3) = 3 example: 1 3 2
pancake(4) = 4 example: 2 4 1 3
pancake(5) = 5 example: 5 1 3 2 4
pancake(6) = 7 example: 5 3 6 1 4 2
pancake(7) = 8 example: 1 5 3 7 4 2 6
pancake(8) = 9 example: 6 1 8 3 5 7 2 4
pancake(9) = 10 example: 3 6 9 2 5 8 4 7 1```

## REXX

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: Go
Translation of: Phix
`/*REXX program calculates/displays  ten  pancake  numbers   (from 1 ──► 20, inclusive). */     pad= center(''        , 10)                                         /*indentation. */say  pad  center('pancakes', 10     )  center('pancake flips', 15     )  /*show the hdr.*/say  pad  center(''        , 10, "─")  center('',              15, "─")  /*  "   "  sep.*/          do #=1  for 20;  say pad  center(#, 10) center( pancake(#), 15) /*index, flips.*/         end   /*#*/exit 0                                           /*stick a fork in it,  we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/pancake: procedure; parse arg n;          gap= 2 /*obtain  N;  initialize the GAP.      */                                          sum= 2 /*            initialize the SUM.      */                          do adj=0  while sum <n /*perform while  SUM is less than  N.  */                          gap= gap*2 - 1         /*calculate the GAP.                   */                          sum= sum + gap         /*add the  GAP  to the  SUM.           */                          end   /*adj*/         return n +adj -1                        /*return an adjusted adjustment sum.   */`
output   when using the default inputs:
```            pancakes   pancake flips
────────── ───────────────
1             0
2             1
3             3
4             4
5             5
6             7
7             8
8             9
9            10
10           11
11           13
12           14
13           15
14           16
15           17
16           18
17           19
18           20
19           21
20           23
```

## Ring

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C

Does not show examples requiring p(n) flips, since that is beyond the capabilities of Ring.

` for n = 1 to 9     see "p(" + n + ") = " + pancake(n) + nlnextreturn 0 func pancake(n)     gap = 2     sum = 2     adj = -1;     while (sum < n)            adj = adj + 1            gap = gap * 2 - 1            sum = sum + gap     end     return n + adj `

Output:

```p(1) = 0
p(2) = 1
p(3) = 3
p(4) = 4
p(5) = 5
p(6) = 7
p(7) = 8
p(8) = 9
p(9) = 10
```

## Ruby

 This example is incomplete. Show examples requiring p(1..9) flips Please ensure that it meets all task requirements and remove this message.
Translation of: C
`def pancake(n)    gap = 2    sum = 2    adj = -1    while sum < n        adj = adj + 1        gap = gap * 2 - 1        sum = sum + gap    end    return n + adjend for i in 0 .. 3    for j in 1 .. 5        n = i * 5 + j        print "p(%2d) = %2d  " % [n, pancake(n)]    end    print "\n"end`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23```

## Wren

### Maximum number of flips only

Translation of: Phix
Library: Wren-fmt

Well, it's hard to believe it can be as simple as this but Pete's algorithm does at least give the same answers as the OEIS sequence for n <= 19 which is usually taken as the authority on these matters.

Clearly, for non-trivial 'n', the number of flips required for the pancake sorting task will generally be more as no attempt is being made there to minimize the number of flips, just to get the data into sorted order.

`import "/fmt" for Fmt var pancake = Fn.new { |n|    var gap = 2    var sum = 2    var adj = -1    while (sum < n) {        adj = adj + 1        gap = gap*2 - 1        sum = sum + gap    }    return n + adj} for (i in 0..3) {    for (j in 1..5) {        var n = i*5 + j        Fmt.write("p(\$2d) = \$2d  ", n, pancake.call(n))    }    System.print()}`
Output:
```p( 1) =  0  p( 2) =  1  p( 3) =  3  p( 4) =  4  p( 5) =  5
p( 6) =  7  p( 7) =  8  p( 8) =  9  p( 9) = 10  p(10) = 11
p(11) = 13  p(12) = 14  p(13) = 15  p(14) = 16  p(15) = 17
p(16) = 18  p(17) = 19  p(18) = 20  p(19) = 21  p(20) = 23
```

### Maximum number of flips plus examples using exhaustive search

Translation of: Julia

Takes a while to process pancake(9) though not too bad for the Wren interpreter particularly as maps don't support lists as keys and we therefore have to convert them to/from strings which is an expensive operation.

Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available.

`import "/fmt" for Fmt // Converts a string of the form "[1, 2]" into a list: [1, 2]var asList = Fn.new { |s|    var split = s[1..-2].split(", ")    return split.map { |n| Num.fromString(n) }.toList} // Merges two maps into one. If the same key is present in both maps// its value will be the one in the second map.var mergeMaps = Fn.new { |m1, m2|    var m3 = {}    for (key in m1.keys) m3[key] = m1[key]    for (key in m2.keys) m3[key] = m2[key]    return m3} // Finds the maximum value in 'dict' and returns the first key// it finds (iteration order is undefined) with that value. var findMax = Fn.new { |dict|    var max = -1    var maxKey = null    for (me in dict) {        if (me.value > max) {            max = me.value            maxKey = me.key        }    }    return maxKey} var pancake = Fn.new { |len|    var numStacks = 1    var goalStack = (1..len).toList.toString    var stacks = {goalStack: 0}    var newStacks = {goalStack: 0}    for (i in 1..1000) {        var nextStacks = {}        for (key in newStacks.keys) {            var arr = asList.call(key)            var pos = 2            while (pos <= len) {                var newStack = (arr[pos-1..0] + arr[pos..-1]).toString                if (!stacks.containsKey(newStack)) nextStacks[newStack] = i                pos = pos + 1            }        }        newStacks = nextStacks        stacks = mergeMaps.call(stacks, newStacks)        var perms = stacks.count        if (perms == numStacks) return [findMax.call(stacks), i - 1]        numStacks = perms    }} var start = System.clockSystem.print("The maximum number of flips to sort a given number of elements is:")for (i in 1..9) {    var res = pancake.call(i)    var example = res    var steps = res    Fmt.print("pancake(\$d) = \$-2d  example: \$n", i, steps, example)}System.print("\nTook %(System.clock - start) seconds.")`
Output:
```The maximum number of flips to sort a given number of elements is:
pancake(1) = 0   example: 
pancake(2) = 1   example: [2, 1]
pancake(3) = 3   example: [1, 3, 2]
pancake(4) = 4   example: [3, 1, 4, 2]
pancake(5) = 5   example: [5, 1, 3, 2, 4]
pancake(6) = 7   example: [5, 3, 6, 1, 4, 2]
pancake(7) = 8   example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 9   example: [6, 1, 3, 8, 2, 5, 7, 4]
pancake(9) = 10  example: [5, 8, 6, 1, 4, 2, 7, 9, 3]

Took 67.792918 seconds.
```