I've recently been obsessed with a mobile game in which the player must stack pancakes as high as possible without letting the stack topple over. When I later explained the concept to a friend, they looked it up but instead discovered the concept of pancake sorting.
Pancake sorting? Today's undergraduate computer science programs often require students to take an algorithms course and learn about various sorting algorithms, from the inefficient bubble or insertion sort to the more performant quicksort or merge sort to the highly efficient radix or bucket sort. But in all my computer science years, I had never encountered the pancake sorting problem!
What is pancake sorting?
Pancake sorting is the problem of sorting a stack of pancakes of various sizes so that the largest pancake ends ups on the bottom and the smallest pancake at the top. The mechanism for moving pancakes around is a spatula that can be inserted at any point of the stack to flip all of the pancakes above that point.
Pancake sorting focuses on minimizing the number of flips needed to sort the stack, called the pancake number. The cost of comparing the size of two pancakes is moot. Thus, pancake sorting algorithms are different from other sorting algorithms, where efficiency is measured by reducing the number of comparisons needed and the cost of swapping elements is moot.
An interesting variation on this problem is the burnt pancake problem. In this version, every pancake starts with a pretty top and a burnt bottom, and the final sort must have every burnt side end up on the bottom.
How efficient are pancake sorting algorithms?
The easiest pancake sorting algorithm is one that sorts the stack from bottom to top. Here's how it works. First, find the largest pancake in the stack, insert the spatula right below it, and flip. Now the largest pancake should be at the top of the stack. Then, flip the entire stack so that the largest pancake ends up on the bottom. Repeat this same process with the next-largest pancake within the unsorted portion of the stack so that it ends up one pancake from the bottom. Then, rinse and repeat with every other pancake.
With this algorithm, every pancake costs 2 flips to get into the correct position, so for a stack of n pancakes, at most 2n flips are needed. In actuality, the upper bound can be reduced to 2n - 3 flips because the last 3 pancakes can be sorted in at most 3 flips. (With only 6 permutations possible for a stack of 3 pancakes, it's very easy to confirm this via brute force.) In fact, it's possible to further reduce the 2n - 3 upper bound to 2n - c by using more efficient sorting methods for the last 4 or 5 or even 6 unsorted pancakes.
But the naïve solution is definitely not the most efficient. Today, it is known that the pancake number lies somewhere between (15/14)n and (18/11)n, though the exact value is unknown. Many notable individuals have done research to improve the bounds on pancake numbers, including Bill Gates (who published a paper in 1979) and Futurama co-creator David Cohen.
What did Bill Gates say?
Bill Gates, in collaboration with Christos Papadimitriou, helped find today's lower bound on pancake numbers.
His proof focuses on mapping pancakes to their final neighbors instead of to their final positions. Assuming the largest pancake must neighbor the plate, a stack of n pancakes will have n pancake-to-neighbor edges that must be correct in the final sort.
Framing the problem in this way is more elegant because the flip operation changes a variable number of pancake positions but always modifies a fixed number of pancake-to-neighbor edges. As a matter of fact, a single flip can only correctly connect at most one pancake to its final neighbor. Thus, in the worst-case starting scenario (where the initial stack has none of these edges correct), at least n flips are required to sort the stack.
Gates then goes on to show how a stack of 16,000 pancakes can be sorted with no less than 17,000 flips and concludes that (17/16)n is a tighter lower bound. He explains that this same trick can be used with even larger stacks to further improve this number, but he says that it isn't worth pursuing because of diminishing returns as the stack size grows.
Show me the code!
This blog post wouldn't be complete without at least one coded algorithm, so I've put together a very simple and expensive implementation:
def flip(stack, i):
"""
Flip all pancakes between the 1st and i-th pancake of the stack. Inclusive.
"""
return stack[i::-1]+stack[i+1:]
def largest(stack, i):
"""
Find the index of the largest pancake between the 1st and i-th pancake of
the stack. Inclusive.
"""
value = max(stack[:i+1])
return stack.index(value)
def is_sorted(stack):
"""
Check if pancake stack is in sorted order.
"""
return stack == sorted(stack)
def pancake_sort(stack):
"""
Sort the pancake stack.
"""
flips = 0
n = len(stack) - 1
while not is_sorted(stack):
i = largest(stack, n)
stack = flip(stack, i)
stack = flip(stack, n)
flips += 2
n -= 1
return flips
stack = [5,3,1,2,4]
pancake_sort(stack) # 8I'm still working on coding a more efficient implementation, but I don't have that done today. If I come up with something that I'm proud enough to share, I'll update this post with that code!