Stack Cats to odwracalny język oparty na stosie. Jego odwracalna natura tworzy nieco dziwne pętle. To wyzwanie dotyczy pętli warunkowej (...). Gdy te pętle są zagnieżdżone w określony sposób, możliwe jest przekształcenie kodu w celu zmniejszenia głębokości zagnieżdżenia. Oto zasady (gdzie Ai Boznaczają dowolne fragmenty):

1. Kiedy jedna pętla zaczyna się od innej, możemy wyodrębnić wewnętrzną pętlę do przodu: ((A)B)staje się (A)(B).
2. Kiedy jedna pętla kończy się na drugiej, możemy wyodrębnić wewnętrzną pętlę do końca: (B(A))staje się (B)(A).
3. Puste pętle ()można całkowicie usunąć z programu. Jako następstwo (w połączeniu z innymi zasadami) ((A))jest równoważne z (A).

Jedyne zagnieżdżonej pętli, które zachowują się w formie (A(B)C), gdzie A, Ba Cto nie jest pusty.

Wyzwanie

Otrzymałeś prawidłowy program Stack Cats, a Twoim zadaniem jest maksymalne zmniejszenie poziomu zagnieżdżania pętli, bez pozostawiania pustych pętli, przy użyciu powyższych transformacji.

Prawidłowy program Stack Cats ...

• ... składa się tylko z postaci ()/\<>[]{}!"*+-:=ITX^_|.
• ... ma symetrię lustrzaną (np. \(]{}!{}[)/jest poprawnym programem, ale /|/nie jest).
• ... prawidłowo dobrane i zagnieżdżone ()i {}( [], <>i \/niekoniecznie muszą być dopasowane, jak zwykle, chociaż oni pojawiają się w parach ze względu na wymóg symetrii lustrzanej).

Jako dane wejściowe możesz wziąć ciąg znaków lub listę znaków, ale dane wyjściowe muszą być prezentowane w tym samym formacie.

Możesz napisać program lub funkcję i użyć dowolnej z naszych standardowych metod otrzymywania danych wejściowych i dostarczania danych wyjściowych. Pamiętaj, że te luki są domyślnie zabronione.

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

Przypadki testowe składają się z dwóch linii (wejściowej i wyjściowej), oddzielonych pustymi liniami. Zauważ, że jedno wyjście jest puste. Musisz także obsługiwać puste dane wejściowe (co powinno skutkować pustymi danymi wyjściowymi).

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

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

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

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


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)

Retina 0.8.2 , 113 107 67 66 bajtów

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

Wypróbuj online! Obejmuje oszczędność 3 4 bajtów dzięki @MartinEnder. Wyjaśnienie:

+`

Wielokrotnie stosuj zmianę, dopóki nie będzie żadnych dopasowań.

\(\)|

Dopasuj pustą pętlę (w którym to przypadku nic nie jest przechwytywane, więc podstawienie po prostu ją usuwa) lub:

(\()?

Opcjonalnie dopasuj a (. Jest to rejestrowane w grupie 1, jeśli pasuje, ale nie, jeśli nie.

(\(

Zdobądź główną część meczu w grupie 2 i dopasuj a (.

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

Wielokrotnie dopasowuj albo a (, przechwytywanie go w grupie 4, lub a ), usuwanie przechwytywania z grupy 4 (niepowodzenie, jeśli nie istnieje) lub coś innego.

(?(4)@)

Upewnij się, że w grupie 4 nie ma żadnych zapasowych zdjęć.

\))

Zakończ przechwytywanie grupy 2 inną ).

(?(1)|(\)))

Jeśli grupa przechwytywania 1 była pusta, )przechwyć grupę przechwytywania 5. (Tak więc dokładnie jedna z tych dwóch grup będzie miała przechwytywanie).

$5$2$1

Przesuń wspornik uchwycony w grupie 1 lub grupie 5 na drugą stronę grupy 2. To powoduje przesunięcie wewnętrznej pętli do przodu lub do końca zewnętrznej pętli, w zależności od tego, z którą stroną pasowała.

Stax v1.0.3 +, 76 65 64 62 58 bajtów ^CP437

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

70 bajtów po rozpakowaniu,

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

Uruchom i debuguj online!

Wyjaśnienie

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Mdto blok, który dzieli się A((B)C)Dna cztery części i zamienia na A(B)(C)D.

X!:Rx!:Rwykonuje blok na łańcuchu wejściowym (krok 1), a następnie odzwierciedla łańcuch (odbicie łańcucha w Stax odnosi się do odwracania łańcucha plus zamiany (tłumaczenia) na (<[{/(do) \}]>)) i wykonuje blok na otrzymanym łańcuchu, a następnie odzwierciedla go z powrotem (krok 2). Krok 2 jest zasadniczo konwertowany (A(B))na (A)(B).

c.()z:r usuń wszystkie puste pętle (krok 3).

gpjest generatorem, który znajduje punkt stałej iteracji. W takim przypadku ciąg jest iterowany w procesie 3-etapowym, dopóki nie zmieni się.

Wyjściowy wynik.

Python 3 , 226 223 212 206 bajtów

Ok, oto próba rozwiązania tego w języku, który nie obsługuje rekurencyjnego wyrażenia regularnego.

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]

Wypróbuj online!

Edycje:

• Przebudowano w [::-1]celu zaoszczędzenia 6 bajtów, dzięki Mr.Xcoder.

Ta gfunkcja jest podstawowym blokiem konstrukcyjnym, który znajduje wystąpienie ((A)B), zmienia je (A)(B), a następnie stosuje się do wyniku, dopóki nie będzie już możliwa transformacja.

Główne kroki to:

• Zastosuj gdo danych wejściowych normalnie.
• Zastosuj gdo odwróconego wejścia. Ten przebieg wykrywa wystąpienie ))A(B(odwróconego wejścia, które skutecznie obsługuje (A(B)).
• Usuń każde wystąpienie ().

Problem polega na tym, że gma tak złą strukturę kontrolną, że próba wyrównania jednej linii sprawiła, że ​​źle się wzdęcia, więc nie sądzę, że w oparciu o to rozwiązanie można dokonać znacznej poprawy.