Pancake numbers: Difference between revisions
(→{{header|REXX}}: added the computer programming language REXX.) |
(Cheats never beat they just make life TDS, saving grace it's still draft) |
||
Line 2: | Line 2: | ||
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. |
||
The task is to determine p(n) for n = 1 to 9 |
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)? |
[[Sorting_algorithms/Pancake_sort]] actually performs the sort some giving the number of flips used. How do these compare with p(n)? |
||
Line 16: | Line 16: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
<lang fsharp> |
<lang fsharp> |
||
// Pancake numbers. Nigel Galloway: |
// 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])] |
||
let e=let rec fG n g=match g with 0->n |_->fG (n*g) (g-1) in fG 1 z |
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 |
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 |
|_->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 (i+1) (Set.union g l) (Set.difference l g|>Set.toList) |
||
fN 0 (set[[1..z]]) [[1..z]] |
fN 0 (set[[1..z]]) [[1..z]] |
||
[1..9]|>List.iter(fun 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]) |
||
</lang> |
</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Maximum number of flips to sort 1 elements is 0. e.g [1]->[1] |
|||
1->0 2->1 3->3 4->4 5->5 6->7 7->8 8->9 9->10 |
|||
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] |
|||
</pre> |
</pre> |
||
Revision as of 14:50, 30 October 2020
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
F#
<lang fsharp> // 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 (set1..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]) </lang>
- 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]
Go
<lang go>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() }
}</lang>
- 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
Julia
<lang 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
</lang>
- Output:
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
Exhaustive search, breadth first method. <lang julia>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 i - 1 numstacks = perms end
end
for i in 1:10
print("pancake(", lpad(i, 2), ") = ", rpad(pancake(i), 5)) i % 5 == 0 && println()
end
</lang>
- Output:
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
Phix
Extra credit to anyone who can prove that this is in any way wrong?
The algorithm is freshly made up today, from scratch, by yours truly.
It agrees with https://oeis.org/A058986/b058986.txt which would put p(20) as either 22 or 23.
Note that several other references/links disagree on p(17) and up.
<lang Phix>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))</lang>
- 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.
exhaustive search
<lang Phix>function visitor(sequence arr, integer steps, sequence userdata)
integer {len,stacks,i,nextstacks} = userdata for pos=2 to len do sequence newstack = reverse(arr[1..pos])&arr[pos+1..$] if getd_index(newstack,stacks)=NULL then setd(newstack,i,nextstacks) end if end for return 1
end function
function merge(sequence arr, integer steps, integer stacks)
setd(arr,steps,stacks) return 1
end function
function pancake(integer len)
sequence goalstack = tagset(len) integer stacks = new_dict(Template:Goalstack,0), numstacks = 1, newstacks = new_dict(stacks) for i=1 to 1000 do integer nextstacks = new_dict() traverse_dict(visitor,{len,stacks,i,nextstacks},newstacks) destroy_dict(newstacks) newstacks = nextstacks traverse_dict(merge,stacks,newstacks) integer perms = dict_size(stacks) if perms == numstacks then return i-1 end if numstacks = perms end for
end function
atom t0 = time() for n=1 to 8 do -- (for <3s)
integer pn = pancake(n) printf(1,"p(%d) = %d (%s)\n",{n,pn,elapsed(time()-t0)})
end for</lang>
- Output:
p(1) = 0 (0s) p(2) = 1 (0.1s) p(3) = 3 (0.1s) p(4) = 4 (0.1s) p(5) = 5 (0.1s) p(6) = 7 (0.1s) p(7) = 8 (0.3s) p(8) = 9 (2.2s) p(9) = 10 (25.5s) p(10) = 11 (5 minutes and 35s)
After p(7), each subsequent p(n) takes about n times as long to complete.
REXX
<lang rexx>/*REXX program calculates/displays ten pancake numbers (from 1 ──► 20, inclusive). */
pad= center( , 10) /*indentation. */
say pad center('pancakes', 10 ) center('pancake flips', 15 ) /*show the hdr.*/ say pad center( , 10, "─") center(, 15, "─") /* " " sep.*/
do #=1 to 20; say pad center(#, 10) center( pancake(#), 15) /*index, flips.*/ end /*#*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ pancake: procedure; parse arg n; adj= -1 /*obtain N; initialize the ADJustment.*/
gap= 2; sum= 2 /*initialize the GAP and the SUM. */ do while sum<n /*perform while SUM is less than N. */ adj= adj + 1 /*bump the value of the ADJustment. */ gap= gap*2 - 1 /*calculate the GAP. */ sum= sum + gap /*add the GAP to the SUM. */ end /*while*/ return n + adj</lang>
- 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
Wren
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. <lang ecmascript>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()
}</lang>
- 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