Wygeneruj wszystkie nawiasy klamrowe o długości n

16

Ciąg nawiasów klamrowych jest zdefiniowany jako ciąg składający się ze znaków, *()[]w których nawiasy klamrowe pasują poprawnie:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"

To jest prawidłowy nawias klamrowy:

((())***[]**)****[(())*]*

Ale to nie są:

)(
**(**[*](**)
**([*)]**

Twoim zadaniem jest napisanie programu (lub funkcji), który przy dodatniej liczbie całkowitej nprzyjmuje liczbę jako dane wejściowe i wyjściowe (lub zwraca) wszystkie prawidłowe ciągi nawiasów o długości n.

Dane techniczne

  • Możesz wyprowadzać ciągi w dowolnej kolejności.
  • Możesz generować jako listę lub ciąg znaków oddzielony innym znakiem.
  • Twój program musi poprawnie obsługiwać 0. Istnieje 1 możliwy ciąg nawiasu klamrowego o długości 0, który jest pustym ciągiem "".
  • To jest , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .

Przypadki testowe

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
Esolanging Fruit
źródło
3
Liczba pozycji na wyjściu to A025235
Gabriel Benamy,
@GabrielBenamy Ah. Zastanawiałem się, czy wcześniej na to spojrzano. Ciekawy.
Esolanging Fruit
2
Jaki jest warunek wygranej? Zakładam najkrótszy program (code golf).
Zgarb
Związane z.
Martin Ender
1
Ponieważ wszyscy zakładają, że jest to golf golfowy, odpowiednio oznaczę to wyzwanie (ponieważ w przeciwnym razie wszystkie istniejące odpowiedzi byłyby nieco bezcelowe). Jeśli zamierzałeś zastosować inne kryterium wygranej, możesz rozważyć opublikowanie nowego wyzwania.
Martin Ender

Odpowiedzi:

3

Galaretka, 29 bajtów

-3 bajty dzięki @JonathanAllan

Proszę powiadom mnie, jeśli są jakieś problemy / bugi / błędy lub bajty mogę strącać!

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

Wypróbuj online!

Poprzednie rozwiązania miałem:

“[(*)]”ṗµḟ”*œṣ⁾()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ị

Objaśnienie (Moja najlepsza próba opisu):

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ý
źródło
Możesz zapisać trzy bajty za pomocą filtrowania ( “[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ)
Jonathan Allan,
15

Prolog, 69 bajtów

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

Jedną z najbardziej interesujących właściwości Prologa jest to, że w wielu przypadkach jest on w stanie uruchomić program wstecz; na przykład, zamiast sprawdzać, czy coś jest prawdą, możesz wygenerować wszystkie rozwiązania, dla których jest to prawda, i zamiast sprawdzać długość łańcucha, możesz wygenerować wszystkie łańcuchy o określonej długości. (Inną fajną właściwością Prologa jest to, że wymaga on spacji po zakończeniu każdej definicji predykatu, a nową linię można wstawić tak tanio jak spację; w ten sposób nawet programy w golfa są często dość czytelne).

Powyższe definiuje predykat (odpowiednik funkcji), bktóry sprawdza, czy łańcuch ma określoną długość i jest „łańcuchem nawiasowym”, jak zdefiniowano w pytaniu. Dokładniej, robi to poprzez wsparcie gramatyki Prologa / wyrażenia regularnego / dopasowania wzorca, które daje trochę miłego, krótkiego cukru do zdefiniowania tego rodzaju wyrażeń (najwyraźniej jest to standardowy / przenośny, ale nie wiedziałem o tym podczas pisania odpowiedzi, a zatem założono, że odpowiedź zadziała tylko na jednej implementacji Prolog; wydaje się, że działa na każdej implementacji zgodnej ze standardami). Program można bezpośrednio przetłumaczyć na angielski; pierwsze dwa wiersze mówią: „ s jest pustym ciągiem lub e po którym następuje s ; an ejest gwiazdką lubsw nawiasach lub sw nawiasach kwadratowych. Trzeci wiersz może być interpretowany jako „ b z N może być A, jeśli A jest listą o długości N, a A to s, po którym następuje łańcuch zerowy”.

Wziąłem trochę opieki napisać s(i tym samym b), tak aby dopasować każdy nawias „ciąg” w dokładnie jeden sposób (co jest powodem, że zarówno si emuszą istnieć, zamiast grupując je w jednym orzecznika). To sprawia, że ​​oba są całkowicie odwracalne; dlatego bmożna go wykorzystać do wygenerowania wszystkich „łańcuchów nawiasu klamrowego” o danej długości, oprócz testowania, czy łańcuch jest struną nawiasu klamrowego o danej długości (można go również użyć w drugą stronę, aby obliczyć długość nawiasu string, ale prawie na pewno jest to najmniej przydatny tryb działania). Implementacja jest rekurencyjna, np. Aby wygenerować s , kod wygeneruje wszystkie możliwe e , które nie są dłuższe niż wymagana długość wyjścia, i dołączy wszystkie możliwe ss, które pasują do nich w pozostałej przestrzeni; ponieważ z góry podałem długość argumentu (w ramach b ), silnik Prolog wie, że nie może wygenerować wyniku dłuższego niż podana długość, co pozwala na zakończenie rekursji.

Oto przykład działającego programu:

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

źródło
wydaje się, że składnia wymaga pewnego kosztu, aby określić, czy chcesz uruchomić program „do przodu”, czy „do tyłu”. perl płaci 1 bajt za każdą rzecz tego rodzaju
Sparr
Cóż, możesz wprowadzić regułę, że argumenty na końcu są zawsze wartością zwracaną, a następnie odwrócić kolejność argumentów, aby określić, w którą stronę uruchamiasz program. Języki gry w golfa dość często zastanawiają się, co powinni robić, patrząc na to, czy otrzymali jakieś uwagi, i jest to porównywalna zasada. Zasadniczo jednak trudno jest stworzyć reguły, które będą się odnosić do każdego możliwego języka; uruchamianie wbudowanych jak lengthi appendna odwrót jest podstawową częścią języka, a funkcje użytkownika często robią to samo.
Och, hmm. Zakładam, że w twoim przykładzie było pewne wskazanie, które wywołało dane zachowanie.
Sparr
Nie, to całkowicie z powodu podanych argumentów. W powyższym programie piszę length(A,N); if Njest podane i Anie jest (co stanie się, jeśli predykat zostanie użyty w sposób wymagany w programie), lengthwygeneruje listę Askładającą się z Nnieznanych elementów. Używanie lengthdo mierzenia długości listy jest prawdopodobnie częściej używane (chociaż używanie „wstecz” jest dość powszechne w programowaniu Prolog). Większość predykatów kończy się w ten sam sposób (jedynym powodem, dla którego nie działają, jest próba ich odwrócenia w celu utworzenia nieskończonej pętli, co jest dość powszechne).
1
@ ais523 -->i ogólnie DCG są standardowym Prologiem ISO .
Fatalize
5

Haskell, 101 94 bajtów

7 bajtów zapisanych przez 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<-["()","[]"]]

Prawie proste, zgodne z definicją, ale z ""przeniesioną obudową.

Posługiwać się:

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

(Drugie obliczenie zajmuje mniej niż sekundę na wolnym komputerze).

Chciałbym również podzielić się wynikiem innego podejścia, które wymyśliłem, myśląc o generowaniu funkcji. Definiuje listę b takich łańcuchów, która b!!nzawiera wszystkie łańcuchy nawiasów o długości n. Podobnie u!!nzawiera wszystkie atomy wielkości n-1. Jedną fajną rzeczą jest to, że kod nie używa żadnych cyfr. To nie jest całkowicie golfed: ui imogą być wstawiane, a to z pewnością nie zdobywa kilka innych możliwości gry w golfa. Niestety nie wygląda na to, że można go skrócić do pierwszej wersji, ale oblicza się length $ b !! 10jeszcze szybciej.

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)
Christian Sievers
źródło
Zaoszczędź dwa bajty za pomocą b$n-ki b$n-2. Również w ostatniej linii możesz zrobić a:b<-["()","[]"]i wrócić a:s++b.
Zgarb
Och, chciałem użyć, ["()","[]"]ale nie mogłem zobaczyć, jak poprawić rozmiar kodu. Dzięki!
Christian Sievers
4

Mathematica, 116 bajtów

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

Wyjaśnienie

Characters@"*([)]"

Znajdź znaki ciągu "*([)]", podając List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Znajdź krotki z powyższej listy o długości n.

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

Nienazwana funkcja boolowska, aby sprawdzić, czy krotka jest zrównoważona:

#/."*"->Nothing

Usuń wszystko "*"z wejścia.

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

Wielokrotnie usuwaj wszystkie kolejne wystąpienia "("i ")"lub "["i "]"dopóki dane wejściowe się nie zmienią.

... =={}

Sprawdź, czy wynik jest pusty List.

Select[ ... , ... ]

Znajdź krotki, które dają Truepo zastosowaniu funkcji boolowskiej.

#<>""&/@

Konwertuj każdy Listze znaków na Strings.

JungHwan Min
źródło
2
Nieoczekiwanie {x=a___,"(",")",y=b___}|{x,"[","]",y}wydaje się działać.
Martin Ender
4

Python 2, 128 bajtów

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

Przykręć rekursywne wyrażenia regularne - używamy parsera Pythona! Aby sprawdzić, na przykład, że *(**[])*jest to nawias klamrowy, wykonujemy następujące czynności:

  1. Utwórz ciąg podobny do tego "*", (0,"*","*", [0,0] ,0) ,"*", w którym co drugi czteroosobowy znak jest znakiem z nawiasów klamrowych, a pozostałe znaki są klejem, aby uczynić z niego potencjalne wyrażenie w języku Python.

  2. eval to.

  3. Jeśli nie spowoduje to błędu, wydrukuj s[1::4](znaki nawiasu klamrowego).

Do kleju znaki są zbierane tak, że ciąg robię jest poprawnym wyrażeniem Pythona tylko wtedy, gdy przy każdym drugi znak z czterech rentowności ważny klamra-strunowych.

Lynn
źródło
2

PHP, 149 bajtów

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

Używa starego dobrego generowania wszystkich możliwych, a następnie metody filtrowania. Użyj jak:

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
użytkownik59178
źródło
1

Python, 134 bajty

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

repl.it

Nienazwana funkcja, która zwraca listę prawidłowych ciągów długości n.
Formy wszystkie długość nkrotki bohaterów *()[], łączy je w ciągi korzystających map(''.join,...)i filtry do tych, które zostały zrównoważone nawiasy usuwając „parę” "*", "()"oraz "[]"z kolei nrazy i upewnieniu się, że wynik jest pustym ciągiem znaków ( nczas jest przesadą, zwłaszcza "*"jednak jest golfistą).

Jonathan Allan
źródło
1

Siatkówka , 78 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

A`;

Wypróbuj online!

Wyjaśnienie

Generuję wszystkie możliwe ciągi o długości 5, a następnie odfiltrowuję niepoprawne.

.+
$*

Konwertuje to wejście na jednoargumentowe, używając 1jako cyfry.

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

To wielokrotnie ( +) zastępuje pierwszy ( 1) jeden w każdej linii ( %) w taki sposób, że tworzy pięć kopii linii, po jednej dla każdego możliwego znaku. Odbywa się to za pomocą podstawień prefiksów i sufiksów $`oraz $'konstruowania reszty każdej linii.

Ta pętla zatrzymuje się, gdy nie ma już 1 do zastąpienia. W tym momencie mamy wszystkie możliwe ciągi długości N, po jednym w każdej linii.

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

Te dwa etapy są wykonywane osobno dla każdej linii ( %). Pierwszy etap po prostu powiela linię za pomocą; oddziela dwie kopie.

Drugi etap jest inny układ ( +), które wielokrotnie usuwa [], ()lub *z pierwszego kopię łańcucha, lub usuwa średnik na początku linii (co jest możliwe dopiero wtedy, gdy łańcuch jest całkowicie zniknął).

A`;

Prawidłowe ciągi to te, które nie mają już średnika przed nimi, więc po prostu odrzucamy wszystkie linie ( A) zawierające średnik.

Martin Ender
źródło
Próbowałem onliny z wejściem 5: ok. Z wejściem 6 dostałem stronę błędu
edc65
@ edc65 Działa dla mnie, ale oczywiście to podejście nie jest dokładnie skuteczne, więc zajmuje to kilka sekund. Jaki rodzaj strony błędu masz na myśli?
Martin Ender
Wejście 5: odpowiedź w ciągu 3 sekund Wejście 6: po 7 sekundach w polu Wyjście otrzymuję źródło html strony, która prawdopodobnie jest stroną błędu, z mojego serwera proxy. Jeśli jest to limit czasu, to jest to bardzo krótki limit czasu ... Próbowałem uzyskać odpowiedni przypadek testowy dla wejścia 6, ponieważ moja odpowiedź wydaje się być
poprawna
@ edc65 To zdecydowanie trwa dłużej niż 7 sekund, a limit czasu TIO wynosi minutę. Nigdy nie widziałem opisywanego błędu, być może warto go omawiać na czacie TIO (lub jeśli wolisz na Gitter lub GitHub ). Jeśli chodzi o dane wyjściowe, oto, co otrzymuję dla wejścia 6: pastebin.com/WmmPPmrc (Wejście 7 zajmuje więcej niż minutę.)
Martin Ender
1

Python 3.5, 146 bajtów

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

Bardzo długi w porównaniu z innymi odpowiedziami, ale najkrótszy, jaki udało mi się obecnie znaleźć. Ma on postać anonimowej funkcji lambda i dlatego musi być wywoływany w formacie

print(<Function Name>(<Integer>))

Wyjścia pytona zestawie z nieuporządkowanych ciągów reprezentujących wszystkie możliwe Brace-ciągi długości wejściowego.

Na przykład przy założeniu, że powyższa funkcja ma nazwę G, wywołanie G(3)spowoduje następujące wyniki:

{'[*]', '*()', '*[]', '(*)', '***', '[]*', '()*'}

Wypróbuj online! (Ideone)


Jeśli jednak, podobnie jak ja, nie jesteś fanem upraszczania rzeczy za pomocą wbudowanych funkcji, oto moja własna oryginalna odpowiedź, która nie korzysta z żadnych zewnętrznych bibliotek w celu znalezienia permutacji, a obecnie stoi na ogromnym poziomie 288 237 bajtów :

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

Ponownie, podobnie jak odpowiedź konkurencyjna, ta ma postać funkcji lambda i dlatego należy ją również wywołać w formacie

print(<Function Name>(<Integer>))

Python i wysyła listy z nieposortowane ciągów reprezentujących wszystkie Brace-ciągi długości wejściowego. Na przykład, jeśli lambda G(3)miałaby zostać wywołana jako , tym razem wynik byłby następujący:

['*()', '(*)', '*[]', '[*]', '()*', '[]*', '***']

Również ten jest również o wiele szybszy niż moja inna odpowiedź, będąc w stanie znaleźć wszystkie nawiasy klamrowe o długości 11w około 115 sekund , te o długości 10w około 19 sekund , o długości 9w około 4 sekundy i te o długości 8w około 0,73 sekundy na moim komputerze, podczas gdy moja konkurencyjna odpowiedź trwa znacznie dłużej niż 115 sekund na wprowadzenie 6.

Wypróbuj online! (Ideone)

R. Kap
źródło
0

05AB1E, 23 bajty

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

Niektóre z tych funkcji mogły zostać zaimplementowane po opublikowaniu pytania. Wszelkie sugestie są mile widziane!

Wypróbuj online!

W jaki sposób?

…[(* - 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ý
źródło
Nie znam 05AB1E, ale czy nie może *być również w tablicy usuwania? I czy õQczek można zastąpić czymś takim, jak NIE?
Esolanging Fruit
Pierwsza sugestia nie zapisuje żadnych bajtów: '*м„()„[]‚õ:vs „()„[]‚'*«õ:(nie testowane), ponieważ nie ma polecenia konkatenacji 3 wartości AFAIK. Drugi nie zadziała, ponieważ nie ma takiego, który działałby tak na łańcuchu, AFAIK. (Gdzie AFAIK reprezentuje „o ile mi wiadomo”)
Zacharý