The cook at Sunrise Diner is sloppy and pancakes come out in all different sizes.
The waiter wants to serve a stack of pancakes with the smallest pancake on top and pancakes getting larger. The only way he can rearrange them is by inserting a spatula between two pancakes and flipping all pancakes on the spatula over. He wants to make as few flips as possible.
Given a stack of pancakes, how many flips are needed to generate a neat and sorted stack of pancakes? What is the process the waiter should follow to generate the sorted stack?
To identify pancakes, we number them so that 1 is the smallest pancake, 2 is the second smallest etc. For example, if we are given the pancakes in order (2, 4, 1, 3), then the sorted order we want to produce corresponds to (1, 2, 3, 4). See the illustration below.
Figure: Sorting four pancakes by making four flips
We can produce the sorted sequence (1, 2, 3, 4) by making four pancake flips:
- The first one flips the top two pancakes producing (4, 2, 1, 3)
- The second flip produces (3, 1, 2, 4). The largest pancake is at the bottom in its correct location. We will never involve it in a flip again.
- The next two flips put the remaining two pancakes in the correct order. The third flip produces (2 ,1, 3, 4)
- The fourth and final flip produces the sorted stack (1, 2, 3, 4).
How can we abstract the process? How shall we represent the pancakes and their position in the stack? What algorithm shall we use that will always generate the sorted stack?
Let your students discuss various strategies. Let them explain their strategy using a specific example and then ask them to describe the approach in general terms so that it can be applied to any pancake sequence and any number of pancakes.
Assume we have n pancakes. The pancakes are numbered such that 1 identifies the smallest pancake and n is the largest (as was done in the example for four pancakes). We also need to refer to the position in the stack: Position 1 of a pancake stack refers to the top and position n is the bottom position. For (2, 4, 1, 3), pancake 3 is at position 4 in the stack.
One pancake sorting proceeds as follows:
- Find the largest pancake in the current stack that is in the wrong place: let’s say it’s pancake P in position j in the stack.
- Reverse the top j pancakes. Now pancake P is at position 1 in the stack.
- Reverse the first P pancakes. Now pancake P is at its correct position, position P.
- Go back to step 1 and repeat the process until the resulting stack is (1, 2, 3, …, n-1, n).
How many flips do we make?
- No more than two flips in each iteration.
- Each iteration puts at least one pancake in its correct and final place.
- We have to put at most n-1 pancakes in their right place
- the last pancake will then be in the right place automatically
- a pancake can be in the correct position without having to make any flips
Thus, we perform at most n-1 iterations and make at most 2(n-1) flips.
Below is an example with 7 pancakes. Using the algorithm described, how many flips are needed to produce the sorted sequence (1, 2, 3, 4, 5, 6, 7)?
Program: Algorithms_6_pancake.py
The program contains a function printCakes which prints a visual representation of the stack. Function arrangeCakes follows the description given above. The code may be more challenging for students than the other examples.
Discussion Topics
- The number of flips needed can vary quite a bit between two stacks having the same number of pancakes. Analyzing this problem in a more accurate way is nontrivial and quite challenging. For more information see http://plus.maths.org/content/os/issue54/features/colvatter/index
