Znajdź pierwszy mecz w nawiasie

22

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 , wygrywa najmniej bajtów!

Pavel
źródło
3
Punkty bonusowe, jeśli odpowiesz w Brain-Flak ofc :)
Erik the Outgolfer
1
@EriktheOutgolfer Done
DJMcMayhem
1
Ta technika jest bardzo pomocna przy pisaniu nieefektywnych implementacji BF.
Esolanging Fruit

Odpowiedzi:

2

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
DJMcMayhem
źródło
Czy nie potrzebujesz płyty kotłowej do dopasowania <>?
Pavel
@Pavel In vim, tak. Ale nie w V.
DJMcMayhem
27

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
<>)
DJMcMayhem
źródło
8
Na miłość boską, co to jest na ziemi.
Leaky Nun
Zasadniczo wszyscy teraz używają n-1&2/ n+1&2/ -n&2lub n%7&2do rozróżnienia nawiasów otwierających i zamykających ...
ETHproductions
@ETHproductions Nie jestem pewien, czy atak mózgu może skutecznie obliczać &2, ale przyjrzę się temu.
DJMcMayhem
Och, myślałem, że jesteś. Musisz robić coś podobnego, aby odróżnić 0/ 1i 2/ 3... chociaż teraz, kiedy na to patrzę, zmniejszasz się, jeśli jesteś pozytywny. Świetna sztuczka :-)
ETHproductions
1
(TOS+1)%4Może być krótszy: Spróbuj online!
MegaTom
11

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
Riley
źródło
žuwydaje się użyteczna tutaj.
Magic Octopus Urn
žu8ÝÈÏwięc nie, nie bardzo lol. W najlepszym razie będzie to nadal 5 bajtów. Myślałem bardziej o podziale na pary nawiasów klamrowych i usuwaniu nawiasów klamrowych, dopóki nie pozostanie tylko jedna para, licznik przyrostów o 2 dla każdej usuniętej pary. Nie mam pojęcia, czy to mniej. Wypróbowanie bankomatu.
Magic Octopus Urn
Do 10 bajtów: Ç>2&<.pO0k.
Adnan
1
Po prostu bawisz się wartościami ASCII. Zauważ, że po zwiększeniu, drugi ostatni bit dotyczy 0wspornika otwierającego i 1zamykającego.
Adnan
11

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
DJMcMayhem
źródło
1
Opublikuj odpowiedź V wtedy :)
Erik the Outgolfer
10

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.


źródło
Fascynujące, jak przyjęliśmy podobne podejście do wykrywania nawiasów zamykających. Niestety znalazłem tylko gorszą wersję:b*2%7>3
2501
Ciekawe podejście! Opracowałem dłuższą odpowiedź (do ćwiczenia), którą w końcu grałem w golfa praktycznie do tego, tyle że co ciekawe, zamiast pierwszego spadku w twoim poście, zamiast tego miałem przyrost. :)
HyperNeutrino
9

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.

Martin Ender
źródło
To wspaniale!
Pavel
Krótsze podejście : usuń drugą część ciągu zamiast dopasowywać pierwszą część. Podoba mi się, jak zmierzyłeś długość sznurka, btw!
Leo
@Leo To naprawdę miłe! Możesz to opublikować jako osobną odpowiedź :)
Martin Ender
Ok, ta nowa sztuczka dla zrównoważonych strun jest cudowna: D
Leo
6

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.

Lew
źródło
Znalazłem wczoraj nową technikę dopasowywania zbalansowanych ciągów, która oszczędza dwa bajty na obu naszych odpowiedziach: tio.run / ##K0otycxL / K@q4Z7wX0 / D3kbX0E4jOlqj2iZWU0tPU0uFi@v/... (i prawdopodobnie kilkanaście innych, które napisałem w przeszłość ...)
Martin Ender
5

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

Dada
źródło
4

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

ETHprodukcje
źródło
Myślę, że zamiast n-1&2, -n&2współpracuje również?
Adnan
@Adnan Hmm, myślę, że masz rację. Dzięki!
ETHprodukcje
4

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.

2501
źródło
4

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)
acidtobi
źródło
1
Witamy na stronie!
DJMcMayhem
1
Nie musisz nazywać lambdas, możesz usunąć g =
Pavel
4

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.

MegaTom
źródło
3

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.

Martin Ender
źródło
Widziałem, że odpowiedziałeś na stronie głównej i wiedziałem, że użyje jakiegoś wyrażenia regularnego
Christopher
@Christopher Eh, ten w ogóle nie używa żadnego wyrażenia regularnego (w przeciwieństwie do drugiej odpowiedzi Retiny, którą właśnie opublikowałem ...).
Martin Ender
Do licha. Regex dużo?
Christopher
Dlaczego nie jest to działa?
Leaky Nun
@LeakyNun Ponieważ (?!(2))jest po prostu (?!2). Prawdopodobnie miałeś na myśli (?(2)(?!))lub (?2)!). Zapomniałeś także o ucieczce ]i ostateczna +musi być *.
Martin Ender
2

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

Jörg Hülsermann
źródło
Czy PHP nie musi zaczynać <?php?
Pavel
@Phoenix: Istnieje samodzielny interpreter PHP, który nie wymaga tagu początkowego. Tak zwykle gra się w golfa.
@ ais523 W tym przypadku PHP działa z wiersza polecenia z opcją -R
Jörg Hülsermann
2

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!

Jonathan Allan
źródło
2

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
Ray Hamel
źródło
2
Witamy w PPCG!
Pavel
1
Bardzo mile widziane! :)
Ray Hamel 30.04.17
2

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!

Dennis
źródło
1

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.

Neil
źródło
1

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}
Neil
źródło
0

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   [[]<>[]]
Khaled.K
źródło
Wszelkie komentarze, downvoter.
Khaled.K
Nie byłem downvoter, ale nie sądzę, żeby to pomogło, że składanie C było już znacznie krótsze.
Ørjan Johansen