Anonymous user
Pancake numbers: Difference between revisions
→{{header|MAD}}
No edit summary |
|||
Line 646:
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|Nim}}==
===Maximum number of flips only===
{{trans|Phix}}
This is the translation of the second version (5th dec 2020). It differs from the first version for p(19).
<lang Nim>import strformat, strutils
func pancake(n: int): int =
var
gap, sumGaps = 2
pg = 1
adj = -1
while sumGaps < n:
inc adj
inc pg, gap
swap pg, gap
inc sumGaps, gap
result = n + adj
var line = ""
for n in 1..20:
line.addSep(" ")
line.add &"p({n:>2}) = {pancake(n):>2}"
if n mod 5 == 0: (echo line; line.setLen(0))</lang>
{{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) = 22 p(20) = 23</pre>
===Exhaustive search with examples===
{{trans|Julia}}
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.
<lang Nim>import sequtils, strformat, strutils, tables
type
StepTable = TableRef[seq[int], int]
Result = tuple[steps: int; example: seq[int]]
func findMax(t: StepTable): Result =
result.steps = -1
for example, steps in t.pairs:
if steps > result.steps:
result = (steps, example)
func partialReversed(arr: openArray[int]; pos: int): seq[int] =
result.setlen(arr.len)
for i in 0..<pos:
result[i] = arr[pos - 1 - i]
for i in pos..arr.high:
result[i] = arr[i]
func pancake(n: int): Result =
var goalStack = toSeq(1..n)
var stacks, newStacks: StepTable = newTable({goalStack: 0})
var numStacks = 1
for i in 1..1000:
var nextStacks = new(StepTable)
for arr, steps in newStacks.pairs:
for pos in 2..n:
let newStack = partialReversed(arr, pos)
if newStack notin stacks:
nextStacks[newStack] = i
newStacks = nextStacks
for key, value in newStacks:
stacks[key] = value
let perms = stacks.len
if perms == numStacks:
return stacks.findMax()
numStacks = perms
for n in 1..10:
let (steps, example) = pancake(n)
echo &"p({n:>2}) = {steps:>2} example: ", example.join(", ")</lang>
{{out}}
<pre>p( 1) = 0 example: 1
p( 2) = 1 example: 2, 1
p( 3) = 3 example: 1, 3, 2
p( 4) = 4 example: 3, 1, 4, 2
p( 5) = 5 example: 2, 5, 3, 1, 4
p( 6) = 7 example: 5, 3, 6, 1, 4, 2
p( 7) = 8 example: 3, 6, 1, 4, 7, 2, 5
p( 8) = 9 example: 1, 7, 5, 3, 6, 8, 4, 2
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|Perl}}==
| |||