News for hackers. Stuff that matters.
Re:Dispelling myths about the autistic programmer by thaumasiotes on Saturday July 09, 2016 @11:24PM (#12064445)
I read too hastily. Pancake sorting involves sorting pancakes by size using the pancake-flipping operation. The problem at issue was aligning them into the same orientation without regard to size, which is the "more difficult" burnt pancake problem, except that all the pancakes are the same size.

I guess for completeness, I should post the solution to the sortless burnt pancake (to me, "coin alignment") problem:

Consider a stack of coins, like top-HTTHHTTHTHTTTTTTH-bottom. The number of flips required to align it is equal to the number of transitions from tails to heads or heads to tails as you move through the stack. In the example, we can break the stack conceptually into runs of H TT HH TT H T H TTTTT H, which is 8 transitions.

1. (This number is necessary.) Two adjacent coins which differ in orientation can only be made not to differ by a flip at the position between them. A flip above or below that position in the stack reverses neither or both, which preserves their difference. Stated another way, no flip can reduce the number of transitions in the stack by more than 1.

2. (This number is sufficient.) If you move from the top of the stack down, flipping whenever a transition is encountered, you preserve the invariant that the prefix of the stack above the point you have reached is all aligned. This is one flip per transition, so one flip per transition suffices.

If the coins must be aligned to a particular direction, for example heads up, just suffix a coin of that alignment to the bottom of the stack.

There are no comments on this comment yet.