# Flipping pancakes

In pancake sorting the only allowed operation is to reverse the elements of some prefix of the sequence. Or, think of a stack of pancakes: We insert a spatula somewhere in the stack and flip all the pancakes above the spatula.

For example, the sequence 6 5 4 1 2 3 can be sorted by first flipping the first 6 elements (the whole sequence), yielding the intermediate result 3 2 1 4 5 6, and then flipping the first 3 elements, arriving at 1 2 3 4 5 6.

As there is only one operation, the whole sorting process can be described by a sequence of integers, where each integer is the number of elements/pancakes to include pr flip. For the example above, the sorting sequence would be 6 3.

Another example: 4 2 3 1 can be sorted with 4 2 3 2. Here's the intermediate results:

         4 2 3 1
flip 4:  1 3 2 4
flip 2:  3 1 2 4
flip 3:  2 1 3 4
flip 2:  1 2 3 4


Write a program which takes a list of integers and prints a valid pancake sorting sequence.

The list to sort can either be a space separated list from stdin, or command line arguments. Print the list however it is convenient, as long as it's somewhat readable.

This is codegolf!

### Edit:

As I said in the comments, you don't need to optimize the output (finding the shortest sequence is NP-hard). However, I just realized that a cheap solution would be to throw out random numbers until you get the desired result (a [new?] type of bogosort). None of the answers so far have done this, so I now declare that your algorithm should not rely on any (pseudo-)randomness.

While you're all kicking yourselves, here's a bogopancakesort variant in Ruby 2.0 (60 characters), to rub it in:

a=$*.map &:to_i a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort  • Any valid sequence, or should it be a minimal length one? Jul 10, 2013 at 22:33 • Tiny typo: the second example shows 4 3 2 1 instead of 4 2 3 1 Jul 10, 2013 at 22:55 • (My internet went down as I tried to edit this, so I post it again) @PeterTaylor I was tempted to include some sort of optimization into this, but chose not to. Finding the length of the minimal sequence is actually NP-hard, while the simplest, straight-forward algorithm can find a solution that at most will be 2n long. I don't really know how I would judge this as a code-challenge/optimal output thing, and I just like plain codegolf more :) Jul 11, 2013 at 1:11 • I wonder if anyone will post their entry from this challenge. – grc Jul 11, 2013 at 3:35 • Does the sequence have to be contiguous values? Is 2 7 5 a valid input? – user8865 Aug 15, 2013 at 1:20 ## 11 Answers ## Python, 91 90 chars L=map(int,raw_input().split()) while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]  Flip the biggest pancake to the top, then flip the whole stack. Remove the biggest pancake from the bottom and repeat. i is the index of the biggest pancake. L=L[:i:-1]+L[:i] flips i+1 pancakes, flips len(L) pancakes, then drops the last pancake. • I thought you were only allowed to make flips. (That is, I didn't think you could drop pancakes from the stack). Did I misunderstand the rules? Hmm. goes to read wiki page again Regardless, nice job :) Less than 100 characters is pretty amazing to me! Jul 11, 2013 at 16:32 • @WendiKidd Actually, what he means is that after flipping the biggest one to the bottom, he's just ignoring it and concerning himself with the pancakes on top of it. Jul 11, 2013 at 16:55 • @AJMansfield Ah, I see! Thanks, that makes sense. I can't read the code (I'm too new to Python) so I misunderstood the explanation :) Thanks! Jul 11, 2013 at 16:56 • Pretty much an evolution of what I wrote before. I didn't think of removing elements because in the beginning I had to check for correctness of the output(i.e. is the list sorted afterwards?). By the way: I believe removing the comma from the print wont render the output unreadable(1 byte saved :) Jul 11, 2013 at 19:51 • @WendiKidd actually, on further inspection, it does indeed remove the pancakes; it only needs to figure out what the sequence of flips is, not actually sort the array. Jul 12, 2013 at 12:48 ## GolfScript, 34 / 21 chars (Thanks @PeterTaylor for chopping 4 chars off) ~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,  Online test A shorter, 21 character version works for lists with unique items only ~].${.2$?.p)p.@\-+}/,  Online test Both versions produce sub-optimal solutions. Explanation for the shorter solution: ~] # read input from stdin .$         # produce a sorted copy from lowest to highest
{          # iterate over the sorted list
.2$? # grab the index of the element .p # print the index )p # increment and print the index .@\-+ # move the element to the front }/ , # leave the length of the list on the stack # this flips the reverse sorted list to become sorted  This uses a different algorithm to most of the others posted. Basically it grabs the smallest element of the list, and with two flips moves it to the front, preserving the other elements' order. To move the nth element to the front: 1 2 3 4 5 6 7 # let's move the 3rd (0-based) element to the front # flip the first 3 elements 3 2 1 4 5 6 7 # flip the first 3+1 elements 4 1 2 3 5 6 7  It repeats this operation for each element in order, and ends up with a reverse sorted list. It then flips the whole list to leave it fully sorted. In fact the algorithm is a variation of a 90-char Python solution (my own, of course): d=map(int,raw_input().split());i=0 while d:n=d.index(max(d));d.pop(n);print n+i,n-~i,;i+=1  • I see you haven't come across one of GolfScript's useful quirks: you can use any token as a variable. You're not using & anywhere, so you should be able to replace s while & and remove the whitespace. Jul 11, 2013 at 7:00 • @PeterTaylor huh, I was wondering why you could use ^ as a variable in the fibonacci challenge ;) Thanks for the tip! Jul 11, 2013 at 7:05 • For input 3 2 1 I get 131211 which is not correct. Jul 11, 2013 at 8:08 • @Howard got it to work now Jul 11, 2013 at 10:37 • @Volatility The last change was a bit too much ;-) E.g. lists like 2 1 1 cannot be sorted any more. Jul 12, 2013 at 7:54 ## Ruby 1.9 - 10988 79 characters Much more compact version based on Keith's great python solution: a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}  Original version: a=$*.map &:to_i
a.size.downto(2){|l|[n=a.index(a[0,l].max)+1,l].map{|v|v>1&&n<l&&p(v);a[0,v]=a[0,v].reverse}}


If you don't care about spurious operations (reversing stacks of size 1, or reversing the same stack twice in a row) you can make it a bit shorter (96 chars):

a=$*.map &:to_i a.size.downto(2){|l|[a.index(a[0,l].max)+1,l].map{|v|p v;a[0,v]=a[0,v].reverse}}  Takes the unsorted list as command-line args. Example usage: >pc.rb 4 2 3 1 4 2 3 2  ### GolfScript, 31 29 characters ~].${1$?).p.2$.,p>-1%\@<+)}%,


Another GolfScript solution, can also be tested online.

Previous version:

~].$-1%{1$?).2$>-1%@2$<+.,\);}/


How does it work: it flips the largest item to the top and then to the last place in the list. Since it is now in the correct position we can remove it from the list.

~]         # Convert STDIN (space separated numbers) to array
.$-1% # Make a sorted copy (largest to smallest) { # Iterate over this copy 1$?)     # Get index of item (i.e. largest item) in the remaining list,
# due to ) the index starts with one
.        # copy (i.e. index stays there for output)
2$> # take the rest of the list... -1% # ... and reverse it @2$<     # then take the beginning of the list
+        # and join both.
# Note: these operations do both flips together, i.e.
# flip the largest item to front and then reverse the complete stack
.,       # Take the length of the list for output
\);      # Remove last item from list
}/


## Perl, 103 100 characters

Expects input on the command line.

for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1) {$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}  The solutions it prints are decidedly sub-optimal. (I had a program with much nicer output about 24 characters ago....) The logic is kind of interesting. It starts by cataloguing the index of each item, were it in sorted order. It then iterates through this catalog from right to left. So applying a flip involves adjusting indexes below the cutoff value, instead of actually moving values around. After some finagling I also managed to save a few characters by doing both flips per iteration simultaneously. ## Python 2 (254) Simple BFS-search, some stuff is inlined, probably could be compressed more without changing the search style. Hopefully this shows maybe how to start golfing a bit (too much to be in a simple comment). Use: python script.py 4 2 3 1  (2 spaces = tab) import sys t=tuple i=t(map(int,sys.argv[1:])) g=t(range(1,len(i)+1)) q=[i] p={} l={} while q: c=q.pop(0) for m in g: n=c[:m][::-1]+c[m:] if n==g: s=[m] while c!=i:s+=[l[c]];c=p[c] print s[::-1] sys.exit() elif n not in p:q+=[n];p[n]=c;l[n]=m  • You can replace sys.exit() with 1/0 (in codegolf you never care for what gets printed in stderr...). Jul 11, 2013 at 7:04 • Sure, I could do print s[::-1];1/0 to shave a few chars. Jul 11, 2013 at 7:12 • The BFS is very interesting, but running it with 4 2 3 1 gives 2 3 2 4, which actually is invalid. Jul 11, 2013 at 11:21 • @daniero How is that output invalid? 4 2 3 1 -> 2 4 3 1 -> 3 4 2 1 -> 4 3 2 1 -> 1 2 3 4 Jul 11, 2013 at 11:26 • @Gareth I have no idea! And I even checked it twice.. Oh well, nevermind then :) Nice solution, miles t. Jul 11, 2013 at 11:30 Python2: 120 L=map(int,raw_input().split()) u=len(L) while u:i=L.index(max(L[:u]))+1;L[:i]=L[i-1::-1];L[:u]=L[u-1::-1];print i,u;u-=1  It's not efficient: it wont find the best sorting sequence, and the given sequence can even contain no-ops(i.e. flipping only the first element), nevertheless the output is valid. The output is given in the form: n_1 n_2 n_3 n_4 n_5 n_6 ...  Which should be read as the sequence of flips: n_1 n_2 n_3 n_4 n_5 n_6 .... If you want to obtain an output like: n_1 n_2 n_3 n_4 n_5 n_6 ... Simply add a comma in the print statement. • [:i][::-1] -> [i-1::-1], [:u][::-1] -> [u-1::-1], saves 2 chars Jul 11, 2013 at 7:19 • In fact, L[:i]=L[i-1::-1];L[:u]=[u-1::-1] saves another 3 chars Jul 11, 2013 at 7:21 • @Volatility Thanks for the tips. Included. Jul 11, 2013 at 7:24 ## Python - 282 characters import sys s=sys.argv[1] l=s.split() p=[] for c in l: p.append(int(c)) m=sys.maxint n=0 while(n==(len(p)-1)): i=x=g=0 for c in p: if c>g and c<m: g=c x=i i+=1 m=g x+=1 t=p[:x] b=p[x:] t=t[::-1] p=t+b a=len(p)-n; t=p[:a] b=p[a:] t=t[::-1] p=t+b print p n+=1  My first ever code golf; I'm under no illusions I'll win, but I had a lot of fun. Giving everything one-character names sure makes it frightening to read, let me tell you! This is run from the command line, sample implementation below: Python PancakeSort.py "4 2 3 1" [1, 3, 2, 4] [2, 1, 3, 4] [1, 2, 3, 4]  There's nothing particularly special or inventive about the way I've gone about this, but the FAQ suggests posting a non-golfed version for interested readers, so I've done so below: import sys pancakesStr = sys.argv[1] pancakesSplit = pancakesStr.split() pancakesAr = [] for pancake in pancakesSplit: pancakesAr.append(int(pancake)) smallestSorted = sys.maxint numSorts = 0 while(numSorts < (len(pancakesAr) - 1)): i = 0 biggestIndex = 0 biggest = 0 for pancake in pancakesAr: if ((pancake > biggest) and (pancake < smallestSorted)): biggest = pancake biggestIndex = i i += 1 smallestSorted = biggest #you've found the next biggest to sort; save it off. biggestIndex += 1 #we want the biggestIndex to be in the top list, so +1. top = pancakesAr[:biggestIndex] bottom = pancakesAr[biggestIndex:] top = top[::-1] #reverse top to move highest unsorted number to first position (flip 1) pancakesAr = top + bottom #reconstruct stack alreadySortedIndex = len(pancakesAr) - numSorts; top = pancakesAr[:alreadySortedIndex] bottom = pancakesAr[alreadySortedIndex:] top = top[::-1] #reverse new top to move highest unsorted number to the bottom position on the unsorted list (flip 2) pancakesAr = top + bottom #reconstruct list print pancakesAr #print after each flip numSorts += 1 print "Sort completed in " + str(numSorts) + " flips. Final stack: " print pancakesAr  The basic algorithm I used is the one mentioned in the wiki article linked in the question: The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes. • Some tips for golfing: four spaces for indentation is wasteful. Better: use one space; even better: combine tabs and spaces to cut back even more. Jul 11, 2013 at 4:49 • t=p[:x] t=t[::-1] (16+indentation) can be reduced to t=p[:x][::-1] (13), or even t=p[x-1::-1] (12). Inline everything you can: p=p[x-1::-1]+p[x:] Jul 11, 2013 at 5:03 • Use negative indices to count from the back. len(a)-n becomes -n; p=p[-n-1::-1]+p[-n:]. Further golf by using the right operations: p=p[~n::-1]+p[-n:] Jul 11, 2013 at 5:11 • Umm... you are supposed to print the entire flipping sequence, not just the end result. Jul 11, 2013 at 5:18 • What Jan Dvorak said. Welcome to codegolf by the way. You can easily cut the character count to a half by some simple measures; some of them has been mentioned. Also, intermediate variables are no good. List comprehension is nice. But if you're using sys.argv you may as well let each number of the input be an argument, then map(int,sys.argv[1:]) does what your 6 first lines does now. i=x=g=0 works, but you should cut the amount of variables anyways. I'll give you one thing though: This is the one python entry of which I understand the least :D Jul 11, 2013 at 10:50 # Haskell, 72 71 bytes h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a) h e=e  Try it online! Finds the maximum, flips it to the back and recursively sorts the remaining list. Edit: -1 byte thanks to BMO # Perl 5.10 (or higher), 66 bytes Includes +3 for -n The use 5.10.0 to bring the language to level perl 5.10 is considered free #!/usr/bin/perl -n use 5.10.0;$'>=$&or$.=s/(\S+) \G(\S+)/$2$1/*say"$. 2$."while\$.++,/\S+ /g


Run with the input as one line on STDIN:

flop.pl <<< "1 8 3 -5 6"


Sorts the list by repeatedly finding any inversion, flipping it to the front then flipping the inversion and flipping everything back to its old position. And that is equivalent to swapping the inversion so I don't need to reverse (which is awkward on strings since it would reverse the digits of the values converting e.g. 12 to 21)

C# - 229

using System;using System.Linq;class P{static void Main(string[] a){
var n=a.ToList();Action<int>d=z=>{Console.Write(z+" ");n.Reverse(0,z);};
int c=n.Count;foreach(var s in n.OrderBy(x=>0-int.Parse(x))){
d(n.IndexOf(s)+1);d(c--);}}}


using System;
using System.Linq;
class P {
static void Main(string[] a) {
var n = a.ToList();
Action<int> d = z => { Console.Write(z + " "); n.Reverse(0, z); };
int c = n.Count;
foreach (var s in n.OrderBy(x => 0 - int.Parse(x))) {
d(n.IndexOf(s) + 1); d(c--);
}
}
}