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 3
se puede ordenar primero volteando los primeros 6
elementos (la secuencia completa), obteniendo el resultado intermedio 3 2 1 4 5 6
, y luego volteando los primeros 3
elementos, 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 1
se 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
4 3 2 1
lugar de4 2 3 1
Respuestas:
GolfScript, 34/21 caracteres
(Gracias @PeterTaylor por cortar 4 caracteres)
Prueba en línea
Una versión más corta de 21 caracteres funciona solo para listas con elementos únicos
Prueba en línea
Ambas versiones producen soluciones subóptimas.
Explicación para la solución más corta:
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:
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):
fuente
&
en cualquier lugar, por lo que debe ser capaz de reemplazars
mientras&
y quitar el espacio en blanco.^
como variable en el desafío de Fibonacci;) ¡Gracias por el consejo!3 2 1
obtengo lo131211
que no es correcto.2 1 1
ya no se pueden ordenar.Python,
9190 caracteresVoltea el panqueque más grande hacia arriba, luego voltea toda la pila. Retire el panqueque más grande del fondo y repita.
i
es el índice del panqueque más grande.L=L[:i:-1]+L[:i]
voltea losi+1
panqueques, voltea loslen(L)
panqueques y luego suelta el último panqueque.fuente
print
Ruby 1.9 -
1098879 caracteresVersión mucho más compacta basada en la gran solución de Python de Keith:
Versión original:
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):
Toma la lista sin clasificar como argumentos de línea de comandos. Ejemplo de uso:
fuente
GolfScript,
3129 caracteresOtra solución de GolfScript, también se puede probar en línea .
Versión previa:
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.
fuente
Perl,
103100caracteresEspera entrada en la línea de comando.
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.
fuente
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:
(2 espacios = pestaña)
fuente
sys.exit()
con1/0
(en codegolf nunca le importa lo que se imprime en stderr ...).print s[::-1];1/0
afeitarme algunos caracteres.4 2 3 1
give2 3 2 4
, que en realidad no es válido.4 2 3 1
->2 4 3 1
->3 4 2 1
->4 3 2 1
->1 2 3 4
Python2: 120
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:
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
print
declaración.fuente
[:i][::-1]
->[i-1::-1]
,[:u][::-1]
->[u-1::-1]
, ahorra 2 caracteresL[:i]=L[i-1::-1];L[:u]=[u-1::-1]
ahorra otros 3 caracteresPython - 282 caracteres
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:
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:
El algoritmo básico que utilicé es el mencionado en el artículo wiki vinculado en la pregunta :
fuente
t=p[:x]
t=t[::-1]
(16 + sangría) se puede reducir at=p[:x][::-1]
(13), o inclusot=p[x-1::-1]
(12). En línea todo lo que pueda:p=p[x-1::-1]+p[x:]
len(a)-n
se convierte-n
;p=p[-n-1::-1]+p[-n:]
. Más golf utilizando las operaciones correctas:p=p[~n::-1]+p[-n:]
map(int,sys.argv[1:])
hace lo que hacen sus 6 primeras líneas ahora.i=x=g=0
funciona, 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: DC # -
264 259 252237 caracteresUtiliza 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.
goto
Recurrí 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.
Sin golf:
Aquí está mi solución inicial, sin golf (264 caracteres golfizados):
fuente
Haskell ,
7271 bytesPrué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
fuente
Perl 5.10 (o superior), 66 bytes
Incluye
+3
para-n
Theuse 5.10.0
para llevar el idioma al nivel perl 5.10 se considera gratuitoEjecute con la entrada como una línea en STDIN:
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,
12
a21
)fuente
C # - 229
versión legible
fuente