Pancake numbers: Difference between revisions
Add C# implementation
m (→{{header|FreeBASIC}}: copied warning from the C example this was translated from) |
(Add C# implementation) |
||
(21 intermediate revisions by 9 users not shown) | |||
Line 16:
=={{header|AWK}}==
{{incomplete|AWK|Show examples requiring p(1..9) flips}}
<syntaxhighlight lang="awk">
# syntax: GAWK -f PANCAKE_NUMBERS.AWK
# converted from C
Line 40:
return(n + adj)
}
</syntaxhighlight>
{{out}}
<pre>
Line 48:
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23
</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}}==
{{incomplete|C|Show examples requiring p(1..9) flips}}
{{trans|Go}}
<
int pancake(int n) {
Line 73 ⟶ 342:
}
return 0;
}</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 80 ⟶ 349:
p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23</pre>
=={{header|C
{{trans|C}}
<syntaxhighlight lang="C#">
using System;
public class Pancake
{
int gap =
int sum
int adj = -1;
while (sum < n)
{
adj++;
gap = 2 * gap - 1;
sum += gap;
}
return n + adj;
}
public static void Main(string[] args)
{
for (int
{
int n = 5 * i + j;
Console.Write($"p({n,2}) = {pancake(n),2} ");
}
Console.WriteLine();
}
}
}
</syntaxhighlight>
{{out}}
<pre>
p(
p(
p(
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}}==
Line 116 ⟶ 470:
{{trans|C}}
<
sub pancake(n: uint8): (r: uint8) is
Line 160 ⟶ 514:
print_nl();
i := i + 1;
end loop;</
{{out}}
Line 170 ⟶ 524:
=={{header|D}}==
{{trans|C}}
<syntaxhighlight lang="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++;
Line 181 ⟶ 539:
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);
}
}
</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
=={{header|F_Sharp|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])]
Line 210 ⟶ 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])
</syntaxhighlight>
{{out}}
<pre>
Line 226 ⟶ 623:
=={{header|FreeBASIC}}==
===Maximum number of flips only===
{{trans|
<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
adj += 1
gap = (gap * 2) - 1
sum += gap
Wend
Line 240 ⟶ 638:
End Function
For
c += 1
Print Using "p(##) = ## "; n; pancake(n);
If c Mod 5 = 0 Then Print
Next j
Next i
Sleep</syntaxhighlight>
{{out}}
<pre>
Line 251 ⟶ 653:
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) =
</pre>
Line 257 ⟶ 659:
===Maximum number of flips only===
{{trans|Phix}}
<
import "fmt"
Line 279 ⟶ 681:
fmt.Println()
}
}</
{{out}}
Line 297 ⟶ 699:
Not particularly fast - Julia is about 3 seconds faster on the same machine.
<
import (
Line 396 ⟶ 798:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</
{{out}}
Line 419 ⟶ 821:
===Fast approximation===
{{trans|Go|Original algorithm from [[#Phix|Phix]]}}
<
private static int pancake(int n) {
int gap = 2;
Line 441 ⟶ 843:
}
}
}</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 452 ⟶ 854:
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.
<
import static java.util.stream.Collectors.toList;
Line 498 ⟶ 900:
}
}
}</
{{out}}
Line 515 ⟶ 917:
=={{header|Julia}}==
{{trans|Phix}}
<
gap, gapsum, adj = 2, 2, -1
while gapsum < len
Line 529 ⟶ 931:
i % 5 == 0 && println()
end
</
<small>Note that pancake(20) and above are guesswork</small>
<pre>
Line 541 ⟶ 943:
=== with examples ===
Exhaustive search, breadth first method.
<
goalstack = collect(1:len)
stacks, numstacks = Dict(goalstack => 0), 1
Line 563 ⟶ 965:
println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example)
end
</
<pre>
pancake( 1) = 0 example: [1]
Line 580 ⟶ 982:
===Fast approximation===
{{trans|Go|Original algorithm from [[#Phix|Phix]]. The printing in main was adapted to use something more idiomatic.}}
<
var gap = 2
var sum = 2
Line 596 ⟶ 998:
val lines = results.chunked(5).map { it.joinToString(" ") }
lines.forEach { println(it) }
}</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 606 ⟶ 1,008:
Using classic breadth-first search with running queue.
<
fun pancake(n: Int): PancakeResult {
Line 631 ⟶ 1,033:
}
}
</syntaxhighlight>
{{out}}
Line 651 ⟶ 1,053:
{{trans|C}}
<
VECTOR VALUES ROW = $5(2HP[,I2,4H] = ,I2,S2)*$
Line 668 ⟶ 1,070:
0 R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5)
END OF PROGRAM</
{{out}}
Line 681 ⟶ 1,083:
{{trans|Phix}}
This is the translation of the second version (5th dec 2020). It differs from the first version for p(19).
<
func pancake(n: int): int =
Line 699 ⟶ 1,101:
line.addSep(" ")
line.add &"p({n:>2}) = {pancake(n):>2}"
if n mod 5 == 0: (echo line; line.setLen(0))</
{{out}}
Line 711 ⟶ 1,113:
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.
<
type
Line 751 ⟶ 1,153:
for n in 1..10:
let (steps, example) = pancake(n)
echo &"p({n:>2}) = {steps:>2} example: ", example.join(", ")</
{{out}}
Line 764 ⟶ 1,166:
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}}==
<
use warnings;
use feature 'say';
Line 808 ⟶ 1,335:
my ($a,$b) = pancake2($n);
say "pancake($n) = $a example: $b";
}</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 834 ⟶ 1,361:
(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>
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<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>
<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>
<span style="color: #000000;">adj</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</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;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adj</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
Line 866 ⟶ 1,396:
=== 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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<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>
<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>
<span style="color: #000000;">adj</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<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>
<span style="color: #000000;">sum_gaps</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">gap</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">adj</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
Line 890 ⟶ 1,423:
=== exhaustive search, with examples ===
{{trans|Julia}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- for pos=0 to length(stack)-2 do</span>
<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>
<span style="color: #000080;font-style:italic;">-- sequence newstack = stack[1..pos]&reverse(stack[pos+1..$])</span>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">stacks</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
-- 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}}
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 955 ⟶ 1,491:
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)
</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}}==
===Maximum number of flips only===
{{trans|C}}
<syntaxhighlight lang="raku"
sub pancake(\n) {
Line 967 ⟶ 1,564:
}
for (1..20).rotor(5) { say [~] @_».&{ sprintf "p(%2d) = %2d ",$_,pancake $_ } }</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 976 ⟶ 1,573:
===Maximum number of flips plus examples using exhaustive search===
{{trans|Go}}
<syntaxhighlight lang="raku"
my @goalStack = (my \numStacks = $ = 1)..n ;
my %newStacks = my %stacks = @goalStack.Str, 0 ;
Line 996 ⟶ 1,593:
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]" }}</
{{out}}
Line 1,011 ⟶ 1,608:
=={{header|REXX}}==
{{trans|Go}}
{{trans|Phix}}
<
/* Gerard
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
gap= 2
sum= 2
Do adj=0 While sum <n /* perform
gap= gap*2 - 1
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:}}
<pre>
Line 1,054 ⟶ 1,653:
19 21
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>
Line 1,060 ⟶ 1,765:
{{trans|C}}
Does not show examples requiring p(n) flips, since that is beyond the capabilities of Ring.
<
for n = 1 to 9
see "p(" + n + ") = " + pancake(n) + nl
Line 1,076 ⟶ 1,781:
end
return n + adj
</syntaxhighlight>
Output:
<pre>
Line 1,093 ⟶ 1,798:
{{incomplete|Ruby|Show examples requiring p(1..9) flips}}
{{trans|C}}
<
gap = 2
sum = 2
Line 1,111 ⟶ 1,816:
end
print "\n"
end</
{{out}}
<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5
Line 1,117 ⟶ 1,822:
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|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}}==
Line 1,125 ⟶ 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.
<
var pancake = Fn.new { |n|
Line 1,145 ⟶ 1,927:
}
System.print()
}</
{{out}}
Line 1,160 ⟶ 1,942:
Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available.
<
// Converts a string of the form "[1, 2]" into a list: [1, 2]
Line 1,223 ⟶ 2,005:
Fmt.print("pancake($d) = $-2d example: $n", i, steps, example)
}
System.print("\nTook %(System.clock - start) seconds.")</
{{out}}
|