The Burnt Pancake Problem

Question

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!

Answer 1

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]

Answer 2

Ruby, 101 95 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

Answer 3

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