Pancake numbers: Difference between revisions
(→modified (9th March 2021): corrected to 5th Dec 2020) |
(Update Java/Kotlin a tiny it) |
||
| Line 387: | Line 387: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
=== |
===Fast approximation=== |
||
{{trans|Go}} |
{{trans|Go|Original algorithm from [[#Phix|Phix]]}} |
||
<lang java>public class Pancake { |
<lang java>public class Pancake { |
||
private static int pancake(int n) { |
private static int pancake(int n) { |
||
| Line 418: | Line 418: | ||
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre> |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre> |
||
=== |
===With exhaustive search=== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
Uses a standard breadth-first search using a queue. Note that because java is very verbose at defining classes, we instead had <code>pancake</code> return a <code>Map.Entry<List<Integer>, Integer></code> directly, rather than a dedicated named class. This is arguably bad practice, but keeps the snippet terse. |
Uses a standard breadth-first search using a queue. Note that because java is very verbose at defining classes, we instead had <code>pancake</code> return a <code>Map.Entry<List<Integer>, Integer></code> directly, rather than a dedicated named class. This is arguably bad practice, but keeps the snippet terse. |
||
| Line 548: | Line 548: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
=== |
===Fast approximation=== |
||
{{trans| |
{{trans|Go|Original algorithm from [[#Phix|Phix]]. The printing in main was adapted to use something more idiomatic.}} |
||
<lang kotlin>fun pancake(n: Int): Int { |
<lang kotlin>fun pancake(n: Int): Int { |
||
var gap = 2 |
var gap = 2 |
||
| Line 573: | Line 573: | ||
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre> |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre> |
||
=== |
===Using exhaustive search=== |
||
Using classic breadth-first search with running queue. |
Using classic breadth-first search with running queue. |
||
| Line 583: | Line 583: | ||
val stackFlips = mutableMapOf(initialStack to 1) |
val stackFlips = mutableMapOf(initialStack to 1) |
||
val queue = ArrayDeque(listOf(initialStack)) |
val queue = ArrayDeque(listOf(initialStack)) |
||
while ( |
while (queue.isNotEmpty()) { |
||
val stack = queue.removeFirst() |
val stack = queue.removeFirst() |
||
val flips = stackFlips[stack]!! + 1 |
val flips = stackFlips[stack]!! + 1 |
||
Revision as of 10:53, 10 March 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
Java
Fast approximation
<lang java>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();
}
}
}</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
With exhaustive search
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.
<lang java>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());
}
}
}</lang>
- 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
<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
Fast approximation
<lang kotlin>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) }
}</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
Using exhaustive search
Using classic breadth-first search with running queue.
<lang kotlin>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") }
}
} </lang>
- 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
<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;
- 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";
}</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 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.
<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.
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. <lang Phix>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))</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) = 22 p(20) = 23
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
Maximum number of flips only
<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
Maximum number of flips plus examples using exhaustive search
<lang perl6>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]" }}</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: 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
<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
Does not show examples requiring p(n) flips, since that is beyond the capabilities of 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
- Java
- Julia
- Kotlin
- MAD
- MAD examples needing attention
- Perl
- Phix
- Raku
- REXX
- REXX examples needing attention
- Ring
- Ring examples needing attention
- Ruby
- Ruby examples needing attention
- Wren
- Wren-fmt