String kurung didefinisikan sebagai string yang terdiri dari karakter *()[]
di mana kawat gigi cocok dengan benar:
[brace-string] ::= [unit] || [unit] [brace-string]
[unit] ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"
Ini adalah brace-string yang valid:
((())***[]**)****[(())*]*
Tapi ini bukan:
)(
**(**[*](**)
**([*)]**
Tugas Anda adalah menulis sebuah program (atau fungsi) yang, diberi bilangan bulat positif n
, mengambil angka sebagai input dan output (atau mengembalikan) semua panjang tanda kurung yang valid n
.
Spesifikasi
- Anda dapat menampilkan string dalam urutan apa pun.
- Anda dapat menampilkan sebagai daftar atau string yang dipisahkan oleh karakter yang berbeda.
- Program Anda harus menangani 0 dengan benar. Ada 1 kemungkinan brace-string dengan panjang 0, yang merupakan string kosong
""
. - Ini adalah kode-golf , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.
Uji Kasus
0.
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
code-golf
balanced-string
Buah Esolanging
sumber
sumber
Jawaban:
Jelly, 29 byte
-3 byte terima kasih kepada @JonathanAllan
Tolong , beri tahu saya jika ada masalah / bug / kesalahan atau byte yang bisa saya tiru!
Cobalah online!
Solusi sebelumnya yang saya miliki:
Penjelasan (Upaya terbaik saya pada deskripsi):
sumber
“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ
)Prolog, 69 byte
Salah satu sifat paling menarik dari Prolog adalah bahwa dalam banyak kasus Prolog mampu menjalankan program mundur; misalnya, alih-alih menguji untuk melihat apakah sesuatu itu benar, Anda dapat menghasilkan semua solusi yang benar, dan alih-alih memeriksa panjang string, Anda dapat menghasilkan semua string dengan panjang tertentu. (Properti Prolog yang bagus lainnya adalah ia membutuhkan spasi setelah akhir setiap definisi predikat, dan baris baru dapat dimasukkan semurah ruang, sehingga bahkan program golf seringkali cukup mudah dibaca.)
Di atas mendefinisikan predikat (setara dengan fungsi)
b
yang menguji untuk melihat apakah suatu string memiliki panjang tertentu dan merupakan "penjepit string" seperti yang didefinisikan dalam pertanyaan. Secara khusus, ia melakukan ini melalui dukungan tata bahasa / regex / pola-pencocokan Prolog yang memberikan sedikit gula, baik untuk mendefinisikan jenis ekspresi ini (tampaknya ini standar / portabel, tetapi saya tidak mengetahui hal ini ketika awalnya menulis jawaban, dan dengan demikian diasumsikan jawabannya hanya akan bekerja pada satu implementasi Prolog; tampaknya ini bekerja pada setiap implementasi yang sesuai dengan standar, meskipun). Program ini dapat diterjemahkan ke dalam bahasa Inggris secara langsung; dua baris pertama mengatakan " s adalah string kosong, atau e diikuti oleh s ; a eadalah tanda bintang, atau s dalam tanda kurung, atau s dalam tanda kurung siku ". Baris ketiga dapat diartikan sebagai" B dari N dapat menjadi A jika A adalah daftar dengan panjang N dan A adalah s diikuti dengan nol tali."Aku mengambil beberapa perawatan untuk menulis
s
(dan dengan demikianb
) sehingga mereka cocok satu sama "brace string" di tepat satu cara (yang merupakan alasan yang baiks
dane
harus ada, daripada mengelompokkan mereka ke dalam satu predikat). Ini membuat keduanya sepenuhnya reversibel; dengan demikianb
dapat digunakan untuk menghasilkan semua "brace strings" dari panjang tertentu, selain untuk menguji apakah sebuah string adalah brace string dengan panjang tertentu (itu juga dapat digunakan putaran cara ketiga, untuk mengetahui panjang brace string, tapi itu hampir pasti mode operasi yang paling tidak berguna). Implementasi adalah rekursif, misalnya untuk menghasilkan s , kode tersebut akan menghasilkan semua kemungkinan e s yang tidak lebih dari panjang yang dibutuhkan dari output, dan menambahkan semua kemungkinan ss yang sesuai dengan ruang yang tersisa untuk mereka; karena saya menentukan panjang argumen sebelumnya (dalam b ), mesin Prolog tahu bahwa ia tidak dapat menghasilkan output yang lebih panjang dari panjang yang diberikan, yang memungkinkan rekursi untuk mengakhiri.Berikut ini contoh program yang sedang beroperasi:
sumber
length
danappend
round way adalah bagian mendasar dari bahasa, dan fungsi pengguna sering melakukan hal yang sama.length(A,N)
; jikaN
diberikan danA
tidak (yang akan terjadi jika predikat digunakan dengan cara yang diminta dalam program),length
akan menghasilkan daftar yangA
terdiri dariN
elemen yang tidak diketahui. Menggunakanlength
untuk mengukur panjang daftar mungkin lebih umum digunakan (meskipun menggunakannya "mundur" cukup umum dalam pemrograman Prolog). Sebagian besar predikat akhirnya bekerja dengan cara yang sama (satu-satunya alasan mereka tidak melakukannya adalah jika mencoba membalikkannya akan membentuk loop tak terbatas, yang cukup umum).-->
dan DCGs secara umum adalah standar ISO Prolog .Haskell,
10194 byte7 byte disimpan oleh Zgarb!
Hampir mudah, mengikuti definisi, tetapi dengan
""
kasus ini dipindahkan.Menggunakan:
(Perhitungan kedua membutuhkan waktu kurang dari satu detik pada mesin yang lambat.)
Saya juga ingin berbagi hasil dari pendekatan lain yang saya buat sambil berpikir tentang menghasilkan fungsi. Ini mendefinisikan daftar
b
daftar string sehinggab!!n
berisi semua penjepit panjangnyan
. Demikian pula,u!!n
berisi semua atom ukurann-1
. Satu hal yang menyenangkan adalah bahwa kodenya tidak menggunakan angka. Ini tidak sepenuhnya golf :u
dani
dapat digarisbawahi, dan tentunya melewatkan beberapa peluang golf lainnya Sayangnya, sepertinya tidak bisa dibuat lebih pendek dari versi pertama, tetapi menghitunglength $ b !! 10
lebih cepat.sumber
b$n-k
danb$n-2
. Juga, pada baris terakhir yang dapat Anda lakukana:b<-["()","[]"]
dan kembalia:s++b
.["()","[]"]
tetapi tidak bisa melihat bagaimana meningkatkan ukuran kode dengannya. Terima kasih!Mathematica, 116 byte
Penjelasan
Temukan karakter string
"*([)]"
, berikanList
{"*", "(", "[", ")", "]"}
.Temukan tupel dari daftar di atas dengan panjang
n
.Fungsi Boolean tanpa nama untuk menemukan apakah tupel seimbang:
Hapus semua
"*"
di input.Hapus semua kejadian berurutan
"("
dan")"
atau"["
dan"]"
sampai input tidak berubah.Periksa apakah hasilnya kosong
List
.Temukan tupel yang memberi
True
ketika fungsi Boolean diterapkan.Ubah setiap
List
karakter menjadiString
s.sumber
{x=a___,"(",")",y=b___}|{x,"[","]",y}
tampaknya berhasil.Python 2, 128 byte
Sekrup regex rekursif - kami menggunakan parser Python! Untuk memverifikasi itu, misalnya,
*(**[])*
adalah brace-string, kami melakukan hal berikut:Buat string seperti
"*", (0,"*","*", [0,0] ,0) ,"*"
, di mana setiap karakter kedua dari empat adalah karakter dari penjepit, dan karakter yang tersisa adalah lem untuk membuat ini ekspresi Python yang potensial.eval
Itu.Jika itu tidak menimbulkan kesalahan, cetak
s[1::4]
(karakter penjepit-string).The lem karakter dipetik sehingga string saya buat adalah ekspresi Python valid jika dan hanya jika mengambil setiap karakter kedua dari empat hasil yang valid penjepit-string.
sumber
PHP, 149 byte
Menggunakan yang lama menghasilkan semua yang mungkin dan kemudian metode filter. Gunakan seperti:
sumber
Python, 134 byte
repl.it
Fungsi tanpa nama yang mengembalikan daftar panjang string yang valid
n
.Bentuk semua panjang
n
tupel dari karakter*()[]
, bergabung ke dalam string menggunakanmap(''.join,...)
dan filter bagi mereka yang telah seimbang kurung dengan menghapus "pasangan""*"
,"()"
dan"[]"
pada gilirannyan
kali dan memeriksa bahwa hasilnya adalah string kosong (n
kali adalah berlebihan, terutama untuk"*"
namun adalah golfier).sumber
Retina , 78 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1.
Cobalah online!
Penjelasan
Saya membuat semua string yang mungkin dengan panjang 5 dan kemudian saya menyaring yang tidak valid.
Ini mengubah input menjadi unary, menggunakan
1
sebagai digit.Ini berulang kali (
+
) menggantikan yang pertama (1
) satu di setiap baris (%
) sedemikian rupa sehingga membuat lima salinan dari baris, satu untuk setiap karakter yang mungkin. Ini dilakukan dengan menggunakan pengganti awalan dan akhiran,$`
dan$'
untuk membangun sisa setiap baris.Loop ini berhenti ketika tidak ada lagi 1 untuk diganti. Pada titik ini, kami memiliki semua string panjang yang mungkin
N
, satu di setiap baris.Dua tahap ini dieksekusi untuk setiap baris secara terpisah (
%
). Tahap pertama hanya menduplikasi baris, dengan;
untuk memisahkan dua salinan.Tahap kedua adalah loop lain (
+
), yang berulang kali menghapus[]
,()
atau*
dari salinan pertama string, atau menghapus titik koma di awal baris (yang hanya mungkin setelah string telah menghilang sepenuhnya).String yang valid adalah yang tidak lagi memiliki tanda titik koma di depannya, jadi kami hanya membuang semua baris (
A
) yang berisi tanda titik koma.sumber
Python 3.5, 146 byte
Sangat lama dibandingkan dengan jawaban lain, tetapi yang terpendek yang dapat saya temukan saat ini. Ini dalam bentuk fungsi lambda anonim dan karena itu harus dipanggil dalam format
print(<Function Name>(<Integer>))
Menghasilkan satu set Python dari string yang tidak berurutan yang mewakili semua kemungkinan penjepit dari panjang input.
Misalnya, dengan asumsi fungsi di atas dinamai
G
, memohonG(3)
akan menghasilkan output berikut:Cobalah secara Online! (Ideone)
Namun, jika, seperti saya, Anda tidak benar-benar penggemar menyederhanakan hal menggunakan built-in, maka di sini adalah saya sendiri asli jawabannya tidak menggunakan setiap perpustakaan eksternal untuk menemukan permutasi, dan saat ini berdiri pada kekalahan
288237 byte :Sekali lagi, seperti jawaban yang bersaing, yang ini dalam bentuk fungsi lambda dan karenanya harus disebut dalam format
print(<Function Name>(<Integer>))
Dan menampilkan daftar Python dari string yang tidak disortir yang mewakili semua penjepit-string dari panjang input. Misalnya, jika lambda dipanggil sebagai
G(3)
, kali ini hasilnya adalah sebagai berikut:Juga, yang ini juga jauh lebih cepat daripada jawaban saya yang lain, mampu menemukan semua penjepit panjang
11
dalam sekitar 115 detik , yang panjangnya10
sekitar 19 detik , panjangnya9
sekitar 4 detik , dan panjangnya8
di sekitar 0,73 detik pada mesin saya, sedangkan jawaban saya yang bersaing membutuhkan waktu lebih lama dari 115 detik untuk input6
.Cobalah secara Online! (Ideone)
sumber
05AB1E, 23 byte
Beberapa fitur ini mungkin telah diterapkan setelah pertanyaan diposting. Ada saran dipersilahkan!
Cobalah online!
Bagaimana?
sumber
*
juga berada di array penghapusan? Dan bisakahõQ
cek diganti dengan sesuatu seperti TIDAK?'*м„()„[]‚õ:
vs„()„[]‚'*«õ:
(tidak diuji), karena tidak ada perintah untuk menggabungkan 3 nilai AFAIK. Yang kedua tidak akan berfungsi karena tidak ada TIDAK yang akan beroperasi seperti itu pada sebuah string, AFAIK. (Di mana AFAIK mewakili "sejauh yang saya tahu")