Pancake numbers: Difference between revisions
A Python implementation
m (→{{header|FreeBASIC}}: copied warning from the C example this was translated from) |
(A Python implementation) |
||
Line 955:
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)
</pre>
=={{header|Python}}==
{{trans|Java}}
{{works with|Python|3.7}}
<lang python>"""Pancake numbers. Requires Python>=3.7."""
import time
from collections import deque
from operator import itemgetter
from typing import Tuple
Pancakes = Tuple[int, ...]
def flip(pancakes: Pancakes, position: int) -> Pancakes:
"""Flip the stack of pancakes at the given position."""
return tuple([*reversed(pancakes[:position]), *pancakes[position:]])
def pancake(n: int) -> Tuple[Pancakes, int]:
"""Return the nth pancake number."""
init_stack = tuple(range(1, n + 1))
stack_flips = {init_stack: 0}
queue = deque([init_stack])
while queue:
stack = queue.popleft()
flips = stack_flips[stack] + 1
for i in range(2, n + 1):
flipped = flip(stack, i)
if flipped not in stack_flips:
stack_flips[flipped] = flips
queue.append(flipped)
return max(stack_flips.items(), key=itemgetter(1))
if __name__ == "__main__":
start = time.time()
for n in range(1, 10):
pancakes, p = pancake(n)
print(f"pancake({n}) = {p:>2}. Example: {list(pancakes)}")
print(f"\nTook {time.time() - start:.3} seconds.")
</lang>
{{out}}
<pre>
pancake(1) = 0. Example: [1]
pancake(2) = 1. Example: [2, 1]
pancake(3) = 3. Example: [1, 3, 2]
pancake(4) = 4. Example: [4, 2, 3, 1]
pancake(5) = 5. Example: [5, 1, 3, 2, 4]
pancake(6) = 7. Example: [5, 3, 6, 1, 4, 2]
pancake(7) = 8. Example: [6, 2, 4, 1, 7, 3, 5]
pancake(8) = 9. Example: [1, 3, 2, 4, 6, 8, 5, 7]
pancake(9) = 10. Example: [4, 2, 3, 1, 5, 7, 9, 6, 8]
Took 2.89 seconds.</pre>
=={{header|Raku}}==
| |||