Pancake numbers: Difference between revisions

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

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

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

{{trans|C}}

#include <iostream>

 

}

return 0;

{{out}}

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

{{trans|C}}

 

 

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

print_nl();

i := i + 1;

 

{{out}}

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

{{trans|C}}

 

int pancake(int n) {

writeln;

}

{{out}}

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

 

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

{{trans|C}}

Function pancake(n As Integer) As Integer

Dim As Integer gap = 2, sum = 2, adj = -1

Next n

Sleep

{{out}}

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

===Fast approximation===

{{trans|Go|Original algorithm from [[#Phix|Phix]]}}

private static int pancake(int n) {

int gap = 2;

}

}

{{out}}

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

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;

 

}

}

 

{{out}}

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

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

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

Using classic breadth-first search with running queue.

 

 

fun pancake(n: Int): PancakeResult {

}

}

 

{{out}}

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

{{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.addSep(" ")

line.add &"p({n:>2}) = {pancake(n):>2}"

 

{{out}}

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

for n in 1..10:

let (steps, example) = pancake(n)

 

{{out}}

 

=={{header|Perl}}==

use warnings;

use feature 'say';

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

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

<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: #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>

{{out}}

<pre>

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

<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: #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>

{{out}}

<pre>

=== exhaustive search, with examples ===

{{trans|Julia}}

<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: #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>

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

{{trans|Java}}

{{works with|Python|3.7}}

import time

 

 

print(f"\nTook {time.time() - start:.3} seconds.")

 

{{out}}

===Maximum number of flips only===

{{trans|C}}

 

sub pancake(\n) {

}

 

{{out}}

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

===Maximum number of flips plus examples using exhaustive search===

{{trans|Go}}

my @goalStack = (my \numStacks = $ = 1)..n ;

my %newStacks = my %stacks = @goalStack.Str, 0 ;

 

say "The maximum number of flips to sort a given number of elements is:";

 

{{out}}

{{trans|Go}}

{{trans|Phix}}

pad= center('' , 10) /*indentation. */

say pad center('pancakes', 10 ) center('pancake flips', 15 ) /*show the hdr.*/

sum= sum + gap /*add the GAP to the SUM. */

end /*adj*/

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

<pre>

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

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

 

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