El problema del panqueque quemado

23

Este desafío está relacionado con Voltear panqueques .

Es posible que haya oído hablar de la clasificación de panqueques , donde una pila de panqueques se ordena por tamaño insertando una espátula en la pila y volteando todos los panqueques por encima de la espátula, hasta que los panqueques se clasifiquen de menor a mayor en el plato. El problema del panqueque quemado es ligeramente diferente. Todos los panqueques ahora tienen un lado quemado, y el lado quemado de cada panqueque debe mirar hacia el plato una vez que se complete la clasificación.

Por ejemplo, dada la siguiente pila (tamaño del panqueque a la izquierda. 0Significado con el lado quemado hacia abajo y 1significado con el lado quemado hacia arriba a la derecha):

1 0
3 1
2 1

Puede voltear toda la pila para obtener 20 30 11, voltear los dos primeros para obtener 31 21 11y voltear toda la pila nuevamente para obtener 10 20 30, una pila ordenada de panqueques quemados. Esta secuencia de movimientos, flip 3, flip 2, flip 3, podría representarse como 3 2 3.

El reto

  • Dada una variedad de tamaños de panqueques (no necesariamente únicos) y sus orientaciones, genera una secuencia válida de clasificación de panqueques quemados, es decir, una secuencia de volteos que lleva a que la pila de panqueques se clasifique de menor a mayor con los lados quemados hacia abajo.
  • La entrada y la salida pueden tener cualquier formato correcto con separadores, pero especifique qué formatos usa y establezca qué extremo de su formato de entrada es la parte superior de la pila (TOS).
  • Voltear cero panqueques está permitido.
  • Se permite mezclar separadores en la entrada / salida.

Casos de prueba

Para todos los siguientes casos de prueba, la entrada es una lista y la salida es una cadena separada por espacios, y TOS está a la izquierda.

[[1, 0], [3, 1], [2, 1]]
"3 2 3"

[[5, 1], [3, 0], [4, 1], [2, 1], [1, 0]]
"5 3 4 1 3 2 1"

[[5, 1], [3, 0], [3, 0], [1, 1]]
"4 3 2 3"

Como siempre, si algo no está claro o es incorrecto, hágamelo saber en los comentarios. ¡Buena suerte y buen golf!

Sherlock9
fuente

Respuestas:

7

Pitón 2, 83

Se espera que la entrada sea la lista de tuplas (tamaño, orientación) con la parte superior de la pila al final. La salida es una lista de tamaños para voltear separados por varios tipos de espacios en blanco.

a=input()
while a:i=a.index(max(a));print len(a)-i,a[i][1],len(a),i;a=a[i+1:]+a[:i]
Feersum
fuente
2
Aparentemente soy un idiota.
Leaky Nun
¿Está 0permitido en la lista de salida?
Leaky Nun
19
@LeakyNun Voltear 0 panqueques es eminentemente posible. De hecho, lo estoy haciendo ahora.
feersum
@daniero La parte superior de la pila está en el lado derecho.
Leaky Nun
@LeakyNun oh lo siento, mi mal
daniero
3

CJam (37 bytes)

q~{__$W>#)_p/(W%\M*2,f.^+(1=p_,)pW%}h

La entrada es una matriz en formato CJam en stdin; La salida es una lista separada por nueva línea de longitudes de volteo en stdout. La parte superior de la pila está en el índice 0; 0indica el lado quemado hacia arriba e 1indica el lado quemado hacia abajo.

Demostración en línea

Disección

La salida siempre es 3nlarga, donde nestá el número de panqueques. Primero volteamos el panqueque restante más grande hacia arriba; entonces, si está quemada, volteamos ese panqueque; y luego lo volteamos al fondo y repetimos como si la pila de panqueques fuera uno más corta.

q~         e# Parse input into array
{          e# Loop...
  __$W>#)  e#   Find 1-based index of largest element in array
  _p       e#   Dup and print
  /(       e#   Split into chunks that long, and pull off the first
  W%       e#   Reverse the first chunk. Note that we don't flip the burnt/unburnt bit
  \M*      e#   Merge the remaining chunks into a single array
  2,f.^    e#   Flip *their* burnt/unburnt bits
  +        e#   Concatenate, prepending the first chunk
  (1=p     e#   Pull off the first (largest) element and print its burnt/unburnt bit
  _,)p     e#   Print the number of remaining elements plus 1 (to account for the largest)
  W%       e#   Reverse. Note that the first chunk has now been flipped twice, which is
           e#   why we have left its burnt/unburnt bit alone
}h         e# ... until we get down to an empty array
Peter Taylor
fuente
3

Ruby, 101 95 93 bytes

No muy golfista, solo quería hacer una variante de tipo bogo. Es una función anónima que toma una matriz de matrices e imprime volteos aleatorios en stdout hasta que se ordenan los panqueques.

->a{(p r=-~rand(a.size)
a[0,r]=a[0,r].reverse.map{|x,b|[x,1-b]})while a!=a.sort||a.rassoc(1)}

Por ejemplo, puede asignarlo fy decirf.call [[1, 0], [3, 1], [2, 1]]

-5 bytes de @Jordan con el brillante uso de rassoc
-2 bytes de @ Sherlock9

daniero
fuente
1
Puede guardar algunos bytes reemplazándolos a.all?{...}con !a.rassoc(1).
Jordania
@ Jordan Wow, eso es realmente genial! No creo que haya pensado en usar ( r) assocantes, pero pensar en ello, probablemente sea útil en muchos problemas en este sitio, creo que debería ir en la publicación de consejos de golf de Ruby. De todos modos, gracias :) Yo también era capaz de matar a otro byte a pesar de la aplicación de la ley deMorgans y reemplazar untilcon while.
daniero
Como bsolo es 0o 1, 1-btambién funcionaría y ahorraría dos bytes.
Sherlock9