Ratakan program Stack Cats

13

Stack Cats adalah bahasa berbasis stack yang dapat dibalik. Sifatnya yang dapat dibalik membuat loop yang agak aneh. Tantangan ini adalah tentang loop bersyarat (...). Ketika loop ini bersarang dengan cara tertentu, dimungkinkan untuk mengubah kode untuk mengurangi kedalaman bersarang. Berikut adalah aturannya (di mana Adan Bberdiri untuk cuplikan yang sewenang-wenang):

  1. Ketika satu loop dimulai dengan loop lain, kita dapat mengekstrak loop dalam ke depan: ((A)B)menjadi (A)(B).
  2. Ketika satu loop berakhir dengan loop lain, kita dapat mengekstrak loop dalam ke ujung: (B(A))menjadi (B)(A).
  3. Loop kosong (),, dapat dihapus dari program sepenuhnya. Sebagai akibat wajar (dalam hubungannya dengan aturan lain), ((A))setara dengan (A).

Satu-satunya loop bersarang yang akan tersisa adalah dari bentuk (A(B)C), di mana A, BdanC tidak kosong.

Tantangan

Anda diberi program Stack Cats yang valid dan tugas Anda adalah mengurangi sebanyak mungkin level loop, tanpa meninggalkan loop kosong, menggunakan transformasi di atas.

Program Stack Cats yang valid ...

  • ... hanya terdiri dari karakter ()/\<>[]{}!"*+-:=ITX^_| .
  • ... memiliki simetri cermin (mis. \(]{}!{}[)/adalah program yang valid, tetapi/|/ tidak).
  • ... telah benar-benar cocok dan bersarang ()dan {}( [], <>dan \/tidak perlu dicocokkan seperti biasa, meskipun mereka akan muncul berpasangan karena persyaratan simetri cermin).

Anda dapat mengambil string atau daftar karakter sebagai input, tetapi output harus disajikan dalam format yang sama.

Anda dapat menulis sebuah program atau fungsi dan menggunakan salah satu metode standar kami untuk menerima input dan memberikan output. Perhatikan bahwa celah ini dilarang secara default.

Ini adalah , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

Kasing uji masing-masing adalah dua jalur (input dan output), dipisahkan oleh jalur kosong. Perhatikan bahwa satu output kosong. Anda juga perlu mendukung input kosong (yang seharusnya menghasilkan output kosong).

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

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

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

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


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)
Martin Ender
sumber
Hanya untuk memastikan, loop yang harus kita ekstrak hanya ditunjukkan oleh tanda kurung (), jadi input {{A}B}akan tetap apa adanya dan tidak akan diekstraksi {A}{B}juga?
Kevin Cruijssen
@KevinCruijssen Ya, transformasi hanya berlaku untuk (...)loop -type.
Martin Ender
Dalam kasus tes akhir, mengapa \^/di dalam kurung?
Kevin Cruijssen
1
@KevinCruijssen Itu adalah kurung terluar setelah Anda mengekstrak (<|>((X((T)))[_]))dan (([_](((T))X))<|>).
Martin Ender
1
Ah saya mengerti. Maka ((A)B(C))akan menjadi (A)(B)(C)karena kedua aturan 1 dan 2 selanjutnya: ((A)B(C))(A)(B(C))(aturan 1) → (A)(B)(C)(aturan 2).
Kevin Cruijssen

Jawaban:

6

Retina 0.8.2 , 113 107 67 66 byte

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

Cobalah online!Termasuk penghematan 3 4 byte berkat @MartinEnder. Penjelasan:

+`

Lakukan penggantian secara berulang sampai tidak ada kecocokan.

\(\)|

Cocokkan loop kosong (dalam hal ini tidak ada yang ditangkap sehingga substitusi hanya menghapusnya) atau:

(\()?

Secara opsional cocok dengan a ( . Ini ditangkap di grup 1 jika cocok, tetapi tidak jika tidak.

(\(

Tangkap bagian utama pertandingan di grup 2 dan cocokkan a ( .

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

Cocokkan berulang kali dengan a (, menangkapnya di grup 4, atau a) , menghapus tangkapan dari grup 4 (gagal jika tidak ada), atau yang lainnya.

(?(4)@)

Pastikan tidak ada tangkapan cadangan yang tersisa di grup 4.

\))

Akhiri penangkapan grup 2 dengan yang lain ).

(?(1)|(\)))

Jika capture group 1 kosong, maka capture a )di capture group 5. (Jadi tepat salah satu dari dua grup tersebut akan memiliki capture).

$5$2$1

Pindahkan braket yang ditangkap dalam grup 1 atau grup 5 ke sisi lain grup 2. Ini memiliki efek memindahkan loop dalam ke depan atau akhir loop luar tergantung pada sisi mana yang cocok.

Neil
sumber
2

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

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

70 byte saat dibongkar,

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

Jalankan dan debug online!

Penjelasan

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Mdadalah blok yang memisahkan A((B)C)Dmenjadi empat bagian dan mengubahnya menjadi A(B)(C)D.

X!:Rx!:Rmengeksekusi blok pada string input (langkah 1), kemudian mencerminkan string (refleksi string dalam Stax mengacu pada membalikkan string plus mengganti (menerjemahkan) (<[{/dengan (untuk) \}]>)) dan menjalankan blok pada string yang diperoleh, dan kemudian memantulkannya kembali (Langkah 2). Langkah 2 pada dasarnya mengkonversi (A(B))ke (A)(B).

c.()z:r hapus semua loop kosong (langkah 3).

gpadalah generator yang menemukan titik perbaikan iterasi. Dalam hal ini string diulangi dengan proses 3 langkah hingga tidak lagi berubah.

Output tersirat.

Weijun Zhou
sumber
1

Python 3 , 226 223 212 206 byte

Oke, ini adalah upaya untuk menyelesaikan ini dalam bahasa yang tidak mendukung regex rekursif.

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]

Cobalah online!

Suntingan:

  • Refactored [::-1]untuk menyimpan 6 byte, terima kasih kepada Mr.Xcoder.

The gfungsi adalah blok bangunan dasar, yang menemukan kejadian dari ((A)B), perubahan itu(A)(B) , maka berlaku itu sendiri untuk hasil sampai tidak ada lagi transformasi adalah mungkin.

Langkah-langkah utamanya adalah:

  • Berlaku guntuk input secara normal.
  • Berlaku guntuk input terbalik. Jalankan ini menemukan terjadinya ))A(B(input terbalik, yang secara efektif menangani (A(B)).
  • Hapus kejadian ().

Masalahnya adalah, gmemiliki struktur kontrol yang sangat buruk sehingga mencoba untuk membuat satu baris itu membuatnya kembung, jadi saya tidak berpikir perbaikan besar dimungkinkan berdasarkan solusi ini.

Bubbler
sumber