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 n
przyjmuje 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 golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .
Przypadki testowe
0.
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
code-golf
balanced-string
Esolanging Fruit
źródło
źródło
Odpowiedzi:
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ć!
Wypróbuj online!
Poprzednie rozwiązania miałem:
Objaśnienie (Moja najlepsza próba opisu):
źródło
“[(*)]”ṗµḟ”*œṣ⁾()Fœṣ⁾[]FµÐLÐḟ
)Prolog, 69 bajtów
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),
b
któ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 samymb
), tak aby dopasować każdy nawias „ciąg” w dokładnie jeden sposób (co jest powodem, że zarównos
ie
muszą istnieć, zamiast grupując je w jednym orzecznika). To sprawia, że oba są całkowicie odwracalne; dlategob
moż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:
źródło
length
iappend
na odwrót jest podstawową częścią języka, a funkcje użytkownika często robią to samo.length(A,N)
; ifN
jest podane iA
nie jest (co stanie się, jeśli predykat zostanie użyty w sposób wymagany w programie),length
wygeneruje listęA
składającą się zN
nieznanych elementów. Używanielength
do 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).-->
i ogólnie DCG są standardowym Prologiem ISO .Haskell,
10194 bajtów7 bajtów zapisanych przez Zgarb!
Prawie proste, zgodne z definicją, ale z
""
przeniesioną obudową.Posługiwać się:
(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órab!!n
zawiera wszystkie łańcuchy nawiasów o długościn
. Podobnieu!!n
zawiera wszystkie atomy wielkościn-1
. Jedną fajną rzeczą jest to, że kod nie używa żadnych cyfr. To nie jest całkowicie golfed:u
ii
mogą 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 !! 10
jeszcze szybciej.źródło
b$n-k
ib$n-2
. Również w ostatniej linii możesz zrobića:b<-["()","[]"]
i wrócića:s++b
.["()","[]"]
ale nie mogłem zobaczyć, jak poprawić rozmiar kodu. Dzięki!Mathematica, 116 bajtów
Wyjaśnienie
Znajdź znaki ciągu
"*([)]"
, podającList
{"*", "(", "[", ")", "]"}
.Znajdź krotki z powyższej listy o długości
n
.Nienazwana funkcja boolowska, aby sprawdzić, czy krotka jest zrównoważona:
Usuń wszystko
"*"
z wejścia.Wielokrotnie usuwaj wszystkie kolejne wystąpienia
"("
i")"
lub"["
i"]"
dopóki dane wejściowe się nie zmienią.Sprawdź, czy wynik jest pusty
List
.Znajdź krotki, które dają
True
po zastosowaniu funkcji boolowskiej.Konwertuj każdy
List
ze znaków naString
s.źródło
{x=a___,"(",")",y=b___}|{x,"[","]",y}
wydaje się działać.Python 2, 128 bajtów
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: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.eval
to.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.
źródło
PHP, 149 bajtów
Używa starego dobrego generowania wszystkich możliwych, a następnie metody filtrowania. Użyj jak:
źródło
Python, 134 bajty
repl.it
Nienazwana funkcja, która zwraca listę prawidłowych ciągów długości
n
.Formy wszystkie długość
n
krotki bohaterów*()[]
, łączy je w ciągi korzystającychmap(''.join,...)
i filtry do tych, które zostały zrównoważone nawiasy usuwając „parę”"*"
,"()"
oraz"[]"
z kolein
razy i upewnieniu się, że wynik jest pustym ciągiem znaków (n
czas jest przesadą, zwłaszcza"*"
jednak jest golfistą).źródło
Siatkówka , 78 bajtów
Liczba bajtów zakłada kodowanie ISO 8859-1.
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
1
jako cyfry.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ął).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.źródło
Python 3.5, 146 bajtów
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łanieG(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
288237 bajtów :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
11
w około 115 sekund , te o długości10
w około 19 sekund , o długości9
w około 4 sekundy i te o długości8
w około 0,73 sekundy na moim komputerze, podczas gdy moja konkurencyjna odpowiedź trwa znacznie dłużej niż 115 sekund na wprowadzenie6
.Wypróbuj online! (Ideone)
źródło
05AB1E, 23 bajty
Niektóre z tych funkcji mogły zostać zaimplementowane po opublikowaniu pytania. Wszelkie sugestie są mile widziane!
Wypróbuj online!
W jaki sposób?
źródło
*
być również w tablicy usuwania? I czyõQ
czek można zastąpić czymś takim, jak NIE?'*м„()„[]‚õ:
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”)