Pancake numbers: Difference between revisions
(Add C# implementation) |
|||
(33 intermediate revisions by 14 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
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. |
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. |
||
Line 16: | Line 16: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
{{incomplete|AWK|Show examples requiring p(1..9) flips}} |
{{incomplete|AWK|Show examples requiring p(1..9) flips}} |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f PANCAKE_NUMBERS.AWK |
# syntax: GAWK -f PANCAKE_NUMBERS.AWK |
||
# converted from C |
# converted from C |
||
Line 40: | Line 40: | ||
return(n + adj) |
return(n + adj) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 48: | Line 48: | ||
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 |
||
</pre> |
</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|Applesoft BASIC}}=== |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">100 HOME |
|||
110 FOR I = 0 TO 3 |
|||
120 FOR J = 1 TO 5 |
|||
130 LET N = (I * 5) + J |
|||
140 LET C = C + 1 |
|||
150 GOSUB 200 |
|||
160 PRINT "p("; N; ") = "; P; " " |
|||
170 NEXT J |
|||
180 NEXT I |
|||
190 END |
|||
200 REM pancake(n) |
|||
210 LET G = 2 : LET S = 2 : LET A = -1 |
|||
220 IF S < N THEN LET A = A + 1 : LET G = (G * 2) - 1 : LET S = S + G |
|||
230 IF S >= N THEN LET P = N + A : RETURN |
|||
240 GOTO 220</syntaxhighlight> |
|||
==={{header|BASIC256}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vb">c = 0 |
|||
for i = 0 to 3 |
|||
for j = 1 to 5 |
|||
n = (i * 5) + j |
|||
c += 1 |
|||
print "p("; rjust(string(n),2); ") = "; pancake(n); " "; |
|||
if c mod 5 = 0 then print |
|||
next j |
|||
next i |
|||
end |
|||
function pancake(n) |
|||
gap = 2 |
|||
sum = 2 |
|||
adj = -1 |
|||
while sum < n |
|||
adj += 1 |
|||
gap = (gap * 2) - 1 |
|||
sum += gap |
|||
end while |
|||
return rjust(string(n + adj), 2) |
|||
end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Chipmunk Basic}}=== |
|||
{{works with|Chipmunk Basic|3.6.4}} |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="qbasic">100 c = 0 |
|||
110 for i = 0 to 3 |
|||
120 for j = 1 to 5 |
|||
130 n = (i*5)+j |
|||
140 c = c+1 |
|||
150 print "p(";format$(n,"##");") = ";format$(pancake(n),"##");" "; |
|||
160 if c mod 5 = 0 then print |
|||
170 next j |
|||
180 next i |
|||
190 end |
|||
200 function pancake(n) |
|||
210 gap = 2 |
|||
220 sum = 2 |
|||
230 adj = -1 |
|||
240 while sum < n |
|||
250 adj = adj+1 |
|||
260 gap = (gap*2)-1 |
|||
270 sum = sum+gap |
|||
280 wend |
|||
290 pancake = n+adj |
|||
300 end function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|Gambas}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vbnet">Public Sub Main() |
|||
Dim i As Integer, j As Integer, c As Integer = 0, n As Integer |
|||
For i = 0 To 3 |
|||
For j = 1 To 5 |
|||
n = (i * 5) + j |
|||
c += 1 |
|||
Print "p("; Format$(n, "##"); ") = "; Format$(pancake(n), "##"); " "; |
|||
If c Mod 5 = 0 Then Print |
|||
Next |
|||
Next |
|||
End |
|||
Function pancake(n As Integer) As Integer |
|||
Dim gap As Integer = 2, sum As Integer = 2, adj As Integer = -1 |
|||
While sum < n |
|||
adj += 1 |
|||
gap = (gap * 2) - 1 |
|||
sum += gap |
|||
Wend |
|||
Return n + adj |
|||
End Function</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|Chipmunk Basic}} |
|||
{{works with|MSX-BASIC}} |
|||
{{works with|PC-BASIC|any}} |
|||
{{works with|QBasic}} |
|||
<syntaxhighlight lang="qbasic">100 CLS |
|||
110 FOR I = 0 TO 3 |
|||
120 FOR J = 1 TO 5 |
|||
130 N = (I*5)+J |
|||
140 C = C+1 |
|||
150 GOSUB 200 |
|||
160 PRINT USING "p(##) = ## ";N;PANCAKE |
|||
170 NEXT J |
|||
180 NEXT I |
|||
190 END |
|||
200 REM pancake(n) |
|||
210 GAP = 2 |
|||
220 SUM = 2 |
|||
230 ADJ = -1 |
|||
240 IF SUM < N THEN ADJ = ADJ+1 : GAP = (GAP*2)-1 : SUM = SUM+GAP |
|||
250 IF SUM >= N THEN PANCAKE = N+ADJ : RETURN |
|||
260 GOTO 240</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
==={{header|MSX Basic}}=== |
|||
<syntaxhighlight lang="qbasic"></syntaxhighlight> |
|||
The [[#GW-BASIC|GW-BASIC]] solution works without any changes. |
|||
==={{header|PureBasic}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="purebasic">Procedure pancake(n) |
|||
gap.i = 2 |
|||
sum.i = 2 |
|||
adj.i = -1 |
|||
While sum < n |
|||
adj + 1 |
|||
gap = (gap * 2) - 1 |
|||
sum + gap |
|||
Wend |
|||
ProcedureReturn n + adj |
|||
EndProcedure |
|||
OpenConsole() |
|||
Define.i i, j, c, n |
|||
For i = 0 To 3 |
|||
For j = 1 To 5 |
|||
n = (i * 5) + j |
|||
c + 1 |
|||
Print("p(" + RSet(Str(n),2) + ") = " + RSet(Str(pancake(n)),2) + " ") |
|||
If Mod(c, 5 )= 0: PrintN(""): EndIf |
|||
Next j |
|||
Next i |
|||
Input() |
|||
CloseConsole()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|QBasic}}=== |
|||
{{works with|QBasic|1.1}} |
|||
{{works with|QuickBasic|4.5}} |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="qbasic">DECLARE FUNCTION pancake! (n) |
|||
FOR i = 0 TO 3 |
|||
FOR j = 1 TO 5 |
|||
n = (i * 5) + j |
|||
c = c + 1 |
|||
PRINT USING "p(##) = ## "; n; pancake(n); |
|||
IF c MOD 5 = 0 THEN PRINT |
|||
NEXT j |
|||
NEXT i |
|||
FUNCTION pancake (n) |
|||
gap = 2 |
|||
sum = 2 |
|||
adj = -1 |
|||
WHILE sum < n |
|||
adj = adj + 1 |
|||
gap = (gap * 2) - 1 |
|||
sum = sum + gap |
|||
WEND |
|||
pancake = n + adj |
|||
END FUNCTION</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
==={{header|True BASIC}}=== |
|||
{{trans|QBasic}} |
|||
<syntaxhighlight lang="qbasic">FUNCTION pancake(n) |
|||
LET gap = 2 |
|||
LET sum = 2 |
|||
LET adj = -1 |
|||
DO while sum < n |
|||
LET adj = adj+1 |
|||
LET gap = (gap*2)-1 |
|||
LET sum = sum+gap |
|||
LOOP |
|||
LET pancake = n+adj |
|||
END FUNCTION |
|||
FOR i = 0 to 3 |
|||
FOR j = 1 to 5 |
|||
LET n = (i*5)+j |
|||
LET c = c+1 |
|||
PRINT using "p(##) = ## ": n, pancake(n); |
|||
IF remainder(round(c),5) = 0 then PRINT |
|||
NEXT j |
|||
NEXT i |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as QBasic entry.</pre> |
|||
==={{header|Yabasic}}=== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight lang="vb">for i = 0 to 3 |
|||
for j = 1 to 5 |
|||
n = (i * 5) + j |
|||
c = c + 1 |
|||
print "p(", n using "##", ") = "; |
|||
print pancake(n) using "##", " "; |
|||
if mod(c, 5) = 0 print |
|||
next j |
|||
next i |
|||
end |
|||
sub pancake(n) |
|||
gap = 2 |
|||
sum = 2 |
|||
adj = -1 |
|||
while sum < n |
|||
adj = adj + 1 |
|||
gap = (gap * 2) - 1 |
|||
sum = sum + gap |
|||
wend |
|||
return n + adj |
|||
end sub</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as FreeBASIC entry.</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
{{incomplete|C|Show examples requiring p(1..9) flips}} |
{{incomplete|C|Show examples requiring p(1..9) flips}} |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
int pancake(int n) { |
int pancake(int n) { |
||
Line 73: | Line 342: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
Line 80: | Line 349: | ||
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> |
||
=={{header|C |
=={{header|C#}}== |
||
{{incomplete|C++|Show examples requiring p(1..9) flips}} |
|||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang="C#"> |
|||
<lang cpp>#include <iomanip> |
|||
using System; |
|||
#include <iostream> |
|||
public class Pancake |
|||
int pancake(int n) { |
|||
{ |
|||
int gap = 2, sum = 2, adj = -1; |
|||
private static int pancake(int n) |
|||
{ |
|||
gap = |
int gap = 2; |
||
sum |
int sum = 2; |
||
int adj = -1; |
|||
while (sum < n) |
|||
{ |
|||
adj++; |
|||
gap = 2 * gap - 1; |
|||
sum += gap; |
|||
} |
|||
return n + adj; |
|||
} |
} |
||
return n + adj; |
|||
} |
|||
public static void Main(string[] args) |
|||
int main() { |
|||
{ |
|||
for (int i = 0; i < 4; i++) { |
|||
for (int |
for (int i = 0; i < 4; i++) |
||
{ |
|||
for (int j = 1; j < 6; j++) |
|||
{ |
|||
int n = 5 * i + j; |
|||
Console.Write($"p({n,2}) = {pancake(n),2} "); |
|||
} |
|||
Console.WriteLine(); |
|||
} |
} |
||
std::cout << '\n'; |
|||
} |
} |
||
} |
|||
return 0; |
|||
</syntaxhighlight> |
|||
}</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
|||
p( |
p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
p( |
p( 6) = 7 p( 7) = 8 p( 8) = 9 p( 9) = 10 p(10) = 11 |
||
p( |
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 |
|||
</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="c++"> |
|||
#include <iostream> |
|||
#include <vector> |
|||
#include <algorithm> |
|||
#include <map> |
|||
#include <queue> |
|||
#include <numeric> |
|||
#include <iomanip> |
|||
std::vector<int32_t> flip_stack(std::vector<int32_t>& stack, const int32_t index) { |
|||
reverse(stack.begin(), stack.begin() + index); |
|||
return stack; |
|||
} |
|||
std::pair<std::vector<int32_t>, int32_t> pancake(const int32_t number) { |
|||
std::vector<int32_t> initial_stack(number); |
|||
std::iota(initial_stack.begin(), initial_stack.end(), 1); |
|||
std::map<std::vector<int32_t>, int32_t> stack_flips = { std::make_pair(initial_stack, 1) }; |
|||
std::queue<std::vector<int32_t>> queue; |
|||
queue.push(initial_stack); |
|||
while ( ! queue.empty() ) { |
|||
std::vector<int32_t> stack = queue.front(); |
|||
queue.pop(); |
|||
const int32_t flips = stack_flips[stack] + 1; |
|||
for ( int i = 2; i <= number; ++i ) { |
|||
std::vector<int32_t> flipped = flip_stack(stack, i); |
|||
if ( stack_flips.find(flipped) == stack_flips.end() ) { |
|||
stack_flips[flipped] = flips; |
|||
queue.push(flipped); |
|||
} |
|||
} |
|||
} |
|||
auto ptr = std::max_element( |
|||
stack_flips.begin(), stack_flips.end(), |
|||
[] ( const auto & pair1, const auto & pair2 ) { |
|||
return pair1.second < pair2.second; |
|||
} |
|||
); |
|||
return std::make_pair(ptr->first, ptr->second); |
|||
} |
|||
int main() { |
|||
for ( int32_t n = 1; n <= 9; ++n ) { |
|||
std::pair<std::vector<int32_t>, int32_t> result = pancake(n); |
|||
std::cout << "pancake(" << n << ") = " << std::setw(2) << result.second << ". Example ["; |
|||
for ( uint64_t i = 0; i < result.first.size() - 1; ++i ) { |
|||
std::cout << result.first[i] << ", "; |
|||
} |
|||
std::cout << result.first.back() << "]" << std::endl; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
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 [1, 3, 2, 5, 4] |
|||
pancake(6) = 8. Example [4, 6, 2, 5, 1, 3] |
|||
pancake(7) = 9. Example [1, 3, 7, 5, 2, 6, 4] |
|||
pancake(8) = 10. Example [1, 3, 2, 4, 6, 8, 5, 7] |
|||
pancake(9) = 11. Example [1, 2, 5, 8, 3, 6, 9, 4, 7] |
|||
</pre> |
|||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
Line 116: | Line 470: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
||
sub pancake(n: uint8): (r: uint8) is |
sub pancake(n: uint8): (r: uint8) is |
||
Line 160: | Line 514: | ||
print_nl(); |
print_nl(); |
||
i := i + 1; |
i := i + 1; |
||
end loop;</ |
end loop;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 170: | Line 524: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{incomplete|D|Show examples requiring p(1..9) flips}} |
|||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang="d"> |
|||
<lang d>import std.stdio; |
|||
import std.stdio; |
|||
import std.algorithm; |
|||
import std.random; |
|||
import std.range; |
|||
int pancake(int n) { |
int pancake(int n) { |
||
int gap = 2, sum = 2, adj = -1; |
int gap = 2, sum = 2, adj = -1; |
||
while (sum < n) { |
while (sum < n) { |
||
adj++; |
adj++; |
||
Line 181: | Line 539: | ||
sum += gap; |
sum += gap; |
||
} |
} |
||
return n + adj; |
return n + adj; |
||
} |
|||
Range pancakeSort(Range)(Range r) { |
|||
foreach_reverse (immutable i; 2 .. r.length + 1) { |
|||
immutable maxIndex = i - r[0 .. i].minPos!q{a > b}.length; |
|||
if (maxIndex + 1 != i) { |
|||
if (maxIndex != 0) { |
|||
r[0 .. maxIndex + 1].reverse(); |
|||
} |
|||
r[0 .. i].reverse(); |
|||
} |
|||
} |
|||
return r; |
|||
} |
} |
||
void main() { |
void main() { |
||
writeln("\nThe maximum number of flips to sort a given number of elements is:\n"); |
|||
foreach (i; 0..4) { |
|||
foreach (j; 1..6) { |
|||
foreach (i; 1..11) |
|||
int n = 5 * i + j; |
|||
{ |
|||
writef("p(%2d) = %2d ", n, pancake(n)); |
|||
auto data = iota(1, i+1).array; |
|||
} |
|||
writeln; |
|||
if (i != 1) { |
|||
// Protection against the edge case data.lenght == 1 not handled by randomShuffle |
|||
}</lang> |
|||
// where also data is invariant with regard to pancakeSort |
|||
do |
|||
data.randomShuffle; |
|||
while (data.isSorted); |
|||
} |
|||
auto sortedData = data.dup; |
|||
sortedData.pancakeSort; |
|||
writefln("pancake(%2d) = %2d e.g %s -> %s", i, pancake(i), data, sortedData); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
|||
The maximum number of flips to sort a given number of elements is: |
|||
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 |
|||
pancake( 1) = 0 e.g [1] -> [1] |
|||
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23</pre> |
|||
pancake( 2) = 1 e.g [2, 1] -> [1, 2] |
|||
pancake( 3) = 3 e.g [3, 2, 1] -> [1, 2, 3] |
|||
pancake( 4) = 4 e.g [3, 1, 4, 2] -> [1, 2, 3, 4] |
|||
pancake( 5) = 5 e.g [2, 4, 3, 5, 1] -> [1, 2, 3, 4, 5] |
|||
pancake( 6) = 7 e.g [2, 5, 6, 1, 4, 3] -> [1, 2, 3, 4, 5, 6] |
|||
pancake( 7) = 8 e.g [7, 1, 4, 6, 3, 5, 2] -> [1, 2, 3, 4, 5, 6, 7] |
|||
pancake( 8) = 9 e.g [3, 1, 4, 5, 2, 8, 7, 6] -> [1, 2, 3, 4, 5, 6, 7, 8] |
|||
pancake( 9) = 10 e.g [3, 6, 4, 9, 7, 1, 8, 2, 5] -> [1, 2, 3, 4, 5, 6, 7, 8, 9] |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Pancake numbers. Nigel Galloway: October 28th., 2020 |
// 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 pKake z=let n=[for n in 1..z-1->Array.ofList([n.. -1..0]@[n+1..z-1])] |
||
Line 210: | Line 607: | ||
[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]) |
[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]) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 222: | Line 619: | ||
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 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] |
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] |
||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
===Maximum number of flips only=== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="vb">Dim As Integer num_pancakes = 20 |
|||
Dim As Integer i, j, c = 0, n |
|||
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 i = 0 To 3 |
|||
For j = 1 To 5 |
|||
n = (i * 5) + j |
|||
c += 1 |
|||
Print Using "p(##) = ## "; n; pancake(n); |
|||
If c Mod 5 = 0 Then Print |
|||
Next j |
|||
Next i |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
Line 227: | Line 659: | ||
===Maximum number of flips only=== |
===Maximum number of flips only=== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 249: | Line 681: | ||
fmt.Println() |
fmt.Println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 267: | Line 699: | ||
Not particularly fast - Julia is about 3 seconds faster on the same machine. |
Not particularly fast - Julia is about 3 seconds faster on the same machine. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 366: | Line 798: | ||
} |
} |
||
fmt.Printf("\nTook %s\n", time.Since(start)) |
fmt.Printf("\nTook %s\n", time.Since(start)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 387: | Line 819: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
===Fast approximation=== |
|||
{{incomplete|Java|Show examples requiring p(1..9) flips}} |
|||
{{trans|Go}} |
{{trans|Go|Original algorithm from [[#Phix|Phix]]}} |
||
< |
<syntaxhighlight lang="java">public class Pancake { |
||
private static int pancake(int n) { |
private static int pancake(int n) { |
||
int gap = 2; |
int gap = 2; |
||
Line 411: | Line 843: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
Line 417: | Line 849: | ||
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17 |
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 </pre> |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23 </pre> |
||
===With exhaustive search=== |
|||
{{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. |
|||
<syntaxhighlight 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()); |
|||
} |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="julia">function pancake(len) |
||
gap, gapsum, adj = 2, 2, -1 |
gap, gapsum, adj = 2, 2, -1 |
||
while gapsum < len |
while gapsum < len |
||
Line 434: | Line 931: | ||
i % 5 == 0 && println() |
i % 5 == 0 && println() |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<small>Note that pancake(20) and above are guesswork</small> |
<small>Note that pancake(20) and above are guesswork</small> |
||
<pre> |
<pre> |
||
Line 446: | Line 943: | ||
=== with examples === |
=== with examples === |
||
Exhaustive search, breadth first method. |
Exhaustive search, breadth first method. |
||
< |
<syntaxhighlight lang="julia">function pancake(len) |
||
goalstack = collect(1:len) |
goalstack = collect(1:len) |
||
stacks, numstacks = Dict(goalstack => 0), 1 |
stacks, numstacks = Dict(goalstack => 0), 1 |
||
Line 468: | Line 965: | ||
println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example) |
println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
pancake( 1) = 0 example: [1] |
pancake( 1) = 0 example: [1] |
||
Line 483: | Line 980: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
===Fast approximation=== |
|||
{{incomplete|Kotlin|Show examples requiring p(1..9) flips}} |
|||
{{trans|Go|Original algorithm from [[#Phix|Phix]]. The printing in main was adapted to use something more idiomatic.}} |
|||
{{trans|C}} |
|||
< |
<syntaxhighlight lang="kotlin">fun pancake(n: Int): Int { |
||
var gap = 2 |
var gap = 2 |
||
var sum = 2 |
var sum = 2 |
||
Line 498: | Line 995: | ||
fun main() { |
fun main() { |
||
(1 .. 20).map {"p(%2d) = %2d".format(it, pancake(it))} |
|||
for (i in 0 until 4) { |
|||
val lines = results.chunked(5).map { it.joinToString(" ") } |
|||
for (j in 1 until 6) { |
|||
lines.forEach { println(it) } |
|||
val n = i * 5 + j |
|||
}</syntaxhighlight> |
|||
print("p(%2d) = %2d ".format(n, pancake(n))) |
|||
} |
|||
println() |
|||
} |
|||
}</lang> |
|||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
Line 511: | Line 1,004: | ||
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17 |
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 </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. |
|||
<syntaxhighlight 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") } |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|MAD}}== |
=={{header|MAD}}== |
||
Line 516: | Line 1,053: | ||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER |
||
VECTOR VALUES ROW = $5(2HP[,I2,4H] = ,I2,S2)*$ |
VECTOR VALUES ROW = $5(2HP[,I2,4H] = ,I2,S2)*$ |
||
Line 533: | Line 1,070: | ||
0 R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5) |
0 R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5) |
||
END OF PROGRAM</ |
END OF PROGRAM</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 541: | Line 1,078: | ||
P[11] = 13 P[12] = 14 P[13] = 15 P[14] = 16 P[15] = 17 |
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</pre> |
P[16] = 18 P[17] = 19 P[18] = 20 P[19] = 21 P[20] = 23</pre> |
||
=={{header|Nim}}== |
|||
===Maximum number of flips only=== |
|||
{{trans|Phix}} |
|||
This is the translation of the second version (5th dec 2020). It differs from the first version for p(19). |
|||
<syntaxhighlight lang="nim">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))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
===Exhaustive search with examples=== |
|||
{{trans|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. |
|||
<syntaxhighlight lang="nim">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(", ")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|ooRexx}}== |
|||
{{trans|REXX}} |
|||
<syntaxhighlight lang="oorexx">/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */ |
|||
ol='' |
|||
Do pcn=1 To 20 |
|||
ol=ol 'p('format(pcn,2)') ='format(pancake(pcn),3)' ' |
|||
If pcn//5=0 Then Do |
|||
Say strip(ol) |
|||
ol='' |
|||
End |
|||
End |
|||
Exit |
|||
/*------------------------------------------------------------------------------*/ |
|||
pancake: Procedure |
|||
Parse Arg n /* obtain N */ |
|||
gap= 2 /* 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. */</syntaxhighlight> |
|||
{{out|output}} |
|||
<pre>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</pre> |
|||
Show examples as required for this task |
|||
<syntaxhighlight lang="oorexx">/* REXX Driver for pancake.test */ |
|||
do n=2 To 10 |
|||
Call pancake n |
|||
End |
|||
Exit |
|||
pancake: Procedure |
|||
/********************************************************************** |
|||
* REXX pancake.rex |
|||
* The task is to determine p(n) for n = 1 to 9, |
|||
* and for each show an example requiring p(n) flips. |
|||
* inspired by java and output like Phix |
|||
* Note: Using q~delete(1) to get the next candidate for flipping |
|||
* has dramatic performance consequences for large stacks. |
|||
* Therefore, I leave the queue alone and use a pointer (qp) |
|||
* 20230604 Walter Pachl |
|||
**********************************************************************/ |
|||
Call time 'R' |
|||
parse arg n -- Number of pancakes |
|||
init=left('123456789abc',n) -- ordered pancakes |
|||
Call o 'heureka' n |
|||
q=.queue~new -- implements the queue |
|||
qp=1 |
|||
ex=0 |
|||
q~append(init) |
|||
stackFlips.=-1 -- initialize map |
|||
stackFlips.init=0 -- stackFlips.v: number of flips |
|||
-- from init to v |
|||
cnt.=0 |
|||
cnt.1=1 |
|||
max=0 |
|||
Do while qp<=q~items -- as long we can flip |
|||
s=q[qp] |
|||
qp+=1 -- get next element |
|||
flips=stackFlips.s+1 -- flips for the successors |
|||
cnt.flips=cnt.flips+1 -- count them |
|||
If flips>max Then ex=0 -- a new maximum |
|||
max=max(max,flips) |
|||
Do i=2 To n -- process n-1 successors |
|||
t=flip(s,i) -- one of them |
|||
If stackFlips.t=-1 Then Do -- not set so far |
|||
stackFlips.t=flips -- flips from init to t |
|||
q~append(t) -- append it to the queue |
|||
If ex<3 Then Do -- show the forst 3 examples |
|||
call o flips t |
|||
If ex>=0 Then Do -- record the data to be shown |
|||
example='' -- as an example (see o2) |
|||
Do While t<>'' |
|||
Parse Var t c +1 t |
|||
Select |
|||
When c='a' Then c=10 |
|||
When c='b' Then c=11 |
|||
When c='c' Then c=12 |
|||
Otherwise Nop |
|||
End |
|||
example=example||c||',' |
|||
End |
|||
exf=flips |
|||
example=strip(example,'T',',') |
|||
End |
|||
ex=ex+1 |
|||
End |
|||
End |
|||
End |
|||
End |
|||
Call o 'max cnt.max:' max cnt.max |
|||
te=time('E') -- elaüsed time |
|||
te=strip(format(te,8,1)) |
|||
Call o te 'seconds' |
|||
Call o '' |
|||
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)' |
|||
Return |
|||
flip: Procedure |
|||
Parse Arg s,k -- cf. flipStack in java |
|||
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1) |
|||
o: -- investigation and debug output |
|||
Return |
|||
Say arg(1) |
|||
Return lineout('heureka.txt',arg(1)) |
|||
o2: -- result to be shown in rosettacode |
|||
Say arg(1) |
|||
Call lineout 'heureka.out',arg(1) |
|||
Call lineout 'heureka.out' |
|||
Return </syntaxhighlight> |
|||
{{out|output|text= when using pancake_test.rex:}} |
|||
<pre>p(2) = 1, example: {2,1} (of 1, 0.0s) |
|||
p(3) = 3, example: {1,3,2} (of 1, 0.0s) |
|||
p(4) = 4, example: {3,1,4,2} (of 3, 0.0s) |
|||
p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s) |
|||
p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s) |
|||
p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s) |
|||
p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s) |
|||
p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 15.4s) |
|||
p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 208.0s)</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
<syntaxhighlight lang="perl">use strict; |
|||
{{incomplete|Perl|Show examples requiring p(1..9) flips}} |
|||
<lang perl>use strict; |
|||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 557: | Line 1,306: | ||
my $out; |
my $out; |
||
$out .= sprintf "p(%2d) = %2d ", $_, pancake $_ for 1..20; |
$out .= sprintf "p(%2d) = %2d ", $_, pancake $_ for 1..20; |
||
say $out =~ s/.{1,55}\K /\n/gr; |
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"; |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>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( 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(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 |
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</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
=== fast estimate === |
|||
Extra credit to anyone who can <i>prove</i> that this is in any way wrong?<br> |
Extra credit to anyone who can <i>prove</i> that this is in any way wrong?<br> |
||
<small>(Apart from the lack of examples, that is)<br> |
<small>(Apart from the lack of examples, that is)<br> |
||
Line 571: | Line 1,361: | ||
(ie the p(20) shown below is actually pure guesswork, with a 50:50 chance of being correct)<br> |
(ie the p(20) shown below is actually pure guesswork, with a 50:50 chance of being correct)<br> |
||
Note that several other references/links disagree on p(17) and up.</small> |
Note that several other references/links disagree on p(17) and up.</small> |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function pancake(integer n) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer gap = 2, sum_gaps = gap, adj = -1 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">pancake</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
while sum_gaps<n do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">adj</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
adj += 1 |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">sum_gaps</span><span style="color: #0000FF;"><</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
gap = gap*2-1 |
|||
<span style="color: #000000;">adj</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
sum_gaps += gap |
|||
<span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
end while |
|||
<span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span> |
|||
n += adj |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
return n |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adj</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span> |
|||
sequence t = tagset(20), |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
r = columnize({t,apply(t,pancake)}), |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">),</span> |
|||
p = apply(true,sprintf,{{"p(%2d) = %2d"},r}) |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pancake</span><span style="color: #0000FF;">)}),</span> |
|||
printf(1,"%s\n",join_by(p,1,5))</lang> |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"p(%2d) = %2d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 601: | Line 1,394: | ||
Obviously the sort focuses on getting one pancake at a time into place, and therefore runs closer to 2n flips. |
Obviously the sort focuses on getting one pancake at a time into place, and therefore runs closer to 2n flips. |
||
=== modified (5th Dec 2020) === |
|||
===exhaustive search, with examples=== |
|||
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. |
|||
{{trans|Julia}} |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function visitor(sequence stack, integer /*unused*/, sequence stacks) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
for pos=2 to length(stack) do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">pancake</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
-- for pos=0 to length(stack)-2 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pg</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">adj</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
sequence newstack = reverse(stack[1..pos])&stack[pos+1..$] |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">sum_gaps</span><span style="color: #0000FF;"><</span><span style="color: #000000;">n</span> <span style="color: #008080;">do</span> |
|||
-- sequence newstack = stack[1..pos]&reverse(stack[pos+1..$]) |
|||
<span style="color: #000000;">adj</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
if getd_index(newstack,stacks[1])=NULL then |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">pg</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">,</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">+</span><span style="color: #000000;">pg</span><span style="color: #0000FF;">}</span> |
|||
setd(newstack,0,stacks[$]) -- (next round) |
|||
<span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span> |
|||
setd(newstack,0,stacks[1]) -- (the master) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end if |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adj</span> |
|||
end for |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span> |
|||
return 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
end function |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pancake</span><span style="color: #0000FF;">)}),</span> |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"p(%2d) = %2d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">r</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=== exhaustive search, with examples === |
|||
function pancake(integer len) |
|||
{{trans|Julia}} |
|||
sequence goalstack = tagset(len), |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
stacks = {new_dict({{goalstack,0}})} |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
while true do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">visitor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000080;font-style:italic;">/*unused*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">stacks</span><span style="color: #0000FF;">)</span> |
|||
stacks &= new_dict() |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
-- add any flips of stacks[$-1] |
|||
<span style="color: #000080;font-style:italic;">-- for pos=0 to length(stack)-2 do</span> |
|||
-- not already in stacks[1] |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newstack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span> |
|||
-- to stacks[$] |
|||
<span style="color: #000080;font-style:italic;">-- sequence newstack = stack[1..pos]&reverse(stack[pos+1..$])</span> |
|||
traverse_dict(visitor,stacks,stacks[$-1]) |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newstack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> |
|||
if dict_size(stacks[$])=0 then exit end if |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newstack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[$])</span> <span style="color: #000080;font-style:italic;">-- (next round)</span> |
|||
end while |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newstack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #000080;font-style:italic;">-- (the master)</span> |
|||
sequence eg = getd_partial_key(0,stacks[$-1],true) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer sz = dict_size(stacks[$-1]) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
papply(stacks,destroy_dict) |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span> |
|||
return {length(stacks)-2,eg,sz} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
end function |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">pancake</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">)</span> |
|||
atom t0 = time() |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">goalstack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">),</span> |
|||
for n=1 to 8 do -- (for <2s) |
|||
<span style="color: #000000;">stacks</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">goalstack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}})}</span> |
|||
{integer pn, sequence eg, integer sz} = pancake(n) |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
printf(1,"p(%d) = %d, example: %v (of %,d, %s)\n",{n,pn,eg,sz,elapsed(time()-t0)}) |
|||
<span style="color: #000000;">stacks</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span> |
|||
end for</lang> |
|||
<span style="color: #000080;font-style:italic;">-- add any flips of stacks[$-1] |
|||
-- not already in stacks[1] |
|||
-- to stacks[$]</span> |
|||
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">visitor</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[$])=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">eg</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">sz</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">[$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stacks</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">eg</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sz</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">8</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (for <2s)</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">pn</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">eg</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">sz</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pancake</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"p(%d) = %d, example: %v (of %,d, %s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">eg</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sz</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
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.<br> |
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.<br> |
||
Line 668: | Line 1,491: | ||
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s) |
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s) |
||
</pre> |
</pre> |
||
=={{header|Python}}== |
|||
{{trans|Java}} |
|||
{{works with|Python|3.7}} |
|||
<syntaxhighlight lang="python">"""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.") |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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.</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
===Maximum number of flips only=== |
|||
{{incomplete|Raku|Show examples requiring p(1..9) flips}} |
|||
{{trans|C}} |
{{trans|C}} |
||
<lang |
<syntaxhighlight lang="raku" line># 20201110 Raku programming solution |
||
sub pancake(\n) { |
sub pancake(\n) { |
||
Line 680: | Line 1,564: | ||
} |
} |
||
for (1..20).rotor(5) { say [~] @_».&{ sprintf "p(%2d) = %2d ",$_,pancake $_ } }</ |
for (1..20).rotor(5) { say [~] @_».&{ sprintf "p(%2d) = %2d ",$_,pancake $_ } }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
Line 686: | Line 1,570: | ||
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17 |
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</pre> |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23</pre> |
||
===Maximum number of flips plus examples using exhaustive search=== |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="raku" line>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]" }}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
{{incomplete|REXX|Show examples requiring p(1..9) flips}} |
|||
{{trans|Go}} |
{{trans|Go}} |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */ |
||
/* Gerard Schildberger's code reformatted and refurbished */ |
|||
pad=copies(' ',10) /*indentation. */ |
|||
Say pad center('pancakes',10 ) center('pancake flips',15) /*show the hdr.*/ |
|||
Say pad center('' ,10,"-") center('',15,"-") /* " " sep.*/ |
|||
Do pcn=1 To 20 |
|||
do #=1 for 20; say pad center(#, 10) center( pancake(#), 15) /*index, flips.*/ |
|||
Say pad center(pcn,10) center(pancake(pcn),15) /*index,flips. */ |
|||
end /*#*/ |
|||
End |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
Exit /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
/*------------------------------------------------------------------------------*/ |
|||
pancake: procedure; parse arg n; gap= 2 /*obtain N; initialize the GAP. */ |
|||
pancake: Procedure |
|||
sum= 2 /* initialize the SUM. */ |
|||
Parse Arg n /* obtain N */ |
|||
gap= 2 /* 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. */ </syntaxhighlight> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 731: | Line 1,653: | ||
19 21 |
19 21 |
||
20 23 |
20 23 |
||
</pre> |
|||
Show examples as required for this task |
|||
<syntaxhighlight lang="rexx"> |
|||
/* REXX Driver for pancake.test */ |
|||
do n=2 To 10 |
|||
Call pancake n |
|||
End |
|||
pancake: Procedure |
|||
/********************************************************************** |
|||
* REXX pancake.rex |
|||
* The task is to determine p(n) for n = 1 to 9, |
|||
* and for each show an example requiring p(n) flips. |
|||
* inspired by java and output like Phix |
|||
* 20230531 Walter Pachl |
|||
**********************************************************************/ |
|||
Call time 'R' |
|||
parse arg n -- Number of pancakes |
|||
init=left('123456789abc',n) -- ordered pancakes |
|||
Call o 'heureka' n |
|||
q.=0 -- implements the queue |
|||
qp=1 |
|||
ex=0 |
|||
call qadd init |
|||
stackFlips.=-1 -- initialize map |
|||
stackFlips.init=0 -- stackFlips.v: number of flips |
|||
-- from init to v |
|||
cnt.=0 |
|||
cnt.1=1 |
|||
max=0 |
|||
Do while qp<=q.0 -- as long we can flip |
|||
s=qget() -- get head of queue |
|||
flips=stackFlips.s+1 -- flips for the successors |
|||
cnt.flips=cnt.flips+1 -- count them |
|||
If flips>max Then ex=0 -- a new maximum |
|||
max=max(max,flips) |
|||
Do i=2 To n -- process n-1 successors |
|||
t=flip(s,i) -- one of them |
|||
If stackFlips.t=-1 Then Do -- not set so far |
|||
stackFlips.t=flips -- flips from init to t |
|||
Call qadd t -- append it to the queue |
|||
If ex<3 Then Do -- show the first 3 examples |
|||
call o flips t |
|||
If ex>=0 Then Do -- record the data to be shown |
|||
example='' -- as an example (see o2) |
|||
Do While t<>'' |
|||
Parse Var t c +1 t |
|||
Select |
|||
When c='a' Then c=10 |
|||
When c='b' Then c=11 |
|||
When c='c' Then c=12 |
|||
Otherwise Nop |
|||
End |
|||
example=example||c||',' |
|||
End |
|||
exf=flips |
|||
example=strip(example,'T',',') |
|||
End |
|||
ex=ex+1 |
|||
End |
|||
End |
|||
End |
|||
End |
|||
Call o 'max cnt.max:' max cnt.max |
|||
te=time('E') -- elapsed time |
|||
te=strip(format(te,8,1)) |
|||
Call o te 'seconds' |
|||
Call o '' |
|||
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)' |
|||
Return |
|||
flip: Procedure |
|||
Parse Arg s,k -- cf. flipStack in java |
|||
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1) |
|||
qadd: -- add an element to the queue |
|||
Parse Arg e |
|||
z=q.0+1 |
|||
q.z=e |
|||
q.0=z |
|||
Return |
|||
qget: -- get top element from the queue |
|||
e=q.qp -- and remove it from the queue |
|||
qp=qp+1 |
|||
Return e |
|||
o: -- investigation and debug output |
|||
Return |
|||
Say arg(1) |
|||
Return lineout('heureka.txt',arg(1)) |
|||
o2: -- result to be shown in rosettacode |
|||
Say arg(1) |
|||
Call lineout 'heureka.out',arg(1) |
|||
Call lineout 'heureka.out' |
|||
Return</syntaxhighlight> |
|||
{{out|output|text= when using pancake_test.rex:}} |
|||
<pre>p(2) = 1, example: {2,1} (of 1, 0.0s) |
|||
p(3) = 3, example: {1,3,2} (of 1, 0.0s) |
|||
p(4) = 4, example: {3,1,4,2} (of 3, 0.0s) |
|||
p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s) |
|||
p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s) |
|||
p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s) |
|||
p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s) |
|||
p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 11.6s) |
|||
p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 238.5s) |
|||
</pre> |
</pre> |
||
Line 737: | Line 1,765: | ||
{{trans|C}} |
{{trans|C}} |
||
Does not show examples requiring p(n) flips, since that is beyond the capabilities of Ring. |
Does not show examples requiring p(n) flips, since that is beyond the capabilities of Ring. |
||
< |
<syntaxhighlight lang="ring"> |
||
for n = 1 to 9 |
for n = 1 to 9 |
||
see "p(" + n + ") = " + pancake(n) + nl |
see "p(" + n + ") = " + pancake(n) + nl |
||
Line 753: | Line 1,781: | ||
end |
end |
||
return n + adj |
return n + adj |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 770: | Line 1,798: | ||
{{incomplete|Ruby|Show examples requiring p(1..9) flips}} |
{{incomplete|Ruby|Show examples requiring p(1..9) flips}} |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="ruby">def pancake(n) |
||
gap = 2 |
gap = 2 |
||
sum = 2 |
sum = 2 |
||
Line 788: | Line 1,816: | ||
end |
end |
||
print "\n" |
print "\n" |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 |
||
Line 794: | Line 1,822: | ||
p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17 |
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</pre> |
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23</pre> |
||
=={{header|Rust}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="Rust"> |
|||
fn pancake(n: i32) -> i32 { |
|||
let mut gap = 2; |
|||
let mut sum = 2; |
|||
let mut adj = -1; |
|||
while sum < n { |
|||
adj += 1; |
|||
gap = gap * 2 - 1; |
|||
sum += gap; |
|||
} |
|||
n + adj |
|||
} |
|||
fn main() { |
|||
for i in 0..4 { |
|||
for j in 1..6 { |
|||
let n = i * 5 + j; |
|||
print!("p({:2}) = {:2} ", n, pancake(n)); |
|||
} |
|||
println!(); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="Scala"> |
|||
object Pancake { |
|||
def pancake(n: Int): Int = { |
|||
var gap = 2 |
|||
var sum = 2 |
|||
var adj = -1 |
|||
while (sum < n) { |
|||
adj += 1 |
|||
gap = 2 * gap - 1 |
|||
sum += gap |
|||
} |
|||
n + adj |
|||
} |
|||
def main(args: Array[String]): Unit = { |
|||
for (i <- 0 until 4) { |
|||
for (j <- 1 until 6) { |
|||
val n = 5 * i + j |
|||
print(f"p($n%2d) = ${pancake(n)}%2d ") |
|||
} |
|||
println() |
|||
} |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Line 802: | Line 1,907: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
var pancake = Fn.new { |n| |
var pancake = Fn.new { |n| |
||
Line 822: | Line 1,927: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 837: | Line 1,942: | ||
Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available. |
Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available. |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
// Converts a string of the form "[1, 2]" into a list: [1, 2] |
// Converts a string of the form "[1, 2]" into a list: [1, 2] |
||
Line 900: | Line 2,005: | ||
Fmt.print("pancake($d) = $-2d example: $n", i, steps, example) |
Fmt.print("pancake($d) = $-2d example: $n", i, steps, example) |
||
} |
} |
||
System.print("\nTook %(System.clock - start) seconds.")</ |
System.print("\nTook %(System.clock - start) seconds.")</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 08:42, 20 January 2024
You are encouraged to solve this task according to the task description, using any language you may know.
Adrian Monk has problems and an assistant, Sharona Fleming. Sharona can deal with most of Adrian's problems except his lack of punctuality paying her remuneration. 2 pay checks down and she prepares him pancakes for breakfast. Knowing that he will be unable to eat them unless they are stacked in ascending order of size she leaves him only a skillet which he can insert at any point in the pile and flip all the above pancakes, repeating until the pile is sorted. Sharona has left the pile of n pancakes such that the maximum number of flips is required. Adrian is determined to do this in as few flips as possible. This sequence n->p(n) is known as the Pancake numbers.
The task is to determine p(n) for n = 1 to 9, and for each show an example requiring p(n) flips.
Sorting_algorithms/Pancake_sort actually performs the sort some giving the number of flips used. How do these compare with p(n)?
Few people know p(20), generously I shall award an extra credit for anyone doing more than p(16).
- References
AWK
# 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
BASIC
Applesoft BASIC
100 HOME
110 FOR I = 0 TO 3
120 FOR J = 1 TO 5
130 LET N = (I * 5) + J
140 LET C = C + 1
150 GOSUB 200
160 PRINT "p("; N; ") = "; P; " "
170 NEXT J
180 NEXT I
190 END
200 REM pancake(n)
210 LET G = 2 : LET S = 2 : LET A = -1
220 IF S < N THEN LET A = A + 1 : LET G = (G * 2) - 1 : LET S = S + G
230 IF S >= N THEN LET P = N + A : RETURN
240 GOTO 220
BASIC256
c = 0
for i = 0 to 3
for j = 1 to 5
n = (i * 5) + j
c += 1
print "p("; rjust(string(n),2); ") = "; pancake(n); " ";
if c mod 5 = 0 then print
next j
next i
end
function pancake(n)
gap = 2
sum = 2
adj = -1
while sum < n
adj += 1
gap = (gap * 2) - 1
sum += gap
end while
return rjust(string(n + adj), 2)
end function
- Output:
Same as FreeBASIC entry.
Chipmunk Basic
100 c = 0
110 for i = 0 to 3
120 for j = 1 to 5
130 n = (i*5)+j
140 c = c+1
150 print "p(";format$(n,"##");") = ";format$(pancake(n),"##");" ";
160 if c mod 5 = 0 then print
170 next j
180 next i
190 end
200 function pancake(n)
210 gap = 2
220 sum = 2
230 adj = -1
240 while sum < n
250 adj = adj+1
260 gap = (gap*2)-1
270 sum = sum+gap
280 wend
290 pancake = n+adj
300 end function
- Output:
Same as FreeBASIC entry.
Gambas
Public Sub Main()
Dim i As Integer, j As Integer, c As Integer = 0, n As Integer
For i = 0 To 3
For j = 1 To 5
n = (i * 5) + j
c += 1
Print "p("; Format$(n, "##"); ") = "; Format$(pancake(n), "##"); " ";
If c Mod 5 = 0 Then Print
Next
Next
End
Function pancake(n As Integer) As Integer
Dim gap As Integer = 2, sum As Integer = 2, adj As Integer = -1
While sum < n
adj += 1
gap = (gap * 2) - 1
sum += gap
Wend
Return n + adj
End Function
- Output:
Same as FreeBASIC entry.
GW-BASIC
100 CLS
110 FOR I = 0 TO 3
120 FOR J = 1 TO 5
130 N = (I*5)+J
140 C = C+1
150 GOSUB 200
160 PRINT USING "p(##) = ## ";N;PANCAKE
170 NEXT J
180 NEXT I
190 END
200 REM pancake(n)
210 GAP = 2
220 SUM = 2
230 ADJ = -1
240 IF SUM < N THEN ADJ = ADJ+1 : GAP = (GAP*2)-1 : SUM = SUM+GAP
250 IF SUM >= N THEN PANCAKE = N+ADJ : RETURN
260 GOTO 240
- 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
MSX Basic
The GW-BASIC solution works without any changes.
PureBasic
Procedure pancake(n)
gap.i = 2
sum.i = 2
adj.i = -1
While sum < n
adj + 1
gap = (gap * 2) - 1
sum + gap
Wend
ProcedureReturn n + adj
EndProcedure
OpenConsole()
Define.i i, j, c, n
For i = 0 To 3
For j = 1 To 5
n = (i * 5) + j
c + 1
Print("p(" + RSet(Str(n),2) + ") = " + RSet(Str(pancake(n)),2) + " ")
If Mod(c, 5 )= 0: PrintN(""): EndIf
Next j
Next i
Input()
CloseConsole()
- Output:
Same as FreeBASIC entry.
QBasic
DECLARE FUNCTION pancake! (n)
FOR i = 0 TO 3
FOR j = 1 TO 5
n = (i * 5) + j
c = c + 1
PRINT USING "p(##) = ## "; n; pancake(n);
IF c MOD 5 = 0 THEN PRINT
NEXT j
NEXT i
FUNCTION pancake (n)
gap = 2
sum = 2
adj = -1
WHILE sum < n
adj = adj + 1
gap = (gap * 2) - 1
sum = sum + gap
WEND
pancake = n + adj
END FUNCTION
- Output:
Same as FreeBASIC entry.
True BASIC
FUNCTION pancake(n)
LET gap = 2
LET sum = 2
LET adj = -1
DO while sum < n
LET adj = adj+1
LET gap = (gap*2)-1
LET sum = sum+gap
LOOP
LET pancake = n+adj
END FUNCTION
FOR i = 0 to 3
FOR j = 1 to 5
LET n = (i*5)+j
LET c = c+1
PRINT using "p(##) = ## ": n, pancake(n);
IF remainder(round(c),5) = 0 then PRINT
NEXT j
NEXT i
END
- Output:
Same as QBasic entry.
Yabasic
for i = 0 to 3
for j = 1 to 5
n = (i * 5) + j
c = c + 1
print "p(", n using "##", ") = ";
print pancake(n) using "##", " ";
if mod(c, 5) = 0 print
next j
next i
end
sub pancake(n)
gap = 2
sum = 2
adj = -1
while sum < n
adj = adj + 1
gap = (gap * 2) - 1
sum = sum + gap
wend
return n + adj
end sub
- Output:
Same as FreeBASIC entry.
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;
}
- 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#
using System;
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;
Console.Write($"p({n,2}) = {pancake(n),2} ");
}
Console.WriteLine();
}
}
}
- 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++
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <numeric>
#include <iomanip>
std::vector<int32_t> flip_stack(std::vector<int32_t>& stack, const int32_t index) {
reverse(stack.begin(), stack.begin() + index);
return stack;
}
std::pair<std::vector<int32_t>, int32_t> pancake(const int32_t number) {
std::vector<int32_t> initial_stack(number);
std::iota(initial_stack.begin(), initial_stack.end(), 1);
std::map<std::vector<int32_t>, int32_t> stack_flips = { std::make_pair(initial_stack, 1) };
std::queue<std::vector<int32_t>> queue;
queue.push(initial_stack);
while ( ! queue.empty() ) {
std::vector<int32_t> stack = queue.front();
queue.pop();
const int32_t flips = stack_flips[stack] + 1;
for ( int i = 2; i <= number; ++i ) {
std::vector<int32_t> flipped = flip_stack(stack, i);
if ( stack_flips.find(flipped) == stack_flips.end() ) {
stack_flips[flipped] = flips;
queue.push(flipped);
}
}
}
auto ptr = std::max_element(
stack_flips.begin(), stack_flips.end(),
[] ( const auto & pair1, const auto & pair2 ) {
return pair1.second < pair2.second;
}
);
return std::make_pair(ptr->first, ptr->second);
}
int main() {
for ( int32_t n = 1; n <= 9; ++n ) {
std::pair<std::vector<int32_t>, int32_t> result = pancake(n);
std::cout << "pancake(" << n << ") = " << std::setw(2) << result.second << ". Example [";
for ( uint64_t i = 0; i < result.first.size() - 1; ++i ) {
std::cout << result.first[i] << ", ";
}
std::cout << result.first.back() << "]" << std::endl;
}
}
- 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 [1, 3, 2, 5, 4] pancake(6) = 8. Example [4, 6, 2, 5, 1, 3] pancake(7) = 9. Example [1, 3, 7, 5, 2, 6, 4] pancake(8) = 10. Example [1, 3, 2, 4, 6, 8, 5, 7] pancake(9) = 11. Example [1, 2, 5, 8, 3, 6, 9, 4, 7]
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;
- 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
import std.stdio;
import std.algorithm;
import std.random;
import std.range;
int pancake(int n) {
int gap = 2, sum = 2, adj = -1;
while (sum < n) {
adj++;
gap = 2 * gap - 1;
sum += gap;
}
return n + adj;
}
Range pancakeSort(Range)(Range r) {
foreach_reverse (immutable i; 2 .. r.length + 1) {
immutable maxIndex = i - r[0 .. i].minPos!q{a > b}.length;
if (maxIndex + 1 != i) {
if (maxIndex != 0) {
r[0 .. maxIndex + 1].reverse();
}
r[0 .. i].reverse();
}
}
return r;
}
void main() {
writeln("\nThe maximum number of flips to sort a given number of elements is:\n");
foreach (i; 1..11)
{
auto data = iota(1, i+1).array;
if (i != 1) {
// Protection against the edge case data.lenght == 1 not handled by randomShuffle
// where also data is invariant with regard to pancakeSort
do
data.randomShuffle;
while (data.isSorted);
}
auto sortedData = data.dup;
sortedData.pancakeSort;
writefln("pancake(%2d) = %2d e.g %s -> %s", i, pancake(i), data, sortedData);
}
}
- Output:
The maximum number of flips to sort a given number of elements is: pancake( 1) = 0 e.g [1] -> [1] pancake( 2) = 1 e.g [2, 1] -> [1, 2] pancake( 3) = 3 e.g [3, 2, 1] -> [1, 2, 3] pancake( 4) = 4 e.g [3, 1, 4, 2] -> [1, 2, 3, 4] pancake( 5) = 5 e.g [2, 4, 3, 5, 1] -> [1, 2, 3, 4, 5] pancake( 6) = 7 e.g [2, 5, 6, 1, 4, 3] -> [1, 2, 3, 4, 5, 6] pancake( 7) = 8 e.g [7, 1, 4, 6, 3, 5, 2] -> [1, 2, 3, 4, 5, 6, 7] pancake( 8) = 9 e.g [3, 1, 4, 5, 2, 8, 7, 6] -> [1, 2, 3, 4, 5, 6, 7, 8] pancake( 9) = 10 e.g [3, 6, 4, 9, 7, 1, 8, 2, 5] -> [1, 2, 3, 4, 5, 6, 7, 8, 9]
F#
// 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
Maximum number of flips only
Dim As Integer num_pancakes = 20
Dim As Integer i, j, c = 0, n
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 i = 0 To 3
For j = 1 To 5
n = (i * 5) + j
c += 1
Print Using "p(##) = ## "; n; pancake(n);
If c Mod 5 = 0 Then Print
Next j
Next i
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) = 23
Go
Maximum number of flips only
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
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
Fast approximation
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
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
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
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
Fast approximation
fun pancake(n: Int): Int {
var gap = 2
var sum = 2
var adj = -1
while (sum < n) {
adj++
gap = gap * 2 - 1
sum += gap
}
return n + adj
}
fun main() {
(1 .. 20).map {"p(%2d) = %2d".format(it, pancake(it))}
val lines = results.chunked(5).map { it.joinToString(" ") }
lines.forEach { println(it) }
}
- Output:
p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5 p( 6) = 7 p( 7) = 8 p( 8) = 9 p( 9) = 10 p(10) = 11 p(11) = 13 p(12) = 14 p(13) = 15 p(14) = 16 p(15) = 17 p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23
Using exhaustive search
Using classic breadth-first search with running queue.
data class PancakeResult(val example: List<Int>, val depth: Int)
fun pancake(n: Int): PancakeResult {
fun List<Int>.copyFlip(spatula: Int) = toMutableList().apply { subList(0, spatula).reverse() }
val initialStack = List(n) { it + 1 }
val stackFlips = mutableMapOf(initialStack to 1)
val queue = ArrayDeque(listOf(initialStack))
while (queue.isNotEmpty()) {
val stack = queue.removeFirst()
val flips = stackFlips[stack]!! + 1
for (spatula in 2 .. n) {
val flipped = stack.copyFlip(spatula)
if (stackFlips.putIfAbsent(flipped, flips) == null) {
queue.addLast(flipped)
}
}
}
return stackFlips.maxByOrNull { it.value }!!.run { PancakeResult(key, value) }
}
fun main() {
for (i in 1 .. 10) {
with (pancake(i)) { println("pancake($i) = $depth. Example: $example") }
}
}
- Output:
pancake(1) = 1. Example: [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
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
Maximum number of flips only
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
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
ooRexx
/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */
ol=''
Do pcn=1 To 20
ol=ol 'p('format(pcn,2)') ='format(pancake(pcn),3)' '
If pcn//5=0 Then Do
Say strip(ol)
ol=''
End
End
Exit
/*------------------------------------------------------------------------------*/
pancake: Procedure
Parse Arg n /* obtain N */
gap= 2 /* 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:
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
Show examples as required for this task
/* REXX Driver for pancake.test */
do n=2 To 10
Call pancake n
End
Exit
pancake: Procedure
/**********************************************************************
* REXX pancake.rex
* The task is to determine p(n) for n = 1 to 9,
* and for each show an example requiring p(n) flips.
* inspired by java and output like Phix
* Note: Using q~delete(1) to get the next candidate for flipping
* has dramatic performance consequences for large stacks.
* Therefore, I leave the queue alone and use a pointer (qp)
* 20230604 Walter Pachl
**********************************************************************/
Call time 'R'
parse arg n -- Number of pancakes
init=left('123456789abc',n) -- ordered pancakes
Call o 'heureka' n
q=.queue~new -- implements the queue
qp=1
ex=0
q~append(init)
stackFlips.=-1 -- initialize map
stackFlips.init=0 -- stackFlips.v: number of flips
-- from init to v
cnt.=0
cnt.1=1
max=0
Do while qp<=q~items -- as long we can flip
s=q[qp]
qp+=1 -- get next element
flips=stackFlips.s+1 -- flips for the successors
cnt.flips=cnt.flips+1 -- count them
If flips>max Then ex=0 -- a new maximum
max=max(max,flips)
Do i=2 To n -- process n-1 successors
t=flip(s,i) -- one of them
If stackFlips.t=-1 Then Do -- not set so far
stackFlips.t=flips -- flips from init to t
q~append(t) -- append it to the queue
If ex<3 Then Do -- show the forst 3 examples
call o flips t
If ex>=0 Then Do -- record the data to be shown
example='' -- as an example (see o2)
Do While t<>''
Parse Var t c +1 t
Select
When c='a' Then c=10
When c='b' Then c=11
When c='c' Then c=12
Otherwise Nop
End
example=example||c||','
End
exf=flips
example=strip(example,'T',',')
End
ex=ex+1
End
End
End
End
Call o 'max cnt.max:' max cnt.max
te=time('E') -- elaüsed time
te=strip(format(te,8,1))
Call o te 'seconds'
Call o ''
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)'
Return
flip: Procedure
Parse Arg s,k -- cf. flipStack in java
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1)
o: -- investigation and debug output
Return
Say arg(1)
Return lineout('heureka.txt',arg(1))
o2: -- result to be shown in rosettacode
Say arg(1)
Call lineout 'heureka.out',arg(1)
Call lineout 'heureka.out'
Return
- output when using pancake_test.rex:
p(2) = 1, example: {2,1} (of 1, 0.0s) p(3) = 3, example: {1,3,2} (of 1, 0.0s) p(4) = 4, example: {3,1,4,2} (of 3, 0.0s) p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s) p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s) p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s) p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s) p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 15.4s) p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 208.0s)
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";
}
- 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.
with javascript_semantics 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)
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.
with javascript_semantics 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
with javascript_semantics 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
"""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
Maximum number of flips only
# 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
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
/*REXX program calculates/displays 20 pancake numbers (from 1 to 20,inclusive). */
/* Gerard Schildberger's code reformatted and refurbished */
pad=copies(' ',10) /*indentation. */
Say pad center('pancakes',10 ) center('pancake flips',15) /*show the hdr.*/
Say pad center('' ,10,"-") center('',15,"-") /* " " sep.*/
Do pcn=1 To 20
Say pad center(pcn,10) center(pancake(pcn),15) /*index,flips. */
End
Exit /*stick a fork in it, we're all done. */
/*------------------------------------------------------------------------------*/
pancake: Procedure
Parse Arg n /* obtain N */
gap= 2 /* 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
Show examples as required for this task
/* REXX Driver for pancake.test */
do n=2 To 10
Call pancake n
End
pancake: Procedure
/**********************************************************************
* REXX pancake.rex
* The task is to determine p(n) for n = 1 to 9,
* and for each show an example requiring p(n) flips.
* inspired by java and output like Phix
* 20230531 Walter Pachl
**********************************************************************/
Call time 'R'
parse arg n -- Number of pancakes
init=left('123456789abc',n) -- ordered pancakes
Call o 'heureka' n
q.=0 -- implements the queue
qp=1
ex=0
call qadd init
stackFlips.=-1 -- initialize map
stackFlips.init=0 -- stackFlips.v: number of flips
-- from init to v
cnt.=0
cnt.1=1
max=0
Do while qp<=q.0 -- as long we can flip
s=qget() -- get head of queue
flips=stackFlips.s+1 -- flips for the successors
cnt.flips=cnt.flips+1 -- count them
If flips>max Then ex=0 -- a new maximum
max=max(max,flips)
Do i=2 To n -- process n-1 successors
t=flip(s,i) -- one of them
If stackFlips.t=-1 Then Do -- not set so far
stackFlips.t=flips -- flips from init to t
Call qadd t -- append it to the queue
If ex<3 Then Do -- show the first 3 examples
call o flips t
If ex>=0 Then Do -- record the data to be shown
example='' -- as an example (see o2)
Do While t<>''
Parse Var t c +1 t
Select
When c='a' Then c=10
When c='b' Then c=11
When c='c' Then c=12
Otherwise Nop
End
example=example||c||','
End
exf=flips
example=strip(example,'T',',')
End
ex=ex+1
End
End
End
End
Call o 'max cnt.max:' max cnt.max
te=time('E') -- elapsed time
te=strip(format(te,8,1))
Call o te 'seconds'
Call o ''
Call o2 'p('n') = 'exf', example: {'example'} (of' cnt.max', 'te's)'
Return
flip: Procedure
Parse Arg s,k -- cf. flipStack in java
Return substr(s,k,1)reverse(left(s,k-1))||substr(s,k+1)
qadd: -- add an element to the queue
Parse Arg e
z=q.0+1
q.z=e
q.0=z
Return
qget: -- get top element from the queue
e=q.qp -- and remove it from the queue
qp=qp+1
Return e
o: -- investigation and debug output
Return
Say arg(1)
Return lineout('heureka.txt',arg(1))
o2: -- result to be shown in rosettacode
Say arg(1)
Call lineout 'heureka.out',arg(1)
Call lineout 'heureka.out'
Return
- output when using pancake_test.rex:
p(2) = 1, example: {2,1} (of 1, 0.0s) p(3) = 3, example: {1,3,2} (of 1, 0.0s) p(4) = 4, example: {3,1,4,2} (of 3, 0.0s) p(5) = 5, example: {1,3,5,2,4} (of 20, 0.0s) p(6) = 7, example: {4,6,2,5,1,3} (of 2, 0.0s) p(7) = 8, example: {5,7,3,1,6,2,4} (of 35, 0.1s) p(8) = 9, example: {6,8,4,2,3,1,7,5} (of 455, 1.1s) p(9) = 10, example: {8,5,7,9,1,3,2,4,6} (of 5804, 11.6s) p(10) = 11, example: {5,1,3,2,4,6,10,8,9,7} (of 73232, 238.5s)
Ring
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
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
Rust
fn pancake(n: i32) -> i32 {
let mut gap = 2;
let mut sum = 2;
let mut adj = -1;
while sum < n {
adj += 1;
gap = gap * 2 - 1;
sum += gap;
}
n + adj
}
fn main() {
for i in 0..4 {
for j in 1..6 {
let n = i * 5 + j;
print!("p({:2}) = {:2} ", 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
Scala
object Pancake {
def pancake(n: Int): Int = {
var gap = 2
var sum = 2
var adj = -1
while (sum < n) {
adj += 1
gap = 2 * gap - 1
sum += gap
}
n + adj
}
def main(args: Array[String]): Unit = {
for (i <- 0 until 4) {
for (j <- 1 until 6) {
val n = 5 * i + j
print(f"p($n%2d) = ${pancake(n)}%2d ")
}
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
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.
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
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.
- Programming Tasks
- Solutions by Programming Task
- AWK
- AWK examples needing attention
- Examples needing attention
- BASIC
- Applesoft BASIC
- BASIC256
- Chipmunk Basic
- Gambas
- GW-BASIC
- MSX Basic
- PureBasic
- QBasic
- True BASIC
- Yabasic
- C
- C examples needing attention
- C sharp
- C++
- Cowgol
- Cowgol examples needing attention
- D
- F Sharp
- FreeBASIC
- Go
- Java
- Julia
- Kotlin
- MAD
- MAD examples needing attention
- Nim
- OoRexx
- Perl
- Phix
- Python
- Raku
- REXX
- Ring
- Ring examples needing attention
- Ruby
- Ruby examples needing attention
- Rust
- Scala
- Wren
- Wren-fmt