23
\$\begingroup\$

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!

\$\endgroup\$
7
\$\begingroup\$

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]
\$\endgroup\$
  • 2
    \$\begingroup\$ Apparently I'm an idiot. \$\endgroup\$ – Leaky Nun Aug 28 '16 at 10:37
  • \$\begingroup\$ Is 0 in the output list allowed? \$\endgroup\$ – Leaky Nun Aug 28 '16 at 10:39
  • 19
    \$\begingroup\$ @LeakyNun Flipping 0 pancakes is eminently possible. In fact, I'm doing it right now. \$\endgroup\$ – feersum Aug 28 '16 at 10:41
  • \$\begingroup\$ @daniero The top of stack is on the right side. \$\endgroup\$ – Leaky Nun Aug 28 '16 at 18:51
  • \$\begingroup\$ @LeakyNun oh sorry, my bad \$\endgroup\$ – daniero Aug 28 '16 at 20:02
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a few bytes by replacing a.all?{...} with !a.rassoc(1). \$\endgroup\$ – Jordan Aug 28 '16 at 16:51
  • \$\begingroup\$ @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. \$\endgroup\$ – daniero Aug 28 '16 at 17:50
  • 1
    \$\begingroup\$ Good idea: codegolf.stackexchange.com/questions/363/… \$\endgroup\$ – Jordan Aug 28 '16 at 20:23
  • \$\begingroup\$ Since b is only ever 0 or 1, 1-b would also work and would save two bytes. \$\endgroup\$ – Sherlock9 Aug 31 '16 at 3:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.