Finde das erste Bracket Match

22

Dies war eine von mehreren Herausforderungen, die zum Geburtstag von Brain-Flak führten. Mehr aus hier .

Herausforderung

Für diese Herausforderung besteht Ihr Ziel darin, das allererste Paar übereinstimmender Klammern in einer vollständig übereinstimmenden Klammerreihe zu finden ()[]{}<>. So leihen Sie die Definition von DJMcMayhem für eine vollständig übereinstimmende Zeichenfolge aus:

  • Für die Zwecke dieser Herausforderung ist eine „Klammer“ eines dieser Zeichen: ()[]{}<>.

  • Ein Klammerpaar wird als "übereinstimmend" betrachtet, wenn die öffnende und schließende Klammer in der richtigen Reihenfolge sind und keine Zeichen enthalten, z

    ()
    []{}
    

    Oder wenn jedes Unterelement in ihm auch übereinstimmt.

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

    Unterelemente können auch mehrere Ebenen tief verschachtelt sein.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Eine Zeichenfolge wird nur dann als "vollständig passend" betrachtet, wenn jedes Klammerpaar die richtige öffnende und schließende Klammer in der richtigen Reihenfolge aufweist.

Eingang

Die Eingabe besteht aus einer einzelnen nicht leeren Zeichenfolge oder einem Zeichen-Array, das nur die Zeichen enthält ()[]{}<>, und es wird garantiert, dass sie vollständig übereinstimmt. Sie können Eingaben in einer angemessenen Weise vornehmen, die unseren E / A-Standardwerten entspricht .

Ausgabe

Die Ausgabe Ihres Programms oder Ihrer Funktion ist der Index der Klammer, die die erste schließt. Die Ausgabe muss entweder 0oder 1indiziert sein. Auch hier kann die Ausgabe in einer angemessenen Weise erfolgen, die unseren E / A-Standardwerten entspricht .

Testfälle

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

Das ist , die wenigsten Bytes gewinnen!

Pavel
quelle
3
Bonuspunkte, wenn Sie in Brain-Flak ofc antworten :)
Erik the Outgolfer
1
@EriktheOutgolfer Done
DJMcMayhem
1
Diese Technik ist sehr hilfreich, um ineffiziente Implementierungen von BF zu schreiben.
Esolanging Fruit

Antworten:

2

V , 4 Bytes

%Dø.

Probieren Sie es online!

Dies verwendet im Gegensatz zu den meisten V-Antworten eine 0-Indizierung. Ich bin sehr stolz auf diese Antwort und wie weit meine Sprache gekommen ist. Erläuterung:

%       " 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
quelle
Gibt es nicht ein Kochfeld, das Sie für die Suche nach <> benötigen?
Pavel
@Pavel In vim, ja. Aber nicht in V.
DJMcMayhem
27

Brain-Flak , 685, 155, 151 , 137 Bytes

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

Probieren Sie es online!

136 Byte Code plus ein Byte für -a. Einer indiziert.

530 Bytes abgeschlagen! Das ist wahrscheinlich das größte Golf, das ich je gemacht habe.

14 Bytes gespart dank Riley!

Dies missbraucht eine Formel der öffnenden / schließenden Klammer: Wenn Sie die ASCII-Werte nehmen, um eins erhöhen und Modulo 4 annehmen, erhalten die openers ( ({[<) immer 0oder 1, wohingegen die closers ( )}]>) immer 2 oder 3 erhalten.

Erläuterung:

#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
quelle
8
Was um alles in der Welt ist das, aus Liebe zu Gott?
Undichte Nonne
Grundsätzlich verwendet jetzt jeder n-1&2/ n+1&2/ -n&2oder n%7&2, um öffnende und schließende Klammern zu unterscheiden ...
ETHproductions
@ETHproductions Ich bin mir nicht sicher, ob Brain-Flak effizient rechnen kann &2, aber ich werde es untersuchen.
DJMcMayhem
Oh, ich dachte du wärst es. Sie müssen etwas Ähnliches tun, um zwischen 0/ 1und 2/ zu unterscheiden 3... obwohl Sie jetzt, wo ich es mir anschaue, nur dekrementieren, wenn es positiv ist. Ein cooler Trick auch :-)
ETHproductions
1
Das (TOS+1)%4kann kürzer sein: Probieren Sie es online!
MegaTom
11

05AB1E , 17 16 10 Bytes

-1 dank carusocomputing

-6 danke an Adnan für seine erstaunliche Einsicht, dass "nach dem Inkrementieren das vorletzte Bit 0 für eine öffnende Klammer und 1 für eine schließende Klammer ist"

Ç>2&<.pO0k

Probieren Sie es 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
quelle
žuscheint hier verwendbar.
Magic Octopus Urn
žu8ÝÈÏAlso, nein, nicht wirklich lol. Bestenfalls sind es noch 5 Bytes. Ich dachte mehr über eine Aufteilung in Klammerpaare nach und entferne Klammern, bis nur noch ein Paar übrig ist, und erhöhe den Zähler für jedes entfernte Paar um 2. Ich habe keine Ahnung, ob das weniger ist. Probieren Sie es aus atm.
Magic Octopus Urn
Für 10 Bytes Ç>2&<.pO0k.
Adnan
1
Einfach mal mit den ASCII-Werten rumspielen. Beachten Sie, dass das vorletzte Bit nach dem Inkrementieren 0für eine öffnende und 1eine schließende Klammer gilt.
Adnan
11

Vim, 23 Bytes

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

Probieren Sie es online!

Ich bin sehr traurig über diese Antwort. Diese Lösung ist wunderschön elegant und kurz, aber standardmäßig berücksichtigt <und muss vim nicht >angepasst werden, sodass ich 13 Byte Boilerplate-Code benötige. Andernfalls wären dies nur 10 Bytes.

Ich hätte eine V Antwort geschrieben, aber das wäre nur ein Byte kürzer, nämlich seinen Wechsel Vrzu Ò, da Vrein gemeinsames vim-Idiom ist.

Dies ist 1-indiziert, kann aber durch Ändern von 1in a trivial modifiziert werden, um 0-indiziert zu werden 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
quelle
1
Dann
schreibe
10

Jelly , 11 10 9 Bytes

O’&2’+\i0

Probieren Sie es online!

Erläuterung

Die Idee dabei war, eine "Zauberformel" zu finden, die das Öffnen von schließenden Klammern unterscheiden kann. Ich habe ursprünglich verwendet O%7&2(dh "nimm den ASCII-Code, Modulo 7, bitweise-und 2"), aber @ETHproductions schlug vor O’&2(was das Modulo 7 durch ein Dekrement ersetzt); Beide geben 0 für eine Art von Klammer und 2 für die andere zurück. Durch Subtrahieren von 1 ( ) werden diese Ergebnisse zu -1 und 1.

Der Rest des Codes ist +\. +\ergibt eine kumulative Summe. Wenn ein Satz von Klammern korrekt übereinstimmt, enthält er die gleiche Anzahl von -1s und 1s, dh seine kumulative Summe ist 0. Dann müssen wir nur den Index der ersten 0 in der resultierenden Liste zurückgeben; das schaffen wir mit i0.


quelle
Faszinierend, wie wir bei der Erkennung von schließenden Klammern einen ähnlichen Ansatz gewählt haben. Leider habe ich nur eine minderwertige Version gefunden:b*2%7>3
2501
Interessanter Ansatz! Ich entwickelte eine längere Antwort (zum Üben), auf die ich schließlich praktisch zurückgegriffen habe, außer interessanterweise, anstatt des ersten Dekrements in Ihrem Beitrag, hatte ich stattdessen ein Inkrement. :)
HyperNeutrino
9

Retina , 26 24 Bytes

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

Probieren Sie es online!

Ergebnis ist 1-basiert.

Erläuterung

Eine ganz andere Retina-Lösung, die im Wesentlichen auf einer einzigen (und sehr gut lesbaren ...) Regex basiert. Dies verwendet eine neue Technik, die ich gestern entdeckt habe, um ausgeglichene Saiten mit Hilfe von Ausgleichsgruppen abzugleichen .

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

Finde ( M) und gib ( !) alle Übereinstimmungen des regulären Ausdrucks zurück ^.(?<-1>([[({<])*.)*. Dieser reguläre Ausdruck überspringt das erste Zeichen der Zeichenfolge und verwendet dann Ausgleichsgruppen, um die Verschachtelungstiefe zu verfolgen. Durch [({<Erhöhen der Tiefe (nach Gruppen verfolgt 1) und jedes andere Zeichen wird die Tiefe verringert (im Prinzip .kann die Tiefe auch durch Öffnen von Klammern verringert werden, aber da die Regex gierig übereinstimmt, wird der Backtracker dies niemals versuchen ). Der seltsame Trick ist, dass die (?<-1>...)einschließende Gruppe 1funktioniert, weil das Herausspringen aus einer Bilanzgruppe am Ende der Gruppe erfolgt. Dies spart zwei Bytes gegenüber dem Standardansatz im Formular((open)|(?<-2>close))*. Die Übereinstimmung endet notwendigerweise an der Klammer, die die erste schließt, da wir sie übersprungen haben, sodass sie in der Stapeltiefe nicht berücksichtigt wird (und die Stapeltiefe nicht negativ werden kann).

Die Länge dieser Übereinstimmung ist der auf 0 basierende Index der gesuchten Klammer.


Zählen Sie einfach die Anzahl der leeren Übereinstimmungen in dieser Zeichenfolge. Der leere reguläre Ausdruck stimmt immer wieder überein, wenn Zeichen in der Zeichenfolge vorhanden sind. Dies gibt uns den 1-basierten Index der gesuchten Klammer.

Martin Ender
quelle
Das ist hervorragend!
Pavel
Kürzere Vorgehensweise : Löschen Sie den zweiten Teil der Zeichenfolge, anstatt den ersten Teil abzugleichen. Mir gefällt, wie Sie die Länge der Saite gemessen haben, übrigens!
Leo
@Leo Das ist wirklich ordentlich! Sie können das als separate Antwort
Martin Ender
Ok, dieser neue Trick für ausgeglichene Saiten ist wunderbar: D
Leo
6

Retina , 24 Bytes

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


Probieren Sie es online!

Dies ist inspiriert von Martin Enders Lösung .

Erläuterung

Die erste Zeile ist ein regulärer Ausdruck, der mit einem Zeichen übereinstimmt, gefolgt von einer ausgeglichenen Zeichenfolge, die bis zum Ende der Hauptzeichenfolge reicht (eine detaillierte Erläuterung der Verwendung von Ausgleichsgruppen in diesem regulären Ausdruck finden Sie in Martins Antwort). Da reguläre Ausdrücke von links nach rechts nach Übereinstimmungen suchen, wird das am längsten ausgeglichene richtige Subfix gefunden, dh alles nach der Klammer, die die erste schließt, sowie die Klammer selbst.

Die folgende Zeile ist leer, daher ersetzen wir die Übereinstimmung durch eine leere Zeichenfolge, was bedeutet, dass wir nur noch die verbleibenden Zeichen zählen müssen, um das (0-indizierte) gewünschte Ergebnis zu erhalten.

Die letzte leere Zeile zählt die Anzahl der Übereinstimmungen der leeren Zeichenfolge in der Zeichenfolge, die um eins höher ist als die Anzahl der Zeichen in der Zeichenfolge, entsprechend dem 1-indizierten Ergebnis.

Löwe
quelle
Ich fand eine neue Technik für ausgewogen Saiten gestern passend , die auf unsere beiden Antworten zwei Bytes speichert: tio.run/##K0otycxL/K@q4Z7wX0/D3kbX0E4jOlqj2iZWU0tPU0uFi@v/... (und wahrscheinlich ein Dutzend andere , die ich habe in der geschrieben Vergangenheit ...)
Martin Ender
5

Perl 5 , 28 Bytes

6 Bytes gespart, indem nur .anstelle [>})\]]von Martin Enders Retina-Antwort verwendet wurde .

27 Byte Code + -pFlag.

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

Probieren Sie es online!

Rekursiver Regex, was für eine schöne Erfindung.
Der reguläre Ausdruck sucht nach einer öffnenden Klammer ( [<{([]), gefolgt von einem rekursiven Aufruf ( ?0), gefolgt von einer schließenden Klammer ( .). All dies ist nicht gierig ( +?), so dass es von Anfang an so kurz wie möglich ist. Der Index für das Ende des Spiels ist die Antwort, und wie es passiert, kann es in gefunden werden $+[0].

Dada
quelle
4

JavaScript (ES6), 55 53 52 Byte

1 Byte dank @Adnan gespeichert

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

Nimmt man für jede öffnende Klammer den Zeichencode Mod 4, erhält man 0 oder 3; für die schließenden Klammern erhalten wir 1 oder 2. Daher können wir zwischen öffnenden und schließenden Klammern unterscheiden, indem wir den Zeichencode der Klammer negieren (der die Bits umdreht und 1 subtrahiert) und das zweitniedrigste Bit nehmen; das heißt n&2,.

ETHproductions
quelle
Ich denke , dass statt n-1&2, -n&2auch funktioniert?
Adnan
@Adnan Hmm, ich denke du hast recht. Vielen Dank!
ETHproductions
4

C 75 72 56 55 54 45 Bytes

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

Seht es euch an , wie es online funktioniert .

Wenn die Ausgabe 1-indiziert statt 0-indiziert sein soll, ersetzen Sie die letzte 0durch 1.

2501
quelle
4

Python 2.7 + Numpy, 85 79 Bytes

Mein erster Versuch, Code Golf zu spielen:

from numpy import*
lambda s:list(cumsum([(ord(x)+1&2)-1for x in s])).index(0)
acidtobi
quelle
1
Willkommen auf der Seite!
DJMcMayhem
1
Sie müssen keine Lambdas benennen, Sie können die g =
Pavel
4

Brain-Flak , 97 Bytes (96 für Code, 1 für Flag)

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

Laufen Sie mit der -aFlagge.

Probieren Sie es online!

Erläuterung:

#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 
}{}) 

Es funktioniert einfach, okay.

MegaTom
quelle
3

Retina , 34 Bytes

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

Probieren Sie es online!

Ergebnis ist 0-basiert.

Erläuterung

^.
!

Ersetzen Sie das erste Zeichen durch ein !. Dies führt dazu, dass die gesuchte Klammer nicht übereinstimmt.

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

Wandeln Sie Klammern, eckige Klammern und Klammern in spitze Klammern um. Da die Zeichenfolge garantiert vollständig übereinstimmt, kümmern wir uns überhaupt nicht um die tatsächlichen Typen, und dies spart im nächsten Schritt einige Bytes.

+T`p`!`<!*>

Wiederholt ( +) jedes Zeichen in allen Übereinstimmungen von <!*>mit !s ersetzen . Das heißt, wir stimmen Paare von Klammern ab, die keine weiteren unverarbeiteten Klammern enthalten, und wandeln sie in weitere Ausrufezeichen um. Dadurch wird die gesamte Zeichenfolge mit Ausnahme der nicht angepassten schließenden Klammer in Ausrufezeichen umgewandelt.

\G!

Zählen Sie die Anzahl der führenden Ausrufezeichen, die der 0-basierten Position des ersten Nicht-Ausrufezeichens (dh der nicht übereinstimmenden Klammer) entspricht. Die \GAnker stimmen jeweils mit dem vorherigen überein, weshalb das !s nach dieser Klammer nicht berücksichtigt wird .

Martin Ender
quelle
Ich sah, dass Sie auf der Homepage geantwortet hatten und wusste, dass es eine Art Regex verwenden würde
Christopher
@Christopher Eh, dieser verwendet kaum Regex (im Gegensatz zu der anderen Retina-Antwort, die ich gerade gepostet habe ...).
Martin Ender
Meine Güte. Regex viel?
Christopher
Warum ist nicht das Problem?
Undichte Nonne
@LeakyNun Weil (?!(2))es einfach ist (?!2). Du meintest wahrscheinlich (?(2)(?!))oder (?2)!). Du hast auch vergessen ein zu entkommen ]und das Finale +muss sein *.
Martin Ender
2

PHP, 116 Bytes

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

Online Version

Jörg Hülsermann
quelle
Muss PHP nicht damit beginnen <?php?
Pavel
@Phoenix: Es gibt einen eigenständigen PHP-Interpreter, der das Starttag nicht benötigt. Das ist, was normalerweise zum Golfen verwendet wird.
@ ais523 In diesem Fall wird PHP über die Befehlszeile mit der Option -R ausgeführt
Jörg Hülsermann,
2

Python , 76 Bytes

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

Rekursive Funktion, die das ordinale 2. LSB als Flag für den Open-vs.-Close-Trick verwendet, den viele von Adnan (und wahrscheinlich auch andere) gefunden haben. Schwanz trifft, wenn die kumulative Summe von -1für offen und 1für geschlossen Null erreicht. Der Index wird in einer Variablen gespeichert, da er im Vergleich zur Verwendung von Bytes billiger len(r)ist. Die Indexierung basiert auf 1.

Probieren Sie es online!

Jonathan Allan
quelle
2

Rubin, 35 34 Bytes

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

Basierend auf Dadas Perl5-Antwort . Die Ausgabe ist 1-indiziert. Erfordert, dass der Ruby-Interpreter mit der -nOption aufgerufen wird (implizite while getsSchleife).

Bearbeiten: Dies ist auch 35 34 Bytes, aber ein weiterer möglicher Ausgangspunkt, um diese Antwort weiter zu reduzieren.

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

Edit2: Unnötige Leerzeichen danach entfernt p.

Edit3: Noch ein paar 34-Byte-Antworten.

~/[<{(\[](\g<0>)*[>})\]]/;p$&.size
p~/[<{(\[](\g<0>)*[>})\]]/+$&.size
Ray Hamel
quelle
2
Willkommen bei PPCG!
Pavel
1
Sehr geschätzt! :)
Ray Hamel
2

Python 3 , 59 55 50 49 Bytes

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

Der Ausgang ist 0-indiziert. Die Formel zur Bestimmung der Klammerrichtung wurde zuerst von @ETHProductions entdeckt und von @Adnan verbessert.

Probieren Sie es online!

Dennis
quelle
1

Batch, 172 Bytes

@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-indiziert. <>s sind natürlich Sonderzeichen in Batch, daher muss ich nicht nur überall Anführungszeichen setzen, sondern kann auch keine Tricks ausführen, z. B. gotoBeschriftungen.

Neil
quelle
1

R, 126 Bytes

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
quelle
0

C 127 Bytes

Versuchen Sie es 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;}

Ausgabe

2   ()
4   (<>)
8   <[]{<>}>
2   {}{}{}{}
8   [[]<>[]]
Khaled.K
quelle
Jeder Kommentar, Downvoter.
Khaled.K
Ich war nicht der Abwähler, aber ich denke nicht, dass es hilft, dass es bereits eine viel kürzere C-Vorlage gab.
Ørjan Johansen