Było to jedno z szeregu wyzwań poprzedzających urodziny Brain-Flaka. Dowiedz się więcej tutaj .

Wyzwanie

W tym wyzwaniu Twoim celem będzie znalezienie pierwszej pary pasujących nawiasów w całkowicie dopasowanym ciągu ()[]{}<>nawiasów. Aby pożyczyć definicję w pełni dopasowanego ciągu DJMcMayhem :

• Dla celów niniejszego wyzwanie, „uchwyt” jest każdy z tych znaków: ()[]{}<>.

• Para nawiasów jest uważana za „dopasowaną”, jeśli nawiasy otwierające i zamykające są w odpowiedniej kolejności i nie zawierają w sobie znaków, takich jak

  ()
  []{}
  

  Lub jeśli każdy podelement w nim również jest dopasowany.

  [()()()()]
  {<[]>}
  (()())
  

  Elementy podrzędne mogą być również zagnieżdżone na kilku warstwach.

  [(){<><>[()]}<>()]
  <[{((()))}]>
  

• Sznurek jest uważany za „w pełni dopasowany” wtedy i tylko wtedy, gdy każda para wsporników ma prawidłowy otwierający i zamykający wspornik we właściwej kolejności.

Wkład

Dane wejściowe będą składały się z pojedynczego niepustego łańcucha znaków lub tablicy znaków zawierającej tylko znaki ()[]{}<>i gwarantuje się, że zostaną w pełni dopasowane. Możesz przyjmować dane wejściowe w dowolny rozsądny sposób, który odpowiada naszym ustawieniom domyślnym we / wy .

Wydajność

Wyjście twojego programu lub funkcji będzie indeksem nawiasu, który zamyka pierwszy. Wyjście musi być 0lub 1indeksowane. Ponownie, wyjście może być w dowolny rozsądny sposób, który odpowiada naszym domyślnym ustawieniom we / wy .

Przypadki testowe

Input       0-indexed   1-indexed
()          1           2
(<>)        3           4
<[]{<>}>    7           8
{}{}{}{}    1           2
[[]<>[]]    7           8

To jest golf golfowy , wygrywa najmniej bajtów!

V , 4 bajty

%Dø.

Wypróbuj online!

To, w przeciwieństwie do większości odpowiedzi V, wykorzystuje indeksowanie 0. Jestem niezwykle dumny z tej odpowiedzi i tego, jak daleko zaszedł mój język. Wyjaśnienie:

%       " Jump to the first bracket match
 D      " Delete everything under and after the cursor
  ø     " Count the number of times the following regex is matched:
   .    "   Any character

Brain-Flak , 685, 155, 151 , 137 bajtów

(())({<{}({}()<(()()()())>)({}(<>))<>{(({})){({}[()])<>}{}}{}<>
([{}()]{})(({})){{}({}[()])(<()>)}{}(<>)<>{{}<>{}({}<>)}{}(<>[]<>)>()}<>)

Wypróbuj online!

136 bajtów kodu plus jeden bajt dla -a. Jeden zindeksowany.

530 bajtów grało w golfa! To chyba największy golf, jaki kiedykolwiek zrobiłem.

14 bajtów zapisanych dzięki Riley!

To narusza formułę nawiasu otwierającego / zamykającego: jeśli weźmiesz wartości ASCII, zwiększysz je o jeden i weź modulo 4, otwieracze ( ({[<) zawsze otrzymają 0lub 1, a zamykacze ( )}]>) zawsze otrzymają 2 lub 3.

Wyjaśnienie:

#Push 1
(())

#While true
({<

    #Pop stack height
    {}

    #Compute (TOS + 1) % 4
    ({}()<(()()()())>)({}(<>))<>{(({})){({}[()])<>}{}}{}<>([{}()]{})

    #Decrement if positive
    (({})){{}({}[()])(<()>)}{}

    #Push 0 onto alternate
    (<>)

    #Toggle back
    <>

    #Pop two zeros from alternate if closer
    {{}<>{}({}<>)}{}

    #Push height of alternate stack
    (<>[]<>)

#Make each time through evaluate to 1
>()

#Endwhile
}

#Push the number of loops onto the offstack
<>)

05AB1E , 17 16 10 bajtów

-1 dzięki carusocomputing

-6 dzięki Adnanowi za jego niesamowity wgląd w to, że „po zwiększeniu drugi bit to 0 dla nawiasu otwierającego i 1 dla nawiasu zamykającego”

Ç>2&<.pO0k

Wypróbuj online!

Ç          # Get input as ASCII values
 >         # Increment
  2&       # And with 2 (0 for open and 2 for close brackets)
    <      # decrement 
     .p    # prefixes
       O   # Sum
        0k # Print the index of the first 0

Vim, 23 bajty

:se mps+=<:>
%DVr<C-a>C1<esc>@"

Wypróbuj online!

Bardzo mi przykro z powodu tej odpowiedzi. To rozwiązanie jest pięknie eleganckie i krótkie, ale domyślnie vim nie bierze pod uwagę <i nie >należy go dopasowywać, więc potrzebuję 13 bajtów kodu typu Boiler Plate. W przeciwnym razie byłoby to tylko 10 bajtów.

Chciałbym opublikować odpowiedź V, ale byłby to tylko jeden bajt krótszy, mianowicie zmiana Vrna Ò, ponieważ Vrjest to powszechny idiom.

Jest to indeksowane 1, ale może być w trywialny sposób modyfikowane, aby było indeksowane 0 poprzez zmianę na 1a 0.

:se mps+=<:>        " Stupid boilerplate that tells vim to consider `<` and `>` matched
%                   " Jump to the bracket that matches the bracket under the cursor
 D                  " Delete everything from here to the end of the line
  V                 " Visually select this whole line
   r<C-a>           " Replace each character in this selection with `<C-a>`
                    " This conveniently places the cursor on the first char also
         C          " Delete this whole line into register '"', and enter insert mode
          1<esc>    " Enter a '1' and escape to normal mode
                @"  " Run the text in register '"' as if typed. Since the `<C-a>` command
                    " Will increment the number currently under the cursor

Galaretka , 11 10 9 bajtów

O’&2’+\i0

Wypróbuj online!

Wyjaśnienie

Pomysł polegał na znalezieniu „magicznej formuły”, która odróżniałaby otwieranie od nawiasów zamykających. Pierwotnie użyłem O%7&2(tj. „Weź kod ASCII, modulo 7, bitowe-i 2”), ale sugerowałem @ETHproductions O’&2(który zastępuje modulo 7 zmniejszeniem); oba zwracają 0 dla jednego rodzaju nawiasu i 2 dla drugiego. Odejmowanie 1 ( ’) spowoduje, że wyniki te będą równe -1 i 1.

Reszta kodu to +\. +\tworzy łączną sumę. Jeśli zestaw nawiasów jest poprawnie dopasowany, będzie zawierał tę samą liczbę -1 i 1s, tzn. Jego suma będzie wynosić 0. Następnie wystarczy zwrócić indeks pierwszego 0 na wynikowej liście; możemy to zrobić za pomocą i0.

Siatkówka , 26 24 bajtów

M!`^.(?<-1>([[({<])*.)*

Wypróbuj online!

Wynik jest oparty na 1.

Wyjaśnienie

Zupełnie inne rozwiązanie Retina, które zasadniczo opiera się na jednym (i bardzo czytelnym ...) wyrażeniu regularnym. Wykorzystuje nową technikę, którą odkryłem wczoraj, do dopasowywania zrównoważonych ciągów za pomocą grup równoważących .

M!`^.(?<-1>([[({<])*.)*

Znajdź ( M) i return ( !) wszystkie dopasowania wyrażenia regularnego ^.(?<-1>([[({<])*.)*. Wyrażenie regularne pomija pierwszy znak ciągu, a następnie używa grup równoważących do śledzenia głębokości zagnieżdżenia. Każda z [({<wzrostem głębokości (śledził przez grupę 1) i każda inna postać zmniejsza głębokość (w zasadzie .pozwala na głębokość być zmniejszona przez nawiasach otwierających jak dobrze, ale ponieważ regex jest dopasowany łapczywie The backtracker nigdy nie próbować, że ). Dziwną sztuczką jest to, że (?<-1>...)otacza grupę, 1która działa, ponieważ wyskakiwanie z grupy równoważącej odbywa się na końcu grupy. To oszczędza dwa bajty w stosunku do standardowego podejścia w formularzu((open)|(?<-2>close))*. Mecz koniecznie kończy się na wsporniku, który zamyka pierwszy, ponieważ go pominęliśmy, więc nie jest uwzględniany na głębokości stosu (a głębokość stosu nie może być ujemna).

Długość tego dopasowania jest indeksem nawiasu, którego szukamy.

Po prostu policz liczbę pustych dopasowań w tym ciągu. Pusty wyrażenie regularne zawsze pasuje raz, niż w łańcuchu są znaki, więc daje nam to indeks 1 nawiasu, którego szukamy.

Siatkówka , 24 bajty

.(([[({<])|(?<-2>.))*$

Wypróbuj online!

Jest to inspirowane rozwiązaniem Martina Endera .

Wyjaśnienie

Pierwszy wiersz to wyrażenie pasujące do znaku, po którym następuje zrównoważony ciąg znaków prowadzący do końca łańcucha głównego (szczegółowe wyjaśnienie, w jaki sposób grupy równoważące są używane w tym wyrażeniu, patrz odpowiedź Martina). Ponieważ wyrażenia regularne szukają dopasowań od lewej do prawej, znajdzie to najdłuższy zrównoważony prawidłowy podrostek, czyli wszystko po nawiasie zamykającym pierwszy plus sam nawias.

Poniższy wiersz jest pusty, więc zastępujemy dopasowanie pustym łańcuchem, co oznacza, że ​​teraz musimy tylko policzyć pozostałe znaki, aby uzyskać pożądany (0-indeksowany) wynik.

Ostatni pusty wiersz zlicza liczbę dopasowań pustego ciągu w ciągu, który jest o jeden większy niż liczba znaków w ciągu, co odpowiada wynikowi o indeksie 1.

Perl 5 , 28 bajtów

Zaoszczędzono 6 bajtów, używając tylko .zamiast [>})\]], z odpowiedzi Retina Martina Endera .

27 bajtów kodu + -pflaga.

/([<{([](?0)*.)+?/;$_=$+[0]

Wypróbuj online!

Recursive regex, co za piękny wynalazek.
Wyrażenie regularne szuka nawiasu otwierającego ( [<{([]), po którym następuje wywołanie rekurencyjne ( ?0), a następnie nawiasu zamykającego ( .). Wszystko to nie jest zachłanne ( +?), więc od początku pasuje tak krótko, jak to możliwe. Indeks końca meczu jest odpowiedzią i jak się zdarza, można go znaleźć w $+[0].

JavaScript (ES6), 55 53 52 bajty

Zapisano 1 bajt dzięki @Adnan

f=([c,...s],i=1)=>(i-=-c.charCodeAt()&2)&&1+f(s,++i)

Przy każdym nawiasie otwierającym pobranie modu char-code 4 daje nam 0 lub 3; dla nawiasów zamykających daje nam 1 lub 2. Dlatego możemy rozróżnić nawiasy otwierające i zamykające, negując kod znakowy nawiasu (który odwraca bity i odejmuje 1) i biorąc drugi najmniej znaczący bit; to jest n&2,.

C, 75 72 56 55 54 45 bajtów

a;f(char*s){return(a-=(-*s++&2)-1)?1+f(s):0;}

Zobacz, jak działa online .

Jeśli chcesz być wyjście do 1 indeksowane zamiast 0 indeksowane, wymienić ostatnią 0z 1.

Python 2.7 + Numpy, 85 79 bajtów

Moja pierwsza próba kodowania golfa:

from numpy import*
lambda s:list(cumsum([(ord(x)+1&2)-1for x in s])).index(0)

Brain-Flak , 97 bajtów (96 dla kodu, 1 dla flagi)

{}<>(())({<(<()>)<>({<({}[()])><>([{}]())<>}{})<>(<{}>())<>{({}[()])<>([{}])<>}{}<>({}{})>()}{})

Uruchom z -aflagą.

Wypróbuj online!

Wyjaśnienie:

#Skip the first open bracket 
{}

#Place a 1 on stack B, representing the nesting depth
<>(())

#Start a loop, until the depth is 0
({<

 #Divide the ASCII code by 2, rounding up
 (<()>)<>({<({}[()])><>([{}]())<>}{})<>

 #Replace TOS B with a 1
 (<{}>())

 #Swap back to stack A
 <>

 #Negate the 1 on stack B n times (n = ASCII value+1/2)
 {({}[()])<>([{}])<>}{}

 #Swap back to stack B
 <>

 #Add the 1/-1 (depending on Open/close bracket) to the nesting depth accumulator
 ({}{})

 #Count loop cycles
 >()

#end loop, print result implicitly by pushing to the stack 
}{}) 

Po prostu działa, dobrze.

Retina , 34 bajty

^.
!
T`([{}])`<<<>
+T`p`!`<!*>
\G!

Wypróbuj online!

Wynik jest oparty na 0.

Wyjaśnienie

^.
!

Zamień pierwszy znak na !. To powoduje, że nawias, którego szukamy, nie ma sobie równych.

T`([{}])`<<<>

Konwertuj nawiasy, nawiasy kwadratowe i nawiasy klamrowe na nawiasy kątowe. Ponieważ ciąg znaków jest w pełni dopasowany, w ogóle nie dbamy o rzeczywiste typy, a to oszczędza niektóre bajty w następnym kroku.

+T`p`!`<!*>

Wielokrotnie ( +) zastąpić każdy znak we wszystkich meczów <!*>z !s. Oznacza to, że dopasowujemy pary nawiasów, które nie zawierają żadnych nieprzetworzonych nawiasów, i przekształcamy je w dalsze wykrzykniki. Spowoduje to obrócenie całego łańcucha oprócz niedopasowanego nawiasu zamykającego w wykrzykniki.

\G!

Policz liczbę wiodących wykrzykników, która jest równa zerowej pozycji pierwszego nie wykrzyknika (tzn. Niedopasowanego nawiasu). Każda \Gkotwica pasuje do poprzedniej, dlatego nie liczy się !s po tym nawiasie.

PHP, 116 bajtów

for($l=["("=>")","["=>"]","{"=>"}","<"=>">"][$f=$argn[0]];;$d>0?$i++:die("$i"))$d+=$f!=($n=$argn[$i])?$n==$l?-1:0:1;

Wersja online

Python , 76 bajtów

f=lambda s,r=[],i=0:(i<1or sum(r))and f(s[1:],r+[(ord(s[0])+1&2)-1],i+1)or i

Funkcja rekurencyjna, która używa porządkowego drugiego LSB jako flagi dla sztuczki open vs close używanej przez wielu znalezionych przez Adnana (i prawdopodobnie innych). Ogon uderza, gdy skumulowana suma -1dla otwarcia i 1dla zamknięcia osiągnie zero. Indeks jest przechowywany w zmiennej, ponieważ jest tańszy bajtowo niż przy użyciu len(r), indeksowanie jest oparte na 1.

Wypróbuj online!

Rubin, 35 34 bajtów

p$_[/[<{(\[](\g<0>)*[>})\]]/].size

Na podstawie odpowiedzi Perl5 autorstwa Dady . Dane wyjściowe są indeksowane 1. Wymaga wywołania interpretera Ruby z -nopcją (niejawna while getspętla).

Edycja: Jest to również 35 34 bajtów, ale jest kolejnym możliwym punktem wyjścia do dalszego ograniczenia tej odpowiedzi.

p$_[/[<{(\[](\g<0>)*[>})\]]/]=~/$/

Edycja2: Usunięto niepotrzebne spacje po p.

Edycja3: Kilka dodatkowych 34-bajtowych odpowiedzi.

~/[<{(\[](\g<0>)*[>})\]]/;p$&.size
p~/[<{(\[](\g<0>)*[>})\]]/+$&.size

Python 3 , 59 55 50 49 bajtów

f=lambda s,n=1:n and-~f(s[1:],n+1-(-ord(s[1])&2))

Wyjście jest indeksowane na 0. Formuła określająca kierunek nawiasu została po raz pierwszy odkryta przez @ETHProductions i ulepszona przez @Adnan.

Wypróbuj online!

Partia, 172 bajty

@set/ps=
@set/ai=d=0
:l
@set/ai+=1,d-=1
@set c="%s:~,1%"
@set "s=%s:~1%
@for %%a in ("<" "(" "[" "{")do @if %%a==%c% set/ad+=2&goto l
@if %d% gtr 0 goto l
@echo %i%

1-indeksowany. <>s są oczywiście znakami specjalnymi w Batch, więc nie tylko muszę zacytować wszystko, ale nawet nie mogę wykonywać takich sztuczek, jak tworzenie gotoetykiet.

R, 126 bajtów

s=readline();i=0;r=0;for(c in strsplit(s,"")[[1]]){if(grepl("[\\[\\(\\{<]",c))i=i+1 else i=i-1;if(i==0){print(r);break};r=r+1}

C, 127 bajtów

Wypróbuj online

c(x){x-40&x-60&x-91&x-123?-1:1;}
f(i,t)char*t;{return i?f(i+c(*t),t+1):t;}
s(char*t){return f(c(*t),t+1)-t;}

Wydajność

2   ()
4   (<>)
8   <[]{<>}>
2   {}{}{}{}
8   [[]<>[]]