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 stdout
atau stderr
dengan 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:
((())())()
()((())())
(()(()))()
()(()(()))
((()))
contoh 1? atau()()()
? Sepertinya Anda tidak memiliki permutasi untuk setiap input.Jawaban:
CJam , 18 byte
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""
).sumber
[][]
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.[][]
pasangan ekstra[]
. Untuk yang lain saya tidak begitu yakin mereka tidak valid._{{B}%e!}&
sebagai ganti_!!{{B}%e!}*
&
hubungan arus pendek atau sesuatu?&
menjalankan blok hanya jika nilai lainnya benarHaskell ,
227210208205 byteCobalah 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!x
tambahkan Stringx
ke daftar String terakhira
(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:
h
memproses daftar bagian: ini berlakuv
untuk bagian pertama dan menggabungkan hasilnya dengan proses bagian yang tersisa.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.sumber
init a
.Python 2,
353350331 BytesMenerima string
()
sebagai input dan mencetak hasilnya.Coba di sini!
Saya menghindari menggunakan
itertools.permutations
dengan 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
()
pasangan dalam string input.()
pasangan lain .sumber
print
dan di tempat-tempat sepertii+1 if
(bisai+1if
). Juga di satu tempat yang Anda milikiy[0:i]
, Anda dapat menghilangkan angka 0.JavaScript (Firefox 30-57), 222 byte
Membawa
[]
string. Penjelasan:sumber
Mathematica, 337 byte
Bukan untuk mendapatkan poin kode-golf, tetapi untuk menunjukkan penggunaan
Permutations
danDistribute
dalam masalah ini. Mungkin ada pendekatan yang lebih baik.(
seq
: urutan,:alt
alternatif)Ambil input sebagai string, menggunakan kurung keriting
{
dan}
. Menghasilkan string multi-line.sumber