# The Burnt Pancake Problem

This challenge is related to Flipping Pancakes.

You may have heard of pancake sorting, where a stack of pancakes is sorted by size by inserting spatula into the stack and flipping all of the pancakes above the spatula, until the pancakes are sorted smallest to largest on the plate. The burnt pancake problem is slightly different. All pancakes now have one side that is burnt, and the burnt side of each pancake must face the plate once the sorting is completed.

For example, given the following stack (size of pancake on the left. 0 meaning burnt-side down and 1 meaning burnt-side up on the right):

1 0
3 1
2 1


You may flip the whole stack to get 20 30 11, flip the top two to get 31 21 11 and flip the whole stack again to get 10 20 30, a sorted stack of burnt pancakes. This sequence of moves, flip 3, flip 2, flip 3, could be represented as 3 2 3.

The Challenge

• Given an array of pancakes sizes (not necessarily unique) and their orientations, output any valid burnt pancake sorting sequence, that is, a sequence of flips that leads to the stack of pancakes being sorted from smallest to largest with burnt sides down.
• Input and output may be any sane format with separators, but please specify which formats you use and state which end of your input format is the top of the stack (TOS).
• Flipping zero pancakes is allowed.
• Mixing separators in the input/output is allowed.

Test cases

For all of the following test cases, input is a list and output is a space-separated string, and TOS is on the left.

[[1, 0], [3, 1], [2, 1]]
"3 2 3"

[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"


As always, if anything is unclear or incorrect, please let me know in the comments. Good luck and good golfing!

# Python 2, 83

Input is expected to be the list of (size, orientation) tuples with the stack's top at the end. The output is a list of sizes to flip separated by various kinds of whitespace.

a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]

• Apparently I'm an idiot. Aug 28, 2016 at 10:37
• Is 0 in the output list allowed? Aug 28, 2016 at 10:39
• @LeakyNun Flipping 0 pancakes is eminently possible. In fact, I'm doing it right now. Aug 28, 2016 at 10:41
• @daniero The top of stack is on the right side. Aug 28, 2016 at 18:51
• @LeakyNun oh sorry, my bad Aug 28, 2016 at 20:02

## CJam (37 bytes)

q~{__$W>#)_p/(W%\M*2,f.^+(1=p_,)pW%}h  Input is an array in CJam format on stdin; output is a newline-separated list of flip lengths on stdout. The top of stack is at index 0; 0 indicates burnt side up, and 1 indicates burnt side down. Online demo ### Dissection The output is always 3n flips long, where n is the number of pancakes. First we flip the largest remaining pancake to the top; then if it's burnt side down we flip that one pancake; and then we flip it to the bottom and repeat as though the stack of pancakes were one shorter. q~ e# Parse input into array { e# Loop... __$W>#)  e#   Find 1-based index of largest element in array
_p       e#   Dup and print
/(       e#   Split into chunks that long, and pull off the first
W%       e#   Reverse the first chunk. Note that we don't flip the burnt/unburnt bit
\M*      e#   Merge the remaining chunks into a single array
2,f.^    e#   Flip *their* burnt/unburnt bits
+        e#   Concatenate, prepending the first chunk
(1=p     e#   Pull off the first (largest) element and print its burnt/unburnt bit
_,)p     e#   Print the number of remaining elements plus 1 (to account for the largest)
W%       e#   Reverse. Note that the first chunk has now been flipped twice, which is
e#   why we have left its burnt/unburnt bit alone
}h         e# ... until we get down to an empty array


# Ruby, 10195 93 bytes

Not very golfy, I just wanted to make a bogo-sort variant. It's an anonymous function that takes an array of arrays and prints random flips to stdout until the pancakes are sorted.

->a{(p r=-~rand(a.size)
a[0,r]=a[0,r].reverse.map{|x,b|[x,1-b]})while a!=a.sort||a.rassoc(1)}


You can for example assign it to f and say f.call [[1, 0], [3, 1], [2, 1]]

-5 bytes from @Jordan with the brilliant use of rassoc
-2 bytes from @Sherlock9

• You can save a few bytes by replacing a.all?{...} with !a.rassoc(1). Aug 28, 2016 at 16:51
• @Jordan Wow, that's a really brilliant! I don't think I've ever thought of using (r)assoc before, but thinking about it, it's probably useful in a lot of problems on this site -- I feel that it should go in the Ruby golfing tips post. Anyhow, thanks :) I was also able to kill another byte though the application of deMorgans law and replacing until with while. Aug 28, 2016 at 17:50
• Aug 28, 2016 at 20:23
• Since b is only ever 0 or 1, 1-b would also work and would save two bytes. Aug 31, 2016 at 3:02