Voltear panqueques

27

En la clasificación de panqueques, la única operación permitida es invertir los elementos de algún prefijo de la secuencia. O piense en una pila de panqueques: insertamos una espátula en algún lugar de la pila y volteamos todos los panqueques por encima de la espátula.

Por ejemplo, la secuencia 6 5 4 1 2 3se puede ordenar primero volteando los primeros 6elementos (la secuencia completa), obteniendo el resultado intermedio 3 2 1 4 5 6, y luego volteando los primeros 3elementos, llegando a 1 2 3 4 5 6.

Como solo hay una operación, todo el proceso de clasificación se puede describir mediante una secuencia de números enteros, donde cada número entero es el número de elementos / panqueques para incluir pr flip. Para el ejemplo anterior, la secuencia de clasificación sería 6 3.

Otro ejemplo: 4 2 3 1se puede ordenar con 4 2 3 2. Aquí están los resultados intermedios:

         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 tarea:

Escriba un programa que tome una lista de enteros e imprima una secuencia de clasificación de panqueques válida.

La lista para ordenar puede ser una lista separada por espacios de stdin o argumentos de línea de comando. Imprima la lista, sin embargo, es conveniente, siempre que sea algo legible.

¡Esto es codegolf!

Editar:

Como dije en los comentarios, no es necesario optimizar la salida (encontrar la secuencia más corta es NP-hard ). Sin embargo , me di cuenta de que una solución barata sería arrojar números aleatorios hasta obtener el resultado deseado (¿un [nuevo?] Tipo de bogosort). Ninguna de las respuestas hasta ahora ha hecho esto, por lo que ahora declaro que su algoritmo no debe basarse en ninguna (pseudo-) aleatoriedad .

Mientras todos se patean, aquí hay una variante bogopancakesortort en Ruby 2.0 (60 caracteres), para frotarlo:

a=$*.map &:to_i
a=a[0,p(v=rand(a.size)+1)].reverse+a[v..-1]while a!=a.sort
daniero
fuente
1
¿Alguna secuencia válida, o debería ser de longitud mínima?
Peter Taylor
Pequeño error tipográfico: el segundo ejemplo se muestra en 4 3 2 1lugar de4 2 3 1
beary605
44
(Mi Internet se cayó cuando intenté editar esto, así que lo publiqué nuevamente) @PeterTaylor Estuve tentado de incluir algún tipo de optimización en esto, pero decidí no hacerlo. Encontrar la longitud de la secuencia mínima es en realidad NP-difícil , mientras que el algoritmo más simple y directo puede encontrar una solución que a lo sumo tendrá una longitud de 2n. Realmente no sé cómo juzgaría esto como un desafío de código / salida óptima, y ​​simplemente me gusta más codegolf simple :)
daniero
Me pregunto si alguien publicará su entrada de este desafío .
grc
¿La secuencia tiene que ser valores contiguos? ¿Es 2 7 5 una entrada válida?

Respuestas:

6

GolfScript, 34/21 caracteres

(Gracias @PeterTaylor por cortar 4 caracteres)

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

Prueba en línea

Una versión más corta de 21 caracteres funciona solo para listas con elementos únicos

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

Prueba en línea

Ambas versiones producen soluciones subóptimas.


Explicación para la solución más corta:

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

Esto usa un algoritmo diferente al de la mayoría de los otros publicados. Básicamente, toma el elemento más pequeño de la lista, y con dos vueltas lo mueve al frente, preservando el orden de los otros elementos.

Para mover el enésimo elemento al frente:

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

Repite esta operación para cada elemento en orden, y termina con una lista ordenada inversa. Luego voltea toda la lista para dejarla completamente ordenada.


De hecho, el algoritmo es una variación de una solución Python de 90 caracteres (la mía, por supuesto):

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
Volatilidad
fuente
2
Veo que no te has encontrado con una de las peculiaridades útiles de GolfScript: puedes usar cualquier token como variable. No se está usando &en cualquier lugar, por lo que debe ser capaz de reemplazar smientras &y quitar el espacio en blanco.
Peter Taylor
@PeterTaylor eh, me preguntaba por qué podría usar ^como variable en el desafío de Fibonacci;) ¡Gracias por el consejo!
Volatilidad
Para la entrada 3 2 1obtengo lo 131211que no es correcto.
Howard
@Howard lo puso a trabajar ahora
Volatilidad
@Volatility El último cambio fue demasiado ;-) Por ejemplo, las listas como 2 1 1ya no se pueden ordenar.
Howard
11

Python, 91 90 caracteres

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

Voltea el panqueque más grande hacia arriba, luego voltea toda la pila. Retire el panqueque más grande del fondo y repita.

ies el índice del panqueque más grande. L=L[:i:-1]+L[:i]voltea los i+1panqueques, voltea los len(L)panqueques y luego suelta el último panqueque.

Keith Randall
fuente
1
Pensé que solo se te permitía hacer volteretas. (Es decir, no pensé que podría dejar caer panqueques de la pila). ¿Entendí mal las reglas? Hmm va a leer la página wiki de nuevo Independientemente, buen trabajo :) ¡Menos de 100 caracteres es bastante sorprendente para mí!
WendiKidd
@WendiKidd En realidad, lo que quiere decir es que después de tirar el más grande al fondo, simplemente lo ignora y se preocupa con los panqueques encima.
AJMansfield
@AJMansfield Ah, ya veo! Gracias, eso tiene sentido. No puedo leer el código (soy demasiado nuevo para Python), así que no entendí la explicación :) ¡Gracias!
WendiKidd
2
Prácticamente una evolución de lo que escribí antes. No pensé en eliminar elementos porque al principio tuve que verificar la corrección de la salida (es decir, ¿se ordena la lista después?). Por cierto: creo que quitar la coma de la print
ventana no hará
@WendiKidd en realidad, en una inspección más profunda, elimina los panqueques; solo necesita descubrir cuál es la secuencia de volteos, no ordenar realmente la matriz.
AJMansfield
6

Ruby 1.9 - 109 88 79 caracteres

Versión mucho más compacta basada en la gran solución de 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]}

Versión original:

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 no le interesan las operaciones espurias (invertir pilas de tamaño 1 o invertir la misma pila dos veces seguidas), puede hacerlo un poco más corto (96 caracteres):

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

Toma la lista sin clasificar como argumentos de línea de comandos. Ejemplo de uso:

>pc.rb 4 2 3 1
4
2
3
2
Paul Prestidge
fuente
6

GolfScript, 31 29 caracteres

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

Otra solución de GolfScript, también se puede probar en línea .

Versión previa:

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

Cómo funciona: voltea el elemento más grande al principio y luego al último lugar de la lista. Como ahora está en la posición correcta, podemos eliminarlo de la lista.

~]         # 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
}/
Howard
fuente
4

Perl, 103100 caracteres

Espera entrada en la línea de comando.

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

Las soluciones que imprime son decididamente subóptimas. (Tenía un programa con una salida mucho más agradable hace unos 24 caracteres ...)

La lógica es algo interesante. Comienza catalogando el índice de cada elemento, si estuviera ordenado. Luego recorre este catálogo de derecha a izquierda. Por lo tanto, aplicar un giro implica ajustar los índices por debajo del valor de corte, en lugar de mover los valores. Después de un poco de determinación, también logré guardar algunos personajes haciendo ambas vueltas por iteración simultáneamente.

caja de pan
fuente
3

Pitón 2 (254)

Búsqueda simple de BFS, algunas cosas están en línea, probablemente podrían comprimirse más sin cambiar el estilo de búsqueda. Esperemos que esto muestre tal vez cómo comenzar a jugar al golf un poco (demasiado para ser un simple comentario).

Utilizar:

python script.py 4 2 3 1

(2 espacios = pestaña)

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
millas
fuente
1
Puede reemplazar sys.exit()con 1/0(en codegolf nunca le importa lo que se imprime en stderr ...).
Bakuriu
Claro, podría print s[::-1];1/0afeitarme algunos caracteres.
millas
El BFS es muy interesante, pero ejecutarlo con 4 2 3 1give 2 3 2 4, que en realidad no es válido.
daniero
1
@daniero ¿Cómo es que la salida no es válida? 4 2 3 1-> 2 4 3 1-> 3 4 2 1-> 4 3 2 1->1 2 3 4
Gareth
@Gareth no tengo idea! E incluso lo comprobé dos veces ... Oh, bueno, no importa entonces :) Buena solución, millas t.
daniero
3

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

No es eficiente: no encontrará la mejor secuencia de clasificación, y la secuencia dada puede contener incluso no-ops (es decir, voltear solo el primer elemento), sin embargo, la salida es válida.

La salida se da en la forma:

n_1 n_2
n_3 n_4
n_5 n_6
...

Que debe ser leída como la secuencia de lanzamientos: n_1 n_2 n_3 n_4 n_5 n_6 .... Si desea obtener una salida como:

n_1 n_2 n_3 n_4 n_5 n_6 ...

Simplemente agregue una coma en la printdeclaración.

Bakuriu
fuente
[:i][::-1]-> [i-1::-1], [:u][::-1]-> [u-1::-1], ahorra 2 caracteres
Volatilidad
De hecho, L[:i]=L[i-1::-1];L[:u]=[u-1::-1]ahorra otros 3 caracteres
Volatility
@Volatility Gracias por los consejos. Incluido.
Bakuriu
3

Python - 282 caracteres

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

Mi primer código de golf; No tengo ilusiones de que gane , pero me divertí mucho. Dar todos los nombres de un carácter seguro hace que sea aterrador de leer, ¡déjame decirte! Esto se ejecuta desde la línea de comandos, ejemplo de implementación a continuación:

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

No hay nada particularmente especial o inventivo sobre la forma en que me he ocupado de esto, pero las preguntas frecuentes sugieren publicar una versión sin golf para los lectores interesados, así que lo he hecho a continuación:

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

El algoritmo básico que utilicé es el mencionado en el artículo wiki vinculado en la pregunta :

El algoritmo de clasificación de panqueques más simple requiere como máximo 2n − 3 vueltas. En este algoritmo, una variación del tipo de selección, llevamos el panqueque más grande que aún no está ordenado a la parte superior con una sola vuelta, y luego lo llevamos a su posición final con uno más, luego repetimos esto para los panqueques restantes.

WendiKidd
fuente
1
Algunos consejos para jugar al golf: cuatro espacios para la sangría es un desperdicio. Mejor: use un espacio; aún mejor: combine pestañas y espacios para recortar aún más.
John Dvorak
1
t=p[:x] t=t[::-1](16 + sangría) se puede reducir a t=p[:x][::-1](13), o incluso t=p[x-1::-1](12). En línea todo lo que pueda:p=p[x-1::-1]+p[x:]
John Dvorak
Use índices negativos para contar desde atrás. len(a)-nse convierte -n; p=p[-n-1::-1]+p[-n:]. Más golf utilizando las operaciones correctas:p=p[~n::-1]+p[-n:]
John Dvorak
1
Umm ... se supone que debes imprimir toda la secuencia de volteo, no solo el resultado final.
John Dvorak
Lo que dijo Jan Dvorak. Bienvenido a codegolf por cierto. Puede reducir fácilmente el recuento de caracteres a la mitad con algunas medidas simples; Algunos de ellos han sido mencionados. Además, las variables intermedias no son buenas. La comprensión de la lista es agradable. Pero si está utilizando sys.argv, también puede permitir que cada número de entrada sea un argumento, luego map(int,sys.argv[1:])hace lo que hacen sus 6 primeras líneas ahora. i=x=g=0funciona, pero debe cortar la cantidad de variables de todos modos. Sin embargo, te daré una cosa: esta es la entrada de Python de la que menos entiendo: D
daniero
3

C # - 264 259 252 237 caracteres

Utiliza el algoritmo más simple y produce una salida correcta sin volteos redundantes. Podría eliminar 7 caracteres si permitiera que incluyera 1 (sin voltear) en la salida, pero eso es feo.

gotoRecurrí a usar para el máximo golfage. También guardó algunos caracteres al permitirle realizar movimientos no invertidos (pero no imprimirlos).

Última mejora: mantener la matriz de entrada como cadenas en lugar de convertir a 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;}}}}}

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

Aquí está mi solución inicial, sin golf (264 caracteres golfizados):

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);
            }
        }
    }
}
Igby Largeman
fuente
No maneja secuencias no contiguas, dando resultados incorrectos con esas entradas.
@hatchet: No estoy seguro de lo que quieres decir. ¿Puedes darme un ejemplo?
Igby Largeman
Dada una entrada de 1 22, el resultado dice hacer un intercambio, lo que daría como resultado 22 1. Creo que su código espera que la secuencia incluya números contiguos (por ejemplo: 2 4 1 3), pero no espera entradas como ( 2 24 5 5 990).
@hatchet: De hecho, no hice ningún intento de apoyar las brechas en la secuencia, porque eso no tendría sentido. La idea del tipo de panqueque es ordenar una pila de objetos, no un grupo de números arbitrarios. El número asociado con cada objeto identifica su posición correcta en la pila. Por lo tanto, los números siempre comenzarán con 1 y serán contiguos.
Igby Largeman
No estaba seguro, porque la pregunta decía "secuencia", y en matemáticas, {1, 22} es una secuencia válida, pero ambos ejemplos eran números contiguos. Entonces solicité una aclaración del OP (ver comentarios sobre la pregunta). Creo que la mayoría de las respuestas aquí manejarán vacíos bien.
2

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

Pruébalo en línea! Encuentra el máximo, lo voltea hacia atrás y ordena recursivamente la lista restante.

Editar: -1 byte gracias a BMO

Laikoni
fuente
2

Perl 5.10 (o superior), 66 bytes

Incluye +3para -n The use 5.10.0para llevar el idioma al nivel perl 5.10 se considera gratuito

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

Ejecute con la entrada como una línea en STDIN:

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

Ordena la lista encontrando repetidamente cualquier inversión, volteándola al frente y luego volteando la inversión y volviendo todo a su posición anterior. Y eso es equivalente a intercambiar la inversión, por lo que no necesito invertir (lo cual es incómodo en las cadenas ya que invertiría los dígitos de los valores que convierten, por ejemplo, 12a 21)

Ton Hospel
fuente
1

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

versión legible

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

fuente