28
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Any valid sequence, or should it be a minimal length one? \$\endgroup\$ – Peter Taylor Jul 10 '13 at 22:33
  • \$\begingroup\$ Tiny typo: the second example shows 4 3 2 1 instead of 4 2 3 1 \$\endgroup\$ – beary605 Jul 10 '13 at 22:55
  • 4
    \$\begingroup\$ (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 :) \$\endgroup\$ – daniero Jul 11 '13 at 1:11
  • \$\begingroup\$ I wonder if anyone will post their entry from this challenge. \$\endgroup\$ – grc Jul 11 '13 at 3:35
  • \$\begingroup\$ Does the sequence have to be contiguous values? Is 2 7 5 a valid input? \$\endgroup\$ – hatchet-inactive Aug 15 '13 at 1:20

12 Answers 12

6
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Jul 11 '13 at 7:00
  • \$\begingroup\$ @PeterTaylor huh, I was wondering why you could use ^ as a variable in the fibonacci challenge ;) Thanks for the tip! \$\endgroup\$ – Volatility Jul 11 '13 at 7:05
  • \$\begingroup\$ For input 3 2 1 I get 131211 which is not correct. \$\endgroup\$ – Howard Jul 11 '13 at 8:08
  • \$\begingroup\$ @Howard got it to work now \$\endgroup\$ – Volatility Jul 11 '13 at 10:37
  • \$\begingroup\$ @Volatility The last change was a bit too much ;-) E.g. lists like 2 1 1 cannot be sorted any more. \$\endgroup\$ – Howard Jul 12 '13 at 7:54
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – WendiKidd Jul 11 '13 at 16:32
  • \$\begingroup\$ @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. \$\endgroup\$ – AJMansfield Jul 11 '13 at 16:55
  • \$\begingroup\$ @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! \$\endgroup\$ – WendiKidd Jul 11 '13 at 16:56
  • 2
    \$\begingroup\$ 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 :) \$\endgroup\$ – Bakuriu Jul 11 '13 at 19:51
  • \$\begingroup\$ @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. \$\endgroup\$ – AJMansfield Jul 12 '13 at 12:48
6
\$\begingroup\$

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

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
}/
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace sys.exit() with 1/0 (in codegolf you never care for what gets printed in stderr...). \$\endgroup\$ – Bakuriu Jul 11 '13 at 7:04
  • \$\begingroup\$ Sure, I could do print s[::-1];1/0 to shave a few chars. \$\endgroup\$ – miles Jul 11 '13 at 7:12
  • \$\begingroup\$ The BFS is very interesting, but running it with 4 2 3 1 gives 2 3 2 4, which actually is invalid. \$\endgroup\$ – daniero Jul 11 '13 at 11:21
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Gareth Jul 11 '13 at 11:26
  • \$\begingroup\$ @Gareth I have no idea! And I even checked it twice.. Oh well, nevermind then :) Nice solution, miles t. \$\endgroup\$ – daniero Jul 11 '13 at 11:30
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ [:i][::-1] -> [i-1::-1], [:u][::-1] -> [u-1::-1], saves 2 chars \$\endgroup\$ – Volatility Jul 11 '13 at 7:19
  • \$\begingroup\$ In fact, L[:i]=L[i-1::-1];L[:u]=[u-1::-1] saves another 3 chars \$\endgroup\$ – Volatility Jul 11 '13 at 7:21
  • \$\begingroup\$ @Volatility Thanks for the tips. Included. \$\endgroup\$ – Bakuriu Jul 11 '13 at 7:24
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – John Dvorak Jul 11 '13 at 4:49
  • 1
    \$\begingroup\$ 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:] \$\endgroup\$ – John Dvorak Jul 11 '13 at 5:03
  • \$\begingroup\$ 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:] \$\endgroup\$ – John Dvorak Jul 11 '13 at 5:11
  • 1
    \$\begingroup\$ Umm... you are supposed to print the entire flipping sequence, not just the end result. \$\endgroup\$ – John Dvorak Jul 11 '13 at 5:18
  • \$\begingroup\$ 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 \$\endgroup\$ – daniero Jul 11 '13 at 10:50
3
\$\begingroup\$

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);
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Does not handle non-contiguous sequences - giving incorrect results with those inputs. \$\endgroup\$ – hatchet-inactive Aug 15 '13 at 13:34
  • \$\begingroup\$ @hatchet: I'm not sure what you mean. Can you give me an example? \$\endgroup\$ – Igby Largeman Aug 15 '13 at 23:09
  • \$\begingroup\$ Given an input of 1 22, the result says to do one swap, which would result in 22 1. I think your code expects the sequence to include contiguous numbers (ex: 2 4 1 3), but doesn't expect inputs like (2 24 5 5 990). \$\endgroup\$ – hatchet-inactive Aug 15 '13 at 23:16
  • \$\begingroup\$ @hatchet: Indeed, I made no attempt to support gaps in the sequence, because that wouldn't make sense. The idea of pancake sort is to sort a stack of objects, not a group of arbitrary numbers. The number associated with each object identifies its proper position in the stack. Therefore the numbers will always begin with 1 and be contiguous. \$\endgroup\$ – Igby Largeman Aug 15 '13 at 23:53
  • \$\begingroup\$ I wasn't sure, because the question said "sequence", and in math, {1, 22} is a valid sequence, but both examples were contiguous numbers. So I asked for clarification from the OP (see comments on question). I think most of the answers here will handle gaps ok. \$\endgroup\$ – hatchet-inactive Aug 15 '13 at 23:56
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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--);
        }
    }
}
\$\endgroup\$

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.