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

From Rosetta Code
Task
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
  1. Bill Gates and the pancake problem
  2. A058986



AWK[edit]

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 C
BEGIN {
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[edit]

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++[edit]

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[edit]

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 number
sub 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 item
sub 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[edit]

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#[edit]

 
// Pancake numbers. Nigel Galloway: October 28th., 2020
let 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 [1]->[1]
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[edit]

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[edit]

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 + adj
End Function
 
For n As Integer = 1 To 20
Print Using "p(##) = ## "; n; pancake(n);
If n Mod 5 = 0 Then ?
Next n
Sleep
 
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[edit]

Maximum number of flips only[edit]

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[edit]

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: [1]
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[edit]

Fast approximation[edit]

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[edit]

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: [1]
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[edit]

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 + adj
end
 
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[edit]

Exhaustive search, breadth first method.

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
end
end
 
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: [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, 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[edit]

Fast approximation[edit]

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[edit]

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: [1]
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]

MAD[edit]

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 + 1
LOOP GAP = GAP * 2 - 1
FUNCTION RETURN N + ADJ
END OF FUNCTION
 
THROUGH OUTP, FOR R=1, 5, R.G.20
OUTP 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[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

Nim[edit]

Maximum number of flips only[edit]

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[edit]

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[edit]

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 search
sub 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[edit]

fast estimate[edit]

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 n
end function
sequence 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)[edit]

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 n
end function
sequence 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[edit]

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[1])=NULL then
setd(newstack,0,stacks[$]) -- (next round)
setd(newstack,0,stacks[1]) -- (the master)
end if
end for
return 1
end 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[1]
-- 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[edit]

Translation of: Java
Works with: Python version 3.7
"""Pancake numbers. Requires Python>=3.7."""
import time
 
from collections import deque
from operator import itemgetter
from 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: [1]
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[edit]

Maximum number of flips only[edit]

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[edit]

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) = $_[1] example: $_[0]" }}
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[edit]

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[edit]

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) + nl
next
return 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[edit]

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 + adj
end
 
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[edit]

Maximum number of flips only[edit]

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[edit]

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.clock
System.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[0]
var steps = res[1]
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: [1]
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.