Pancake numbers: Difference between revisions
Add C# implementation
Walterpachl (talk | contribs) m (→{{header|REXX}}: make it executabke as is) |
(Add C# implementation) |
||
| (11 intermediate revisions by 5 users not shown) | |||
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}}
Line 79 ⟶ 348:
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#}}==
{{trans|C}}
<syntaxhighlight lang="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();
}
}
}
</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|C++}}==
<syntaxhighlight lang="c++">
#include <iostream>
#include <vector>
Line 90 ⟶ 406:
#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);
Line 127 ⟶ 443:
int main() {
for (
std::pair<std::vector<int32_t>, int32_t> result = pancake(n);
std::cout << "pancake(" << n << ") = " << std::setw(2) << result.second << ". Example [";
Line 307 ⟶ 623:
=={{header|FreeBASIC}}==
===Maximum number of flips only===
{{trans|
<syntaxhighlight lang="
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 321 ⟶ 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 332 ⟶ 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 845 ⟶ 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}}==
Line 1,164 ⟶ 1,610:
{{trans|Go}}
{{trans|Phix}}
<syntaxhighlight lang="rexx">/*REXX program calculates/displays
/* 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
/*------------------------------------------------------------------------------*/
pancake: Procedure
Parse Arg n /* obtain N
gap= 2
sum= 2
Do adj=0 While sum <n
gap= gap*2 - 1
sum= sum + gap
End /*adj*/
Return n +adj -1 /* return an adjusted adjustment sum. */ </syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,374 ⟶ 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,382 ⟶ 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.
<syntaxhighlight lang="
var pancake = Fn.new { |n|
Line 1,417 ⟶ 1,942:
Note that map iteration order is undefined in Wren and so the examples are (in effect) randomly chosen from those available.
<syntaxhighlight lang="
// Converts a string of the form "[1, 2]" into a list: [1, 2]
| |||