Find the First Bracket Match

Question

This was one of a series of challenges leading up to Brain-Flak's birthday. Find out more here.

Challenge

For this challenge your objective will be to find the very first pair of matching brackets in a fully matched string of ()[]{}<> brackets. To borrow DJMcMayhem's definition of a fully matched string:

• For the purpose of this challenge, a "bracket" is any of these characters: ()[]{}<>.

• A pair of brackets is considered "matched" if the opening and closing brackets are in the right order and have no characters inside of them, such as

  ()
  []{}
  

  Or if every subelement inside of it is also matched.

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

  Subelements can also be nested several layers deep.

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

• A string is considered "Fully matched" if and only if each pair of brackets has the correct opening and closing bracket in the right order.

Input

Input will consist of a single nonempty string or char array containing only the characters ()[]{}<>, and is guaranteed to be fully matched. You may take input in any reasonable manner that corresponds with our i/o defaults.

Output

The output of your program or function will be the index of the bracket which closes the first one. Output must be either 0 or 1 indexed. Again, output may be in any reasonable manner that corresponds with our i/o defaults.

Test Cases

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

This is code-golf, fewest bytes wins!

Answer 1

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

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

Try it online!

136 bytes of code, plus one byte for -a. One indexed.

530 bytes golfed off! That's probably the largest golf I've ever done.

14 bytes saved thanks to Riley!

This abuses a formula of the opening/closing parenthesis: if you take the ASCII values, increment it by one, and take modulo of 4, the openers (({[<) will always get 0 or 1, whereas the closers ()}]>) will always get 2 or 3.

Explanation:

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

Answer 2

05AB1E, 17 16 10 bytes

-1 thanks to carusocomputing

-6 thanks to Adnan for his amazing insight that "after incrementing, the second last bit is 0 for an opening bracket and 1 for an closing bracket"

Ç>2&<.pO0k

Try it 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

Answer 3

Jelly, 11 10 9 bytes

O’&2’+\i0

Try it online!

Explanation

The idea here was to find a "magic formula" that can distinguish opening from closing brackets. I originally used O%7&2 (i.e. "take the ASCII code, modulo 7, bitwise-and 2"), but @ETHproductions suggested O’&2 (which replaces the modulo 7 with a decrement); both return 0 for one sort of bracket and 2 for the other. Subtracting 1 (’) will make these results into -1 and 1.

The rest of the code is +\. +\ produces a cumulative sum. If a set of brackets is correctly matched, it will contain the same number of -1s and 1s, i.e. its cumulative sum will be 0. Then we just need to return the index of the first 0 in the resulting list; we can do that with i0.

Answer 4

Vim, 23 bytes

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

Try it online!

I'm really sad about this answer. This solution is beautifully elegant and short, but, by default, vim does not consider < and > to be matched, so I need 13 bytes of boilerplate code. Otherwise, this would just be 10 bytes.

I would have posted a V answer, but that would only be one byte shorter, namely changing Vr to Ò, since Vr is a common vim-idiom.

This is 1-indexed but could be trivially modified to be 0-indexed by changing the 1 to a 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

Answer 5

Retina, 26 24 bytes

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

Try it online!

Result is 1-based.

Explanation

A very different Retina solution that is essentially based on a single (and very readable...) regex. This uses a new technique I discovered yesterday for matching balanced strings using balancing groups.

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

