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
Pancake numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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]

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

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

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]

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

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

Translation of: C
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() {
for (i in 0 until 4) {
for (j in 1 until 6) {
val n = i * 5 + j
print("p(%2d) = %2d ".format(n, pancake(n)))
}
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  

Phix[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.
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.

exhaustive search, with examples[edit]

Translation of: Julia
function visitor(sequence stack, integer /*unused*/, sequence stacks)
for pos=2 to length(stack) do
sequence newstack = reverse(stack[1..pos])&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)
papply(stacks,destroy_dict)
return {length(stacks)-2,eg}
end function
 
atom t0 = time()
for n=1 to 8 do -- (for <2s)
{integer pn, sequence eg} = pancake(n)
printf(1,"p(%d) = %d, example: %v (%s)\n",{n,pn,eg,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.

p(1) = 0, example: {1} (0s)
p(2) = 1, example: {2,1} (0.1s)
p(3) = 3, example: {1,3,2} (0.1s)
p(4) = 4, example: {4,2,3,1} (0.1s)
p(5) = 5, example: {5,3,1,4,2} (0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (0.1s)
p(7) = 8, example: {7,3,1,5,2,6,4} (0.2s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (19.3s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (4 minutes and 11s)

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

Raku[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

REXX[edit]

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 to 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; adj= -1 /*obtain N; initialize the ADJustment.*/
gap= 2; sum= 2 /*initialize the GAP and the SUM. */
do while sum<n /*perform while SUM is less than N. */
adj= adj + 1 /*bump the value of the ADJustment. */
gap= gap*2 - 1 /*calculate the GAP. */
sum= sum + gap /*add the GAP to the SUM. */
end /*while*/
return n + adj
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

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.