Hasilkan semua penjepit panjang string n

16

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 , sehingga jawaban terpendek yang valid - diukur dalam byte - menang.

Uji Kasus

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
Buah Esolanging
sumber
3
Jumlah entri dalam output adalah A025235
Gabriel Benamy
@GabrielBenamy Ah. Saya bertanya-tanya apakah itu sudah pernah dilihat sebelumnya. Menarik.
Buah Esolanging
2
Bagaimana kondisi kemenangan? Saya menganggap program terpendek (golf code).
Zgarb
Terkait
Martin Ender
1
Karena semua orang menganggap ini adalah kode golf, saya akan menandai tantangan yang sesuai (karena kalau tidak, akan membuat semua jawaban yang ada agak tidak berguna). Jika Anda menginginkan kriteria kemenangan yang berbeda, Anda dapat mempertimbangkan untuk memposting tantangan baru.
Martin Ender

Jawaban:

3

Jelly, 29 byte

-3 byte terima kasih kepada @JonathanAllan

Tolong , beri tahu saya jika ada masalah / bug / kesalahan atau byte yang bisa saya tiru!

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ

Cobalah online!

Solusi sebelumnya yang saya miliki:

“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€Tị
“[(*)]”ṗµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹ḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐL€Ṇ€×Jḟ0ị
“[(*)]”x⁸ṗ⁸Qµ¹µḟ”*œṣ⁾()Fœṣ⁾[]FµÐLµ€Ṇ€×Jḟ0ị

Penjelasan (Upaya terbaik saya pada deskripsi):

Input n
“[(*)]”ṗ-All strings composed of "[(*)]" of length n
µḟ”*    -Filter out all occurences of "*"
œṣ⁾()   -Split at all occurences of "()"
F       -Flatten
œṣ⁾[]   -Split at all occurences of "[]"
F       -Flatten
µÐL     -Repeat that operation until it gives a duplicate result
Ðḟ      -Filter
Zacharý
sumber
Anda dapat menyimpan tiga byte menggunakan filtering ( “[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ)
Jonathan Allan
15

Prolog, 69 byte

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

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) byang 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 demikian b) sehingga mereka cocok satu sama "brace string" di tepat satu cara (yang merupakan alasan yang baik sdan eharus ada, daripada mengelompokkan mereka ke dalam satu predikat). Ini membuat keduanya sepenuhnya reversibel; dengan demikian bdapat 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:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

sumber
rasanya seperti harus ada biaya untuk sintaks yang diperlukan untuk menentukan apakah Anda ingin menjalankan program "maju" atau "mundur". perl membayar 1 byte untuk setiap bit hal semacam itu
Sparr
Nah, Anda bisa membuat aturan bahwa argumen pada akhirnya selalu merupakan nilai balik, lalu balikkan urutan argumen untuk menentukan ke arah mana Anda menjalankan program. Cukup umum untuk bermain golf untuk mengetahui apa yang harus mereka lakukan sebagian dengan melihat apakah mereka diberi masukan, dan ini adalah prinsip yang sebanding. Namun, secara umum, sulit untuk membuat aturan yang berlaku untuk setiap bahasa yang memungkinkan; menjalankan builtin like lengthdan appendround way adalah bagian mendasar dari bahasa, dan fungsi pengguna sering melakukan hal yang sama.
Oh, hmm. Saya berasumsi ada beberapa indikasi dalam contoh Anda yang memicu perilaku tersebut.
Sparr
Nah, itu sepenuhnya karena argumen mana yang diberikan. Dalam program di atas, saya menulis length(A,N); jika Ndiberikan dan Atidak (yang akan terjadi jika predikat digunakan dengan cara yang diminta dalam program), lengthakan menghasilkan daftar yang Aterdiri dari Nelemen yang tidak diketahui. Menggunakan lengthuntuk 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).
1
@ ais523 -->dan DCGs secara umum adalah standar ISO Prolog .
Membius
5

Haskell, 101 94 byte

7 byte disimpan oleh Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Hampir mudah, mengikuti definisi, tetapi dengan ""kasus ini dipindahkan.

Menggunakan:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(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 sehingga b!!nberisi semua penjepit panjangnya n. Demikian pula, u!!nberisi semua atom ukuran n-1. Satu hal yang menyenangkan adalah bahwa kodenya tidak menggunakan angka. Ini tidak sepenuhnya golf : udan idapat digarisbawahi, dan tentunya melewatkan beberapa peluang golf lainnya Sayangnya, sepertinya tidak bisa dibuat lebih pendek dari versi pertama, tetapi menghitung length $ b !! 10lebih cepat.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)
Sievers Kristen
sumber
Simpan dua byte dengan b$n-kdan b$n-2. Juga, pada baris terakhir yang dapat Anda lakukan a:b<-["()","[]"]dan kembali a:s++b.
Zgarb
Oh saya ingin menggunakan ["()","[]"]tetapi tidak bisa melihat bagaimana meningkatkan ukuran kode dengannya. Terima kasih!
Christian Sievers
4

Mathematica, 116 byte

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Penjelasan

Characters@"*([)]"

Temukan karakter string "*([)]", berikan List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Temukan tupel dari daftar di atas dengan panjang n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Fungsi Boolean tanpa nama untuk menemukan apakah tupel seimbang:

#/."*"->Nothing

Hapus semua "*"di input.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Hapus semua kejadian berurutan "("dan")" atau "["dan "]"sampai input tidak berubah.

... =={}

Periksa apakah hasilnya kosong List .

Select[ ... , ... ]

Temukan tupel yang memberi True ketika fungsi Boolean diterapkan.

#<>""&/@

Ubah setiap Listkarakter menjadi Strings.

JungHwan Min
sumber
2
Agak tak terduga, {x=a___,"(",")",y=b___}|{x,"[","]",y}tampaknya berhasil.
Martin Ender
4

Python 2, 128 byte

n=input()
for i in range(5**n):
 try:s=','.join('  "00([*])00"  '[i/5**j%5::5]for j in range(n));eval(s);print s[1::4]
 except:1

Sekrup regex rekursif - kami menggunakan parser Python! Untuk memverifikasi itu, misalnya,*(**[])* adalah brace-string, kami melakukan hal berikut:

  1. 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.

  2. eval Itu.

  3. 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.

Lynn
sumber
2

PHP, 149 byte

for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));

Menggunakan yang lama menghasilkan semua yang mungkin dan kemudian metode filter. Gunakan seperti:

php -r "for(;$argv[1]--;$l=$c,$c=[])foreach($l?:['']as$s)for($n=5;$n--;)$c[]=$s.'*()[]'[$n];echo join(' ',preg_grep('/^((\*|\[(?1)]|\((?1)\))(?1)?|)$/',$l));" 4
pengguna59178
sumber
1

Python, 134 byte

from itertools import*
lambda n:[x for x in map(''.join,product('*()[]',repeat=n))if''==eval("x"+".replace('%s','')"*3%('*',(),[])*n)]

repl.it

Fungsi tanpa nama yang mengembalikan daftar panjang string yang valid n.
Bentuk semua panjang ntupel dari karakter *()[], bergabung ke dalam string menggunakan map(''.join,...)dan filter bagi mereka yang telah seimbang kurung dengan menghapus "pasangan" "*", "()"dan "[]"pada gilirannya nkali dan memeriksa bahwa hasilnya adalah string kosong ( nkali adalah berlebihan, terutama untuk "*"namun adalah golfier).

Jonathan Allan
sumber
1

Retina , 78 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

.+
$*
+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]
%(`^
$';
)+`(\[]|\(\)|\*)(?=.*;)|^;

A`;

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 1sebagai digit.

+%1`1
*$'¶$`($'¶$`)$'¶$`[$'¶$`]

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).

A`;

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.

Martin Ender
sumber
Saya mencoba onliny dengan input 5: ok. Dengan input 6 saya mendapat halaman kesalahan
edc65
@ edc65 Berfungsi untuk saya, tetapi tentu saja pendekatan ini tidak terlalu efisien, sehingga perlu beberapa detik. Apa jenis halaman kesalahan yang Anda maksud?
Martin Ender
Input 5: jawab dalam 3 detik. Input 6: setelah 7 detik, Di dalam kotak Output, saya mendapatkan sumber html dari apa yang mungkin merupakan halaman kesalahan dari proxy saya. Jika itu timeout maka itu timeout yang sangat singkat ... Saya mencoba untuk mendapatkan test case yang tepat untuk input 6, karena saya jawaban saya tampaknya ok untuk input 5, tetapi salah untuk 6 atau lebih
edc65
@ edc65 Pasti membutuhkan waktu lebih dari 7 detik, dan batas waktu TIO adalah satu menit. Saya belum pernah melihat kesalahan yang Anda jelaskan, mungkin layak untuk membahasnya di obrolan TIO (atau jika Anda lebih suka pada gitter atau GitHub ). Adapun keluaran referensi, inilah yang saya dapatkan untuk input 6: pastebin.com/WmmPPmrc (Input 7 membutuhkan waktu lebih dari satu menit.)
Martin Ender
1

Python 3.5, 146 byte

import re;from itertools import*;lambda f:{i for i in map(''.join,permutations("[()]*"*f,f))if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)}

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, memohon G(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 288 237 byte :

import re;D=lambda f:f and"for %s in range(%d)"%(chr(64+f),5)+D(f-1)or'';lambda g:[i for i in eval('["".join(('+''.join('"[()]*"['+chr(o)+'],'for o in range(65,65+g))+'))'+D(g)+']')if re.fullmatch("(\**\[\**\]\**|\**\(\**\)\**)*|\**",i)]

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 11dalam sekitar 115 detik , yang panjangnya 10sekitar 19 detik , panjangnya 9sekitar 4 detik , dan panjangnya 8di sekitar 0,73 detik pada mesin saya, sedangkan jawaban saya yang bersaing membutuhkan waktu lebih lama dari 115 detik untuk input 6.

Cobalah secara Online! (Ideone)

R. Kap
sumber
0

05AB1E, 23 byte

…[(*.∞sãʒ'*м„()„[]‚õ:õQ

Beberapa fitur ini mungkin telah diterapkan setelah pertanyaan diposting. Ada saran dipersilahkan!

Cobalah online!

Bagaimana?

…[(* - the string '[(*'
.∞ - intersected mirror, '[(*'=>'[(*)]'
s - swap the top two items, which moves the input to the top
ã - cartesian power
ʒ ...  - filter by this code:
  '*м      - remove all occurrences of '*'
  „()„[]‚  - the array ["()","[]"]
  õ        - the empty string ""
  :        - infinite replacement (this repeatedly removes "()", "[]", and "*" from the string
  õQ       - test equality with the empty string
Zacharý
sumber
Saya tidak tahu 05AB1E, tetapi tidak bisakah itu *juga berada di array penghapusan? Dan bisakah õQcek diganti dengan sesuatu seperti TIDAK?
Buah Esolanging
Saran pertama tidak akan menyimpan byte: '*м„()„[]‚õ: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")
Zacharý