Find (M) and return (!) all matches of the regex ^.(?<-1>([[({<])*.)*. That regex skips the first character of the string and then uses balancing groups to keep track of the nesting depth. Any of [({< increase the depth (kept track of by group 1) and any other character decreases the depth (in principle, the . allows the depth to be decreased by opening brackets as well, but since the regex is matched greedily, the backtracker will never attempt that). The weird trick is that the (?<-1>...) encloses group 1 which works because the popping from a balancing group happens at the end of the group. This saves two bytes over the standard approach in the form ((open)|(?<-2>close))*. The match necessarily stops at the bracket that closes the first one, because we skipped it, so it isn't accounted for in the stack depth (and the stack depth can't go negative).

The length of this match is the 0-based index of the bracket we're looking for.

Simply count the number of empty matches in this string. The empty regex always matches once more than there are characters in the string, so this gives us the 1-based index of the bracket we're looking for.

Answer 6

Retina, 24 bytes

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

Try it online!

This is inspired by Martin Ender's solution.

Explanation

The first line is a regex that matches a character followed by a balanced string going all the way to the end of the main string (for a detailed explanation of how balancing groups are used in this regex see Martin's answer). Since regexes look for matches from left to right, this will find the longest balanced proper subfix, that is everything after the bracket that closes the first one, plus the bracket itself.

The following line is empty, so we replace the match with an empty string, meaning that we now only need to count the remaining characters to get the (0-indexed) desired result.

The last empty line counts the number of matches of the empty string in the string, which is one more than the number of characters in the string, equivalent to the 1-indexed result.

Answer 7

Perl 5, 28 bytes

Saved 6 bytes by using just . instead of [>})\]], from Martin Ender's Retina answer.

27 bytes of code + -p flag.

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

Try it online!

Recursive regex, what a beautiful invention.
The regex looks for an opening bracket ([<{([]), followed by reccursive call (?0), followed by a closing bracket (.). All of this non-greedily (+?) so it matches as short as possible from the beginning. The index of the end of the match is the answer, and as it happens, it can be found in $+[0].

Answer 8

V, 4 bytes

%Dø.

Try it online!

This, unlike most V answers, uses 0-indexing. I'm extremely proud of this answer, and how far my language has come. Explanation:

%       " 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

Answer 9

JavaScript (ES6), 55 53 52 bytes

Saved 1 byte thanks to @Adnan

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

For every opening bracket, taking its char-code mod 4 gives us 0 or 3; for the closing brackets, it gives us 1 or 2. Therefore, we can distinguish between opening and closing brackets by negating the bracket's char-code (which flips the bits and subtracts 1) and taking the second least significant bit; that is, n&2.

Answer 10

C, 75 72 56 55 54 45 bytes

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

See it work online.

If you want the output to be 1-indexed instead of 0-indexed, replace the last 0 with 1.

Answer 11

Python 2.7 + Numpy, 85 79 bytes

My first attempt at code golf:

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

Answer 12

Brain-Flak, 97 bytes (96 for code, 1 for flag)

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

Run with the -a flag.

Try it online!

Explanation:

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

It just works, okay.

Answer 13

Retina, 34 bytes

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

Try it online!

Result is 0-based.

Explanation

^.
!

Replace the first character with a !. This causes the bracket that we're looking for to be unmatched.

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

Convert parentheses, square brackets and braces to angle brackets. Since the string is guaranteed to be fully matched, we don't care about the actual types at all, and this saves some bytes in the next step.

+T`p`!`<!*>

Repeatedly (+) replace each character in all matches of <!*> with !s. That is, we match pairs of brackets which contain no further unprocessed brackets and turn them into further exclamation marks. This will turn the entire string except the unmatched closing bracket into exclamation marks.

\G!

Count the number of leading exclamation marks, which is equal to the 0-based position of the first non-exclamation-mark (i.e. the unmatched bracket). The \G anchors each match to the previous one, which is why this doesn't count the !s after said bracket.

Answer 14

Ruby, 35 34 bytes

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

Based on Dada's Perl5 answer. Output is 1-indexed. Requires the Ruby interpreter be invoked with the -n option (implicit while gets loop).

Edit: This is also 35 34 bytes, but is another possible starting point to reduce this answer further.

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

Edit2: Removed unnecessary spaces after p.

Edit3: A couple more 34-byte answers.

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

Answer 15

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

Answer 16

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

Recursive function that uses the ordinal 2nd LSB as a flag for open vs close trick used by many found by Adnan (and probably others). Tail hits when the cumulative sum of -1 for open and 1 for close reaches zero. The index is kept in a variable as it's byte-cheaper than using len(r), indexing is 1-based.

Try it online!

Answer 17

Python 3, 59 55 50 49 bytes

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

Output is 0-indexed. The formula to determine the bracket direction was first discovered by @ETHProductions and improved by @Adnan.

Try it online!

Answer 18

Vyxal, 5 bytes

¦⁽øβǑ

Try it Online!

    Ǒ # First index
¦     # In prefixes of input
 ⁽--  # Where...
  øβ  # Brackets are balanced

Answer 19

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-indexed. <>s are of course special characters in Batch so not only do I have to quote all over but I can't even do tricks such as making them goto labels.

Answer 20

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}

Answer 21

Julia, 42 bytes

!S=argmin(cumsum(2(s∈"([{<")-1 for s=S))

Attempt This Online!

Answer 22

C, 127 bytes

Try 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;}

Output

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