27
3
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
1Any valid sequence, or should it be a minimal length one? – Peter Taylor – 2013-07-10T22:33:48.840
Tiny typo: the second example shows
4 3 2 1
instead of4 2 3 1
– beary605 – 2013-07-10T22:55:37.3404
(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 :)
– daniero – 2013-07-11T01:11:16.590I wonder if anyone will post their entry from this challenge.
– grc – 2013-07-11T03:35:16.857Does the sequence have to be contiguous values? Is 2 7 5 a valid input? – None – 2013-08-15T01:20:08.780
@hatchet No, it doesn't; 2 7 5 is valid input. There may also be duplicate values, e.g., 2 7 5 5. – daniero – 2013-08-15T09:52:59.370
ok, that wasn't obvious from the question. I think some of the answers don't handle those non-contiguous inputs correctly. – None – 2013-08-15T20:44:07.133