Gelembungkan tanda kurung!

27

Ada yang beberapa pertanyaan di situs ini tentang menyeimbangkan kurung, dan memeriksa apakah tanda kurung yang seimbang. Saya mengusulkan sekarang saatnya untuk menggunakan kurung yang seimbang itu untuk sesuatu!

Dalam matematika dan pemrograman, tanda kurung seperti gelembung, mengisolasi segala sesuatu di dalam bentuk segala sesuatu di luar sehingga apa pun yang ada di dalamnya dapat melakukan hal itu dengan tenang dan apa pun yang ada di luar hanya melihat satu objek. Namun, seutas kurung adalah satu dimensi, sedangkan gelembung biasanya setidaknya dua dimensi. Itu berarti bahwa gelembung bebas untuk bergerak di sekitar satu sama lain selama mereka tidak pernah menyentuh satu sama lain atau melintasi antara bagian dalam dan bagian luar gelembung lainnya.

Tantangan

Input adalah serangkaian tanda kurung yang cocok dari tipe tunggal, baik bulat (), persegi [], keriting {}atau sudut <>. Terserah Anda, jenis program apa yang ingin Anda terima, dan program yang hanya menerima satu jenis tanda kurung diterima. (Bonus imajiner jika program Anda dapat menangani salah satunya, poin bonus imajiner besar jika dapat menangani semuanya dalam input yang sama.) Input tidak dapat berisi apa pun di antara tanda kurung, meskipun spasi spasi tambahan diperbolehkan.

Outputnya adalah semua kemungkinan reorganisasi (dalam urutan sewenang-wenang, dan termasuk input asli) dari tanda kurung yang menghasilkan konfigurasi gelembung yang sama, tanpa dua string yang identik. Itu berarti bahwa dengan input ()(), output juga adil ()(), meskipun secara teknis ada dua gelembung yang dapat bertukar tempat. Untuk bonus imajiner besar-besaran, sebuah input {}[]()tentu saja akan menghasilkan 6 elemen / string / baris yang berbeda.

Dua konfigurasi gelembung "sama" jika Anda dapat membuat satu ke yang lain dengan memindahkan gelembung di sekitar, tanpa membiarkan gelembung melintas dari dalam gelembung lain ke luar, atau dari luar ke dalam. Jika Anda menyamakan tanda kurung bersarang dengan pohon (setiap pasangan yang cocok adalah satu simpul, dan setiap pasangan yang cocok di dalamnya adalah subnode, dan setiap pasangan yang cocok di dalamnya adalah subnode dari mereka lagi, dan seterusnya) di mana subnode dari setiap simpul yang dipesan dipesan , maka satu konfigurasi gelembung adalah pohon tempat simpul tidak berurutan.

Apa pun format output yang masuk akal akan dilakukan, seperti mengembalikan daftar string atau daftar karakter tunggal atau string tunggal dengan beberapa jenis spasi putih, atau mencetak ke stdoutatau stderrdengan beberapa bentuk karakter spasi putih yang terlihat (paling umum baris baru atau spasi) antara setiap reorganisasi.

Trailing space untuk setiap reorganisasi dan trailing serta mendahului newlines / elemen daftar kosong sebelum dan sesudah output aktual diizinkan. Anda harus menggunakan kurung yang sama dalam output Anda seperti yang Anda terima di input Anda. Terlepas dari tanda kurung, baris baru dan spasi seperti yang ditentukan di sini, dan pemisah apa pun yang Anda gunakan, tidak ada yang harus dicetak (termasuk karakter tidak terlihat / lebar-nol).

Skornya adalah jumlah byte dalam kode; hitungan terendah untuk setiap bahasa menang. Anda dapat mencatat apakah Anda mendapatkan bonus imajiner, baik reguler atau besar-besaran, tetapi itu tidak mempengaruhi skor Anda. Bonus aktual terlalu sulit untuk diseimbangkan dengan benar.

Contoh input-output

Contoh 1:

Memasukkan:

()(())

Keluaran:

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

Contoh 2:

Memasukkan:

(()())()()

Keluaran:

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

Contoh 3:

Memasukkan:

(()(()))()

Keluaran:

((())())()
()((())())
(()(()))()
()(()(()))
Arthur
sumber
Mengapa kita tidak bisa mendapatkan ((()))contoh 1? atau ()()()? Sepertinya Anda tidak memiliki permutasi untuk setiap input.
Wheat Wizard
@WheatWizard Itu tidak akan memberikan konfigurasi gelembung yang sama: satu gelembung besar dengan dua gelembung kosong di dalamnya.
Arthur
@ WoatWizard sejauh yang saya mengerti, Anda tidak dapat mengambil gelembung dari dalam gelembung lain ke luar, atau sebaliknya.
Grzegorz Puławski
@WheatWizard Saya menambahkan sedikit penjelasan.
Arthur
7
Btw, Selamat Datang di PPCG! Tantangan pertama yang bagus!
Tn. Xcoder

Jawaban:

4

CJam , 18 byte

{~{_{{B}%e!}&}:B~}

Cobalah online!

-2 Terima kasih kepada Business Cat .

Menerima input sebagai string yang hanya berisi []. Mengembalikan daftar permutasi (daftar kosong sama dengan string kosong di CJam, jadi alih-alih []Anda akan mendapatkan "").

Erik the Outgolfer
sumber
Mengapa hasilnya [][]adil ""? - Haruskah input dimasukkan dalam set ekstra []? Jika demikian mengapa ada set tambahan []sekitar apa (mungkin?) Adalah output untuk contoh yang disebutkan di atas? Juga pertanyaannya menyatakan "Anda harus menggunakan kurung yang sama dalam output Anda seperti yang Anda terima di input Anda. Terlepas dari tanda kurung, baris baru dan spasi seperti yang ditentukan di sini, dan pemisah apa pun yang Anda gunakan, tidak ada yang harus dicetak", jadi saya Saya tidak yakin campuran []dan ""dapat diterima.
Jonathan Allan
@ JonathanAllan Ya saya pikir Anda perlu menyertakan [][]pasangan ekstra []. Untuk yang lain saya tidak begitu yakin mereka tidak valid.
Erik the Outgolfer
Saya pikir Anda dapat melakukannya _{{B}%e!}&sebagai ganti_!!{{B}%e!}*
Bisnis Kucing
@BusinessCat Apakah &hubungan arus pendek atau sesuatu?
Erik the Outgolfer
&menjalankan blok hanya jika nilai lainnya benar
Bisnis Cat
4

Haskell , 227 210 208 205 byte

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

Cobalah online!

Yang ini tangguh!

Golf sedikit

Disimpan dua byte berkat Laikoni

Simpan dua byte berkat Bruce Forte

Saya tidak yakin ini berfungsi dalam setiap kasus. Beberapa penjelasan:

  • a!xtambahkan String xke daftar String terakhir a(a is of type [[String]])

  • snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])menggunakan persyaratan yang lebih pendek untuk mengekspresikan ide sederhana: pisahkan String pada root )( s. Misalnya "(()(()))()"memberi ["()(())", ""].

  • Kita perlu memproses setiap bagian dari perpecahan, kemudian mengumpulkan dan menggabungkan semua string untuk mendapatkan hasil yang benar:

    1. hmemproses daftar bagian: ini berlaku vuntuk bagian pertama dan menggabungkan hasilnya dengan proses bagian yang tersisa.

    2. v mengagregasi hasil untuk setiap permutasi bagian, dan menghapus duplikat.

Untuk menambahkan tampilan yang lebih luas: pada dasarnya Anda memiliki pohon (bukan biner) dengan node kosong. Cuti adalah (). Anda harus menghasilkan semua permutasi dari cabang untuk setiap node, tetapi Anda mungkin tidak mengambil cabang dari suatu node dan meletakkannya di node lain. Saya melakukan semacam pencarian pertama yang mendalam.

jferard
sumber
Anda dapat menjatuhkan tanda kurung init a.
Laikoni
2

Python 2, 353 350 331 Bytes

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Menerima string ()sebagai input dan mencetak hasilnya.

Coba di sini!

Saya menghindari menggunakan itertools.permutationsdengan bantuan dari jawaban Paolo untuk pertanyaan ini .

Terima kasih kepada Business Cat untuk menemukan 3 byte, dan terima kasih kepada Mr. Xcoder untuk 19 byte yang luar biasa!

Penjelasan

  1. Buat daftar tupel indeks masing-masing ()pasangan dalam string input.
  2. Jatuhkan tupel dari daftar yang dikelilingi oleh ()pasangan lain .
  3. Iris string pada indeks tupel yang tersisa.
  4. Buatlah daftar setiap permutasi dari daftar irisan.
  5. Bergabunglah dengan daftar dengan baris baru untuk dicetak.
Solvasi
sumber
Saya melihat beberapa byte yang bisa dicukur. Anda memiliki beberapa spasi putih yang dapat dihapus, yaitu setelah printdan di tempat-tempat seperti i+1 if(bisa i+1if). Juga di satu tempat yang Anda miliki y[0:i], Anda dapat menghilangkan angka 0.
Business Cat
Terima kasih, @BusinessCat! IDE saya mengeluhkan beberapa di antaranya, jadi saya masih mempelajari beberapa trik kode golf.
Solvasi
342 bytes (-8 bytes) dengan menyusun ulang beberapa persyaratan untuk menghapus spasi putih.
Tn. Xcoder
340 byte (-10 byte) dengan menggunakan perbandingan leksikografis atas pemeriksaan kesetaraan.
Tn. Xcoder
331 byte (-19 byte) karena tantangan memungkinkan pengembalian daftar Strings. yay, kami mengalahkan Mathematica :-)
Mr. Xcoder
2

JavaScript (Firefox 30-57), 222 byte

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Membawa []string. Penjelasan:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s
Neil
sumber
0

Mathematica, 337 byte

Bukan untuk mendapatkan poin kode-golf, tetapi untuk menunjukkan penggunaan Permutationsdan Distributedalam masalah ini. Mungkin ada pendekatan yang lebih baik.

( seq: urutan,: altalternatif)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Ambil input sebagai string, menggunakan kurung keriting {dan }. Menghasilkan string multi-line.

pengguna202729
sumber