Dans le tri des crêpes, la seule opération autorisée consiste à inverser les éléments d'un préfixe de la séquence. Ou, pensez à une pile de crêpes: nous insérons une spatule quelque part dans la pile et retournons toutes les crêpes au-dessus de la spatule.

Par exemple, la séquence 6 5 4 1 2 3peut être triée en retournant d'abord les premiers 6éléments (la séquence entière), donnant le résultat intermédiaire 3 2 1 4 5 6, puis en retournant les premiers 3éléments, pour arriver à 1 2 3 4 5 6.

Comme il n'y a qu'une seule opération, l'ensemble du processus de tri peut être décrit par une séquence d'entiers, où chaque entier est le nombre d'éléments / crêpes à inclure pr flip. Pour l'exemple ci-dessus, la séquence de tri serait 6 3.

Autre exemple: 4 2 3 1peut être trié avec 4 2 3 2. Voici les résultats intermédiaires:

         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

La tâche:

Écrivez un programme qui prend une liste d'entiers et imprime une séquence de tri de crêpes valide.

La liste à trier peut être soit une liste séparée par des espaces de stdin, soit des arguments de ligne de commande. Imprimez la liste mais c'est pratique, tant qu'elle est quelque peu lisible.

C'est du codegolf!

Modifier:

Comme je l'ai dit dans les commentaires, vous n'avez pas besoin d'optimiser la sortie (trouver la séquence la plus courte est NP-difficile ). Cependant , je viens de réaliser qu'une solution bon marché serait de jeter des nombres aléatoires jusqu'à ce que vous obteniez le résultat souhaité (un [nouveau?] Type de bogosort). Aucune des réponses n'a jusqu'à présent fait cela, donc je déclare maintenant que votre algorithme ne devrait pas s'appuyer sur un (pseudo) hasard .

Pendant que vous vous frappez tous, voici une variante de bogopancakesort dans Ruby 2.0 (60 caractères), pour le frotter:

a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort

GolfScript, 34/21 caractères

(Merci @PeterTaylor d'avoir coupé 4 caractères)

~].{,,{1$=}$\}2*${.2$?.p)p.@\-+}/,

Test en ligne

Une version plus courte de 21 caractères fonctionne uniquement pour les listes contenant des éléments uniques

~].${.2$?.p)p.@\-+}/,

Test en ligne

Les deux versions produisent des solutions sous-optimales.

Explication de la solution plus courte:

~]         # 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

Cela utilise un algorithme différent de la plupart des autres publiés. Fondamentalement, il saisit le plus petit élément de la liste, et avec deux flips le déplace vers l'avant, préservant l'ordre des autres éléments.

Pour déplacer le nième élément vers l'avant:

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

Il répète cette opération pour chaque élément dans l'ordre et se termine par une liste triée inversée. Il retourne ensuite la liste entière pour la laisser entièrement triée.

En fait, l'algorithme est une variation d'une solution Python de 90 caractères (la mienne, bien sûr):

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

Python, 91 90 caractères

L=map(int,raw_input().split())
while L:i=L.index(max(L));print-~i,len(L),;L=L[:i:-1]+L[:i]

Retournez la plus grosse crêpe vers le haut, puis retournez toute la pile. Retirez la plus grosse crêpe du bas et répétez.

iest l'indice de la plus grosse crêpe. L=L[:i:-1]+L[:i]retourne les i+1crêpes, retourne les len(L)crêpes, puis laisse tomber la dernière crêpe.

Ruby 1.9 - 109 88 79 caractères

Version beaucoup plus compacte basée sur l'excellente solution python de Keith:

a=$*.map &:to_i;$*.map{p v=a.index(a.max)+1,a.size;a=a[v..-1].reverse+a[0,v-1]}

Version originale:

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

Si vous ne vous souciez pas des opérations parasites (inversion de piles de taille 1, ou inversion de la même pile deux fois de suite), vous pouvez la raccourcir un peu (96 caractères):

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

Prend la liste non triée comme arguments de ligne de commande. Exemple d'utilisation:

>pc.rb 4 2 3 1
4
2
3
2

GolfScript, 31 29 caractères

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

Une autre solution GolfScript, peut également être testée en ligne .

La version précédente:

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

Comment ça marche: il retourne le plus grand élément vers le haut, puis à la dernière place de la liste. Puisqu'il est maintenant dans la bonne position, nous pouvons le supprimer de la liste.

~]         # 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 caractères

Attend une entrée sur la ligne de commande.

for(@n=sort{$ARGV[$a]<=>$ARGV[$b]}0..$#ARGV;@n;say$i+1,$/,@n+1)
{$i=pop@n;$_=@n-$_-($_<=$i&&$i)for@n}

Les solutions qu'il imprime sont décidément sous-optimales. (J'avais un programme avec une sortie beaucoup plus agréable il y a environ 24 caractères ....)

La logique est plutôt intéressante. Il commence par cataloguer l'index de chaque élément, s'il était trié. Il parcourt ensuite ce catalogue de droite à gauche. Donc, appliquer un retournement implique d'ajuster les index en dessous de la valeur de coupure, au lieu de déplacer réellement les valeurs. Après quelques finagling, j'ai également réussi à sauver quelques personnages en faisant les deux flips par itération simultanément.

Python 2 (254)

Recherche BFS simple, certaines choses sont en ligne, pourraient probablement être compressées davantage sans changer le style de recherche. Espérons que cela montre peut-être comment commencer à jouer au golf un peu (trop pour être dans un simple commentaire).

Utilisation:

python script.py 4 2 3 1

(2 espaces = tabulation)

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

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

Ce n'est pas efficace: il ne trouvera pas la meilleure séquence de tri, et la séquence donnée peut même contenir des non-opérations (c'est-à-dire retourner uniquement le premier élément), néanmoins la sortie est valide.

La sortie est donnée sous la forme:

n_1 n_2
n_3 n_4
n_5 n_6
...

Ce qui doit être lu comme la séquence de flips: n_1 n_2 n_3 n_4 n_5 n_6 .... Si vous souhaitez obtenir une sortie comme:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Ajoutez simplement une virgule dans la printdéclaration.

Python - 282 caractères

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

Mon tout premier golf à code; Je ne me fais aucune illusion, je vais gagner , mais je me suis beaucoup amusé. Donner tout les noms à un caractère rend la lecture effrayante, laissez-moi vous dire! Ceci est exécuté à partir de la ligne de commande, exemple d'implémentation ci-dessous:

Python PancakeSort.py "4 2 3 1"
[1, 3, 2, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]

Il n'y a rien de particulièrement spécial ou d'inventif dans la façon dont j'ai procédé, mais la FAQ suggère de publier une version non-golfée pour les lecteurs intéressés, alors je l'ai fait ci-dessous:

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

L'algorithme de base que j'ai utilisé est celui mentionné dans l' article wiki lié à la question :

L'algorithme de tri des crêpes le plus simple nécessite au plus 2n − 3 flips. Dans cet algorithme, une variante du tri de sélection, nous amenons la plus grande crêpe non encore triée vers le haut avec un flip, puis la ramène à sa position finale avec un autre, puis répétons cela pour les crêpes restantes.

C # - 264 259 252 237 caractères

Utilise l'algorithme le plus simple et produit une sortie correcte sans retournements redondants. Pourrait raser 7 caractères si je l'autorisais à inclure des 1 (non-flips) dans la sortie, mais c'est moche.

J'ai eu recours à goto pour un maximum de golf. Également enregistré certains caractères en lui permettant d'effectuer des non-flips (mais pas de les imprimer).

Dernière amélioration: conserver le tableau d'entrée sous forme de chaînes au lieu de le convertir en pouces.

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

Non golfé:

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

Voici ma solution initiale, non golfée (264 caractères golfés):

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

Haskell , 72 71 octets

h s|(a,x:b)<-span(<maximum s)s=map length[x:a,s]++h(reverse b++a)
h e=e

Essayez-le en ligne! Recherche le maximum, le retourne à l'arrière et trie récursivement la liste restante.

Edit: -1 octet grâce à BMO

Perl 5.10 (ou supérieur), 66 octets

Comprend +3pour -n l' use 5.10.0apporter la langue au niveau perl 5.10 est considéré comme gratuit

#!/usr/bin/perl -n
use 5.10.0;
$'>=$&or$.=s/(\S+) \G(\S+)/$2 $1/*say"$. 2 $."while$.++,/\S+ /g

Exécutez avec l'entrée en une seule ligne sur STDIN:

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

Trie la liste en trouvant à plusieurs reprises toute inversion, en la retournant vers l'avant, puis en retournant l'inversion et en retournant tout à son ancienne position. Et cela équivaut à permuter l'inversion, donc je n'ai pas besoin d'inverser (ce qui est gênant sur les chaînes car cela inverserait les chiffres des valeurs converties, par exemple 12en 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--);}}}

version lisible

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