Spłaszcz program Stack Cats

13

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 , 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)(<|>)
Martin Ender
źródło
Dla pewności, pętle, które musimy wyodrębnić, są oznaczone tylko nawiasami (), więc dane wejściowe {{A}B}pozostaną takie, jakie są i do których nie zostaną również wyodrębnione {A}{B}?
Kevin Cruijssen
@KevinCruijssen Tak, transformacja jest ważna tylko dla (...)pętli typu.
Martin Ender
W ostatnim przypadku testowym, dlaczego jest \^/w nawiasie?
Kevin Cruijssen
1
@KevinCruijssen To są najbardziej zewnętrzne nawiasy po wypakowaniu (<|>((X((T)))[_]))i (([_](((T))X))<|>).
Martin Ender,
1
O, rozumiem. Tak ((A)B(C))będzie (A)(B)(C)ze względu na obu reguł 1 i 2 kolejno: ((A)B(C))(A)(B(C))(zasada 1) → (A)(B)(C)(reguła 2).
Kevin Cruijssen

Odpowiedzi:

6

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.

Neil
źródło
2

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.

Weijun Zhou
źródło
1

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.

Bubbler
źródło