Pancake numbers: Difference between revisions
(→{{header|Ring}}: put incorrect tag back. It needs eg "p(9) =10, e.g [9; 7; 5; 2; 8; 1; 4; 6; 3]", See F#, Go, Julia, Phix, Wren (only).) |
|||
| Line 702: | Line 702: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
{{incomplete|Ring|Show examples requiring p(1..9) flips. It needs eg "p(9)=10, e.g [9; 7; 5; 2; 8; 1; 4; 6; 3]", See (as yet only) F#, Go, Julia, Phix, or Wren.}} |
|||
{{trans|C}} |
{{trans|C}} |
||
<lang ring> |
<lang ring> |
||
Revision as of 16:52, 21 January 2021
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
<lang AWK>
- 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)
} </lang>
- 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
<lang c>#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;
}</lang>
- 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++
<lang cpp>#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;
}</lang>
- 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
<lang cowgol>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;</lang>
- 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
<lang d>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;
}
}</lang>
- 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#
<lang fsharp> // 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 (set1..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]) </lang>
- 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
Maximum number of flips only
<lang go>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()
}
}</lang>
- 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
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. <lang go>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))
}</lang>
- 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
<lang julia>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
</lang>
- 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
Exhaustive search, breadth first method. <lang julia>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
</lang>
- 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
<lang scala>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()
}
}</lang>
- 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
MAD
<lang MAD> 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</lang>
- 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
Perl
<lang 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;</lang>
- 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
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.
<lang Phix>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))</lang>
- 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
<lang Phix>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(Template: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</lang>
- 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)
Raku
<lang perl6># 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 $_ } }</lang>
- 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
<lang rexx>/*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. */</lang>
- 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
<lang 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
</lang> 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
<lang ruby>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</lang>
- 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
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. <lang ecmascript>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()
}</lang>
- 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
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. <lang ecmascript>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.")</lang>
- 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.
- Draft Programming Tasks
- AWK
- AWK examples needing attention
- Examples needing attention
- C
- C examples needing attention
- C++
- C++ examples needing attention
- Cowgol
- Cowgol examples needing attention
- D
- D examples needing attention
- F Sharp
- Go
- Julia
- Kotlin
- Kotlin examples needing attention
- MAD
- MAD examples needing attention
- Perl
- Perl examples needing attention
- Phix
- Raku
- Raku examples needing attention
- REXX
- REXX examples needing attention
- Ring
- Ring examples needing attention
- Ruby
- Ruby examples needing attention
- Wren
- Wren-fmt