Acoplar un programa Stack Cats

13

Stack Cats es un lenguaje reversible basado en pila. Su naturaleza reversible crea bucles algo extraños. Este desafío es sobre el ciclo condicional (...). Cuando estos bucles se anidan de ciertas maneras, es posible transformar el código para reducir la profundidad de anidación. Estas son las reglas (dónde Ay Brepresentan fragmentos arbitrarios):

  1. Cuando un ciclo comienza con otro ciclo, podemos extraer el ciclo interno al frente: se ((A)B)convierte (A)(B).
  2. Cuando un ciclo termina con otro ciclo, podemos extraer el ciclo interno hasta el final: se (B(A))convierte (B)(A).
  3. Los bucles vacíos (), se pueden eliminar del programa por completo. Como corolario (en conjunción con las otras reglas), ((A))es equivalente a (A).

Los bucles anidados única que permanecerán son de la forma (A(B)C), donde A, By Cson no vacío.

El reto

Se le proporciona un programa válido de Stack Cats y su tarea es reducir el nivel de anidamiento de los bucles tanto como sea posible, sin dejar bucles vacíos, utilizando las transformaciones anteriores.

Un programa válido de Stack Cats ...

  • ... consta solo de los personajes ()/\<>[]{}!"*+-:=ITX^_|.
  • ... tiene simetría de espejo (por ejemplo, \(]{}!{}[)/es un programa válido, pero /|/no lo es).
  • ... ha emparejado correctamente y anidado ()y {}( [], <>y \/no necesariamente tienen que ser igualado como de costumbre, a pesar de que aparecerán en parejas debido al requisito de simetría de espejo).

Puede tomar una cadena o una lista de caracteres como entrada, pero la salida debe presentarse en el mismo formato.

Puede escribir un programa o una función y utilizar cualquiera de nuestros métodos estándar para recibir entradas y proporcionar salidas. Tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.

Este es el , por lo que gana la respuesta válida más corta, medida en bytes .

Casos de prueba

Los casos de prueba son dos líneas cada uno (entrada y salida), separados por líneas vacías. Tenga en cuenta que una salida está vacía. También debe admitir la entrada vacía (que debería dar como resultado una salida vacía).

(((=+|+=)))
(=+|+=)

({(=+|+=)})
({(=+|+=)})

((\)/)I(\(/))
(\)(/)I(\)(/)

(()()(())()())


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)
Martin Ender
fuente
Solo para estar seguros, los bucles que tenemos que extraer solo se indican entre paréntesis (), por lo que una entrada {{A}B}permanecerá como está y no se extraerá {A}{B}también.
Kevin Cruijssen
@KevinCruijssen Sí, la transformación solo es válida para (...)bucles de tipo.
Martin Ender
En el caso de prueba final, ¿por qué está \^/dentro del paréntesis?
Kevin Cruijssen
1
@KevinCruijssen Esos son los paréntesis más externos después de extraer (<|>((X((T)))[_]))y (([_](((T))X))<|>).
Martin Ender
1
Ah, ya veo. Entonces ((A)B(C))se volverá (A)(B)(C)debido a las reglas 1 y 2 posteriormente: ((A)B(C))(A)(B(C))(regla 1) → (A)(B)(C)(regla 2).
Kevin Cruijssen

Respuestas:

6

Retina 0.8.2 , 113 107 67 66 bytes

+`\(\)|(\()?(\(((\()|(?<-4>\))|[^()])*(?(4)@)\))(?(1)|(\)))
$5$2$1

Pruébalo en línea! Incluye 3 4 bytes de ahorro gracias a @MartinEnder. Explicación:

+`

Aplica la sustitución repetidamente hasta que no haya coincidencias.

\(\)|

Haga coincidir un bucle vacío (en cuyo caso no se captura nada, por lo que la sustitución simplemente lo elimina) o:

(\()?

Opcionalmente coincida con a (. Esto se captura en el grupo 1 si coincide, pero no si no coincide.

(\(

Captura el cuerpo principal del partido en el grupo 2 y combina a (.

(
 (\()
|
 (<-4>\))
|
 [^()]
)*

Haga coincidir repetidamente a (, capturándolo en el grupo 4, o a ), eliminando una captura del grupo 4 (si no hay una), o algo más.

(?(4)@)

Asegúrese de que no queden capturas de repuesto en el grupo 4.

\))

Finalice la captura del grupo 2 con otro ).

(?(1)|(\)))

Si el grupo de captura 1 estaba vacío, capture un )grupo de captura 5. (entonces exactamente uno de esos dos grupos tendrá una captura).

$5$2$1

Mueva el soporte capturado en el grupo 1 o en el grupo 5 al otro lado del grupo 2. Esto tiene el efecto de mover el bucle interno hacia el frente o el final del bucle externo dependiendo de qué lado coincida.

Neil
fuente
2

Stax v1.0.3 +, 76 65 64 62 58 bytes CP437

îÜ•$o,Γ{í]Üf╒9♦╛üΣóç*\$ñ₧└ΦJ♠¥c╥jóu≥3E.╘ⁿ◄◘W₧<¶┼7úê╟┴zç↨aG

70 bytes cuando está desempaquetado,

{{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md}X!:Rx!:Rc.()z:rgp

¡Ejecute y depure en línea!

Explicación

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Mdes un bloque que se separa A((B)C)Den cuatro partes y lo convierte enA(B)(C)D .

X!:Rx!:Rejecuta el bloque en la cadena de entrada (paso 1), luego refleja la cadena (la reflexión de la cadena en Stax se refiere a invertir la cadena más reemplazar (traducir) (<[{/con (a) \}]>)) y ejecutar el bloque en la cadena obtenida, y luego reflejarlo de nuevo (paso 2). El paso 2 se está convirtiendo esencialmente (A(B))en(A)(B) .

c.()z:r elimine todos los bucles vacíos (paso 3).

gpes un generador que encuentra el punto fijo de una iteración. En este caso, la cadena se repite con el proceso de 3 pasos hasta que ya no cambie.

Salida implícita.

Weijun Zhou
fuente
1

Python 3 , 226 223 212 206 bytes

Bien, aquí hay un intento de resolver esto en un lenguaje que no admite expresiones regulares recursivas.

lambda s:g(g(s,*'()'),*')(').replace('()','')
def g(s,t,u):
 m,*a={},;i=v=0
 for c in s:
  i+=1;a+=[i]*(c==t)
  if c==u:*a,x=a;m[x]=i;v=m.get(x+1)
  if v:return g(s[:x]+s[x+1:v]+t+s[v:],t,u)
 return s[::-1]

Pruébalo en línea!

Ediciones:

  • Refactorizado [::-1]para guardar 6 bytes, gracias a Mr.Xcoder.

La gfunción es el bloque de construcción básico, que encuentra una ocurrencia de ((A)B), lo cambia a(A)(B) luego se aplica al resultado hasta que no sea posible más transformación.

Los pasos principales son:

  • Aplicar ga la entrada normalmente.
  • Aplicar ga la entrada invertida. Esta ejecución encuentra la aparición de ))A(B(en la entrada invertida, que maneja efectivamente (A(B)).
  • Eliminar cualquier aparición de ().

El problema es que gtiene una estructura de control tan mala que tratar de hacer una línea lo hizo hincharse mucho, por lo que no creo que sea posible una mejora importante en función de esta solución.

Bubbler
fuente