Un diagrama de estado de la pila muestra cómo los valores de una pila se cambian a la otra. Por ejemplo, este es un diagrama de estado de pila:
3 0 2 1 0
Esto significa que hay una pila que inicialmente contiene 3 valores (la 3parte). Estos valores están indexados de 0 a 2, con 0 en la parte superior: 2 1 0. La siguiente parte 0 2 1 0describe el estado final de la pila: el valor que originalmente estaba encima de la pila también se ha copiado en la parte posterior.
Estas transformaciones ocurren en una pila que admite varios tipos de datos:
- El tipo de "valor", que es lo que está originalmente en la pila. Esto podría ser una cadena, un entero, etc., pero no es necesario conocer su valor.
- El tipo "lista", que es una lista que contiene valores de cualquier tipo de datos.
Para modelar esta transformación, se permiten las siguientes operaciones:
S: Intercambia los dos valores en la parte superior de la pila:2 1 0→2 0 1D: Duplica el valor en la parte superior de la pila:1 0→1 0 0R: Elimine el valor superior en la pila.2 1 0→2 1L: Convierta el valor superior en una lista de un elemento que contenga ese valor:2 1 0→2 1 (0)C: Concatenar las dos listas superiores en la pila:2 (1) (0)→2 (1 0)U: Coloque todos los valores de una lista en la pila:2 (1 0)→2 1 0
Estos son equivalentes a los comandos de baja carga~ : ! a * ^ , siempre que no se utilicen otros comandos.
S, D, R, Y Lse puede utilizar con cualquier valor en la parte superior de la pila, pero Cy Udeben tener listas en la parte superior de la pila de funcionar. Un envío cuyas secuencias generadas intentan realizar operaciones no válidas (como Den una pila vacía o Uen una no lista) es incorrecto y debe ser castigado .
Para resolver un diagrama de estado de la pila, encuentre una secuencia de comandos que transformará correctamente el estado inicial de la pila en uno nuevo. Por ejemplo, una solución 3: 0 2 1 0es LSLCSLCULSLCLSLDCSC USLCU:
2 1 0
L 2 1 (0)
S 2 (0) 1
L 2 (0) (1)
C 2 (0 1)
S (0 1) 2
L (0 1) (2)
C (0 1 2)
U 0 1 2
L 0 1 (2)
S 0 (2) 1
L 0 (2) (1)
C 0 (2 1)
L 0 ((2 1))
S ((2 1)) 0
L ((2 1)) (0)
D ((2 1)) (0) (0)
C ((2 1)) (0 0)
S (0 0) ((2 1))
C (0 0 (2 1))
U 0 0 (2 1)
S 0 (2 1) 0
L 0 (2 1) (0)
C 0 (2 1 0)
U 0 2 1 0
Su tarea es escribir un programa que tome un diagrama de estado de la pila y genere una solución.
Casos de prueba
2 1 0 ->
3 2 0 -> SR
9 -> RRRRRRRRR
2 0 1 0 -> LSLCDCUR
2 0 1 1 -> SD
6 2 -> RRSRSRSR
5 0 1 2 3 4 -> LSLCSLCSLCSLCU
4 2 0 1 3 2 -> LSLCSLSCSLCULSLSCSLSCLSLDCSCUSLCU
Este es el código de golf , por lo que gana la respuesta válida más corta (en bytes).
fuente
Cnecesidad aparece en la primera y segunda posición de la pila? o el elemento en segunda posición podría agregarse a una lista en la parte superior?Cnecesita listas en ambas posiciones. No tiene sentido concatenar un valor y una lista.Respuestas:
Python 3, 84 bytes
Uso:
Explicación: Para comenzar, duplicamos el cero y lo envolvemos en una lista:
Esta es nuestra base. Ahora explicaré un algoritmo general que se convierte
... 1 0 (x)en... 1 0 (i x)entero arbitrarioi. Lo usaré como ejemploi = 2, y tenemos una lista arbitraria(x). Comenzamos envolviendo nuestra lista actual(x)en otra lista:Ahora repetimos los siguientes
itiempos de secuencia :Ahora estamos listos para insertar el 2 en la lista
(x). Esto va de la siguiente manera:Tenga en cuenta que seguimos presionando nuevos enteros a la izquierda. Así que lo primero
(0)que comenzamos con queda a la derecha.Después de insertar todos los enteros que necesitamos en la lista, eliminamos el resto de la pila intercambiando y eliminando n time (
SR). Finalmente desempaquetamos nuestra lista y0eliminamos el primero que insertamos para comenzar nuestra lista (UR).fuente
slugar del?lestaba definido en mi REPL.DLLSLSCSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCSRSRSRSRUR). Intenta ejecutar unaSinstrucción cuando solo hay 1 valor en la pila.CJam, 54 bytes
Solo una traducción de la solución Python de orlp a CJam. No hay nada nuevo aquí.
Explicación:
fuente