The Gates' algorithm that we saw in the previous exercise quickly sort a stack of unburned pancakes by increasing the size of the blocks of sorted pancakes. This is much faster that the naive algorithm which moves at each step the largest pancake to the bottom of still unsorted pancakes. Gates' algorithm manages to sort a stack of n pancakes in less than (5n + 5)/3 steps in the worst case, while the naive algorithm requires at most 2n steps. Gates is thus about one third faster in the worst case.
In this exercise, we will explore an adaptation of the same idea to burnt pancakes. This was first published by David X. Cohen and Manuel Blum. David Cohen co-founded a few years later the Futurama TV show full of mathematical jokes. Definitively, interesting people studied that little pancake problem...
The Cohen's algorithm is slightly easier than the Gates' one since it distinguishes less cases:
Case 1: At least one pancake is rightside up in the stack. Let p be the largest such pancake. Note that p + 1 must therefore be upside down, unless p = n (in which case there is no p + 1 pancake).
Case 2: All pancakes are downside. Again, we distinguish two sub-cases.
As you can see, we achieve one join in 2 flips in the cases 1 or 2.a. Since we need to achieve n joins to sort the stack, we can sort the stack in 2n steps if case 2.b does not occurs.
That case 2.b requires a very different handling as it is obviously not possible to achieve a join in only 2 flips. But fortunately, we can leverage the very specific setting of the stack in that case to provide the following algorithm. It sorts a stack in that exact configuration after exactly 2n steps.
Repeat n times Flip the whole stack of n pancakes Flip the top (n-1) pancakes
It may sound somehow magic, but it actually works, as depicted on an example below.
So, all in all, the Cohen algorithm manages to sort the stack of burnt pancakes in 2n steps in all cases. Quite a win over the naive algorithm for burnt pancakes that requires 3n steps.
isSelected()
so that your logs only appears in the
currently displayed world. In particular, it may help to print textually the state of the world
each time you enter the main loop.