Pancake numbers: Difference between revisions

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.

 

=={{header|AWK}}==

{{incomplete|AWK|Show examples requiring p(1..9) flips}}

# syntax: GAWK -f PANCAKE_NUMBERS.AWK

# converted from C

return(n + adj)

}

{{out}}

<pre>

p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23

</pre>

=={{header|C}}==

{{incomplete|C|Show examples requiring p(1..9) flips}}

{{trans|Go}}

 

int pancake(int n) {

}

return 0;

{{out}}

<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5

p(16) = 18 p(17) = 19 p(18) = 20 p(19) = 21 p(20) = 23</pre>

 

{{trans|C}}

 

}

 

}

}

{{out}}

 

=={{header|Cowgol}}==

{{trans|C}}

 

 

sub pancake(n: uint8): (r: uint8) is

print_nl();

i := i + 1;

 

{{out}}

 

=={{header|D}}==

{{trans|C}}

 

int pancake(int n) {

int gap = 2, sum = 2, adj = -1;

while (sum < n) {

adj++;

sum += gap;

}

return n + adj;

}

 

void main() {

{{out}}

 

=={{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])]

 

[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])

{{out}}

<pre>

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]

</pre>

 

===Maximum number of flips only===

{{trans|Phix}}

 

import "fmt"

fmt.Println()

}

 

{{out}}

 

Not particularly fast - Julia is about 3 seconds faster on the same machine.

 

import (

}

fmt.Printf("\nTook %s\n", time.Since(start))

 

{{out}}

 

Took 57.512153273s

</pre>

 

=={{header|Julia}}==

{{trans|Phix}}

gap, gapsum, adj = 2, 2, -1

while gapsum < len

i % 5 == 0 && println()

end

<small>Note that pancake(20) and above are guesswork</small>

<pre>

=== with examples ===

Exhaustive search, breadth first method.

goalstack = collect(1:len)

stacks, numstacks = Dict(goalstack => 0), 1

println("pancake(", lpad(i, 2), ") = ", rpad(steps, 5), " example: ", example)

end

<pre>

pancake( 1) = 0 example: [1]

 

=={{header|Kotlin}}==

var gap = 2

var sum = 2

 

fun main() {

{{out}}

<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5

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|MAD}}==

{{trans|C}}

 

VECTOR VALUES ROW = $5(2HP[,I2,4H] = ,I2,S2)*$

0 R+3,P.(R+3), R+4,P.(R+4), R+5,P.(R+5)

 

{{out}}

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|Perl}}==

use warnings;

use feature 'say';

my $out;

$out .= sprintf "p(%2d) = %2d ", $_, pancake $_ for 1..20;

{{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

 

=={{header|Phix}}==

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>

(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>

{{out}}

<pre>

Obviously the sort focuses on getting one pancake at a time into place, and therefore runs closer to 2n flips.

 

 

{{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>

p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)

</pre>

 

=={{header|Raku}}==

{{trans|C}}

 

sub pancake(\n) {

}

 

{{out}}

<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5

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|REXX}}==

{{trans|Go}}

{{trans|Phix}}

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

19 21

20 23

</pre>

 

=={{header|Ring}}==

{{trans|C}}

for n = 1 to 9

see "p(" + n + ") = " + pancake(n) + nl

end

return n + adj

Output:

<pre>

{{incomplete|Ruby|Show examples requiring p(1..9) flips}}

{{trans|C}}

gap = 2

sum = 2

end

print "\n"

{{out}}

<pre>p( 1) = 0 p( 2) = 1 p( 3) = 3 p( 4) = 4 p( 5) = 5

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}}==

 

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|

}

System.print()

 

{{out}}

 

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]

Fmt.print("pancake($d) = $-2d example: $n", i, steps, example)

}

 

{{out}}