Aplatir un programme Stack Cats

13

Stack Cats est un langage réversible basé sur la pile. Sa nature réversible crée des boucles quelque peu étranges. Ce défi concerne la boucle conditionnelle (...). Lorsque ces boucles sont imbriquées de certaines manières, il est possible de transformer le code pour réduire la profondeur d'imbrication. Voici les règles (où Aet Breprésentent des extraits arbitraires):

  1. Lorsqu'une boucle commence par une autre boucle, nous pouvons extraire la boucle intérieure vers l'avant: ((A)B)devient (A)(B).
  2. Lorsqu'une boucle se termine par une autre boucle, nous pouvons extraire la boucle interne jusqu'à la fin: (B(A))devient (B)(A).
  3. Les boucles vides,, ()peuvent être entièrement supprimées du programme. En corollaire (en conjonction avec les autres règles), ((A))est équivalent à (A).

Les boucles ne imbriquées qui restent sont de la forme (A(B)C), où A, Bet ne Csont pas vides.

Le défi

Vous disposez d'un programme Stack Cats valide et votre tâche consiste à réduire le niveau d'imbrication des boucles autant que possible, sans laisser de boucles vides, en utilisant les transformations ci-dessus.

Un programme Stack Cats valide ...

  • ... se compose uniquement des personnages ()/\<>[]{}!"*+-:=ITX^_|.
  • ... a une symétrie miroir (par exemple, \(]{}!{}[)/est un programme valide, mais /|/ne l'est pas).
  • ... a correctement apparié et imbriqué ()et {}( [], <>et \/n'a pas nécessairement besoin d'être apparié comme d'habitude, bien qu'ils apparaissent par paires en raison de l'exigence de symétrie miroir).

Vous pouvez prendre une chaîne ou une liste de caractères en entrée, mais la sortie doit être présentée dans le même format.

Vous pouvez écrire un programme ou une fonction et utiliser l'une de nos méthodes standard de réception d'entrée et de sortie. Notez que ces failles sont interdites par défaut.

Il s'agit de , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Cas de test

Les cas de test sont deux lignes chacun (entrée et sortie), séparés par des lignes vides. Notez qu'une sortie est vide. Vous devez également prendre en charge l'entrée vide (ce qui devrait entraîner une sortie vide).

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

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

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

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


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)
Martin Ender
la source
Juste pour être sûr, les boucles que nous devons extraire ne sont indiquées que par des parenthèses (), donc une entrée {{A}B}restera telle quelle et ne sera pas extraite {A}{B}aussi?
Kevin Cruijssen
@KevinCruijssen Oui, la transformation n'est valide que pour les (...)boucles de type.
Martin Ender
Dans le dernier cas de test, pourquoi se trouve-t-il \^/entre parenthèses?
Kevin Cruijssen
1
@KevinCruijssen Ce sont les parenthèses les plus externes après avoir extrait (<|>((X((T)))[_]))et (([_](((T))X))<|>).
Martin Ender
1
Ah, je vois. Cela ((A)B(C))deviendra donc (A)(B)(C)dû aux règles 1 et 2 par la suite: ((A)B(C))(A)(B(C))(règle 1) → (A)(B)(C)(règle 2).
Kevin Cruijssen

Réponses:

6

Retina 0.8.2 , 113 107 67 66 octets

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

Essayez-le en ligne! Inclut une économie de 3 4 octets grâce à @MartinEnder. Explication:

+`

Appliquez la substitution à plusieurs reprises jusqu'à ce qu'il n'y ait plus de correspondance.

\(\)|

Correspond à une boucle vide (auquel cas rien n'est capturé de sorte que la substitution la supprime simplement) ou:

(\()?

Correspond éventuellement à a (. Ceci est capturé dans le groupe 1 s'il correspond, mais pas si ce n'est pas le cas.

(\(

Capturez le corps principal du match dans le groupe 2 et match a (.

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

Faites correspondre à plusieurs reprises a (, la capturant dans le groupe 4, ou a ), supprimant une capture du groupe 4 (échec s'il n'y en a pas), ou autre chose.

(?(4)@)

Assurez-vous qu'il ne reste aucune capture de rechange dans le groupe 4.

\))

Terminez le groupe de capture 2 par un autre ).

(?(1)|(\)))

Si le groupe de capture 1 était vide, alors capturez un )dans le groupe de capture 5. (Donc, exactement l'un de ces deux groupes aura une capture).

$5$2$1

Déplacez le support capturé dans le groupe 1 ou le groupe 5 de l'autre côté du groupe 2. Cela a pour effet de déplacer la boucle intérieure vers l'avant ou la fin de la boucle extérieure selon le côté auquel elle correspond.

Neil
la source
2

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

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

70 octets une fois déballés,

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

Exécutez et déboguez en ligne!

Explication

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Mdest un bloc qui se sépare A((B)C)Den quatre parties et le convertit enA(B)(C)D .

X!:Rx!:Rexécute le bloc sur la chaîne d'entrée (étape 1), puis reflète la chaîne (la réflexion de chaîne dans Stax fait référence à l'inversion de la chaîne plus le remplacement (traduction) (<[{/par (à) \}]>)) et exécute le bloc sur la chaîne obtenue, puis la renvoie (étape 2). L'étape 2 consiste essentiellement à convertir (A(B))en(A)(B) .

c.()z:r supprimez toutes les boucles vides (étape 3).

gpest un générateur qui trouve le point fixe d'une itération. Dans ce cas, la chaîne est itérée avec le processus en 3 étapes jusqu'à ce qu'elle ne change plus.

Sortie implicite.

Weijun Zhou
la source
1

Python 3 , 226 223 212 206 octets

D'accord, voici une tentative pour résoudre ce problème dans un langage qui ne prend pas en charge l'expression régulière récursive.

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]

Essayez-le en ligne!

Modifications:

  • Refactorisé [::-1]pour économiser 6 octets, grâce à Mr.Xcoder.

La gfonction est le bloc de construction de base, qui trouve une occurrence de ((A)B), la change en(A)(B) , puis s'applique au résultat jusqu'à ce qu'aucune transformation supplémentaire ne soit possible.

Les principales étapes sont les suivantes:

  • Appliquer gà l'entrée normalement.
  • Appliquer gà l'entrée inversée. Cette exécution trouve l'occurrence de ))A(B(dans l'entrée inversée, qui gère efficacement (A(B)).
  • Supprimez toute occurrence de ().

Le problème est gque la structure de contrôle est si mauvaise que le fait d'essayer d'une ligne la fait mal gonfler, donc je ne pense pas qu'une amélioration majeure soit possible basée sur cette solution.

Bubbler
la source