Faster Pancake Sorting

Unlike others sorting problem, the expensive operation is not the comparison of values, but the flipping of pancakes. In this exercise, we will explore another algorithm that attempt to reduce the amount of stack flipping. The funny side is that this algorithm was first introduced by Bill Gates, before invented Windows.

The basic idea is to grow sequences of sorted pancakes, not necessarily starting from the bottom. We say that a sequence of ordered pancakes constitute a block while a pancake that is not part of a block is said to be free. The algorithm then considers the topmost pancake (of radius t) and search for the t+1 or t-1 pancakes (the considered neighbor is noted t+o). Eight cases may happen:

Each iteration increases the size of the blocks, so the algorithm eventually halts in all cases. A finer analysis would show that it takes at most (5n+5)/3 steps to sort the stack. That's better than the naïve algorithm, that requires 2n-3 steps.

Ваш хід

You now have almost enough information to implement this algorithm on your own. We just have to remove the last remaining ambiguities to ensure that you implement exactly the same algorithm that the correction. If several cases apply to your situation, then you should use the first given one. For example, if both cases a and b apply (e.g., with t-1 on case a and t+1 on case b), then you should apply the flips of case a. If a given case applies for both t+1 and t-1, then you should apply it to t+1.

Note that it is somehow harder than the other exercises we did so far, so don't be surprised if you need more time to achieve this. But do not give up hope, you can do it!

First write some helper functions such as isFirst() or isFree(). This will simplify your main algorithm afterward, that can be written very similarly to the explication above with a bunch of if conditions. Factorizing code this way often helps making your code more readable.

To debug one world after the other and avoid that the messages of all worlds get intermixed, you can write your debug function only if the method isSelected() returns true. It will be so only for the entity that is currently selected in the graphical interface, that is probably the world you are currently debugging. This will help breaking the difficulty in parts by debugging the situation one after the other.
In particular, it may help to print textually the state of the world each time you enter the main loop.