Flipping pancakes

Question

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

The task:

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

Answer 1

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

Answer 2

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.

Answer 3

Ruby 1.9 - 109 88 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

Answer 4

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
}/

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

C# - 264 259 252 237 characters

Uses the simplest algorithm and produces correct output without redundant flips. Could shave 7 chars off if I allowed it to include 1's (non-flips) in the output, but that's ugly.

I resorted to using goto for maximum golfage. Also saved some chars by allowing it to perform non-flips (but not print them).

Latest improvement: keeping input array as strings instead of converting to ints.

using System.Linq;class P{static void Main(string[]a){var n=a.ToList();for(int p
=n.Count;p>0;p--){int i=n.IndexOf(p+"")+1;if(i<p){f:if(i>1)System.Console.Write
(i);n=n.Take(i).Reverse().Concat(n.Skip(i)).ToList();if(i!=p){i=p;goto f;}}}}}

Ungolfed:

using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var numbers = args.ToList();

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake+"") + 1;
            if (index < pancake)
            {
                flip:

                if (index > 1)
                    System.Console.Write(index);

                numbers = numbers.Take(index)
                                 .Reverse()
                                 .Concat(numbers.Skip(index))
                                 .ToList();

                if (index != pancake)
                {
                    index = pancake;
                    goto flip;
                }
            }
        }
    }
}

Here's my initial solution, ungolfed (264 chars golfed):

using System.Linq;
using System;

class Program
{
    static void Main(string[] args)
    {
        var numbers = args.Select(int.Parse).ToList();

        Action<int> Flip = howMany =>
        {
            Console.Write(howMany);
            numbers = numbers.Take(howMany)
                             .Reverse()
                             .Concat(numbers.Skip(howMany))
                             .ToList();
        };

        for (int pancake = numbers.Count; pancake > 0; pancake--)
        {
            int index = numbers.IndexOf(pancake) + 1;
            if (index < pancake)
            {
                if (index > 1)
                    Flip(index);
                Flip(pancake);
            }
        }
    }
}

Answer 10

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

Answer 11

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)

Answer 12

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--);}}}

readable version

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--);
        }
    }
}