22
\$\begingroup\$

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 , fewest bytes wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ Bonus points if you answer in Brain-Flak ofc :) \$\endgroup\$ – Erik the Outgolfer Apr 28 '17 at 17:02
  • 1
    \$\begingroup\$ @EriktheOutgolfer Done \$\endgroup\$ – DJMcMayhem Apr 28 '17 at 18:02
  • 1
    \$\begingroup\$ This technique is very helpful for writing inefficient implementations of BF. \$\endgroup\$ – Esolanging Fruit Apr 29 '17 at 2:09

20 Answers 20

2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Isn't there boilerplate you need for matching <>? \$\endgroup\$ – Pavel Sep 11 '17 at 20:53
  • \$\begingroup\$ @Pavel In vim, yes. But not in V. \$\endgroup\$ – DJMcMayhem Sep 11 '17 at 20:54
27
\$\begingroup\$

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
<>)
\$\endgroup\$
  • 8
    \$\begingroup\$ For the love of God, what on earth is this. \$\endgroup\$ – Leaky Nun Apr 28 '17 at 18:09
  • \$\begingroup\$ Basically everyone now is using n-1&2/n+1&2/-n&2 or n%7&2 to distinguish opening and closing brackets... \$\endgroup\$ – ETHproductions Apr 28 '17 at 18:57
  • \$\begingroup\$ @ETHproductions I'm not sure if brain-flak can efficiently compute &2, but I'll look into it. \$\endgroup\$ – DJMcMayhem Apr 28 '17 at 19:01
  • \$\begingroup\$ Oh, I thought you were. You must be doing something similar to distinguish between 0/1 and 2/3... though now that I look at it, you're just decrementing if positive. A cool trick as well :-) \$\endgroup\$ – ETHproductions Apr 28 '17 at 19:02
  • 1
    \$\begingroup\$ The (TOS+1)%4 can be shorter:Try it online! \$\endgroup\$ – MegaTom May 2 '17 at 15:00
11
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ žu seems usable here. \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 at 17:28
  • \$\begingroup\$ žu8ÝÈÏ so, no, not really lol. At best it will still be 5 bytes. I was thinking more of split into the pairs of braces, and remove braces until there's only one pair left, increment counter by 2 for each removed pair. I have no idea if that's less though. Trying it out atm. \$\endgroup\$ – Magic Octopus Urn Apr 28 '17 at 17:31
  • \$\begingroup\$ For 10 bytes: Ç>2&<.pO0k. \$\endgroup\$ – Adnan Apr 28 '17 at 18:21
  • 1
    \$\begingroup\$ Just messing around with the ASCII values. Note that after incrementing, the second last bit is 0 for an opening bracket and 1 for an closing bracket. \$\endgroup\$ – Adnan Apr 28 '17 at 18:28
11
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Post a V answer then :) \$\endgroup\$ – Erik the Outgolfer Apr 28 '17 at 16:59
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Fascinating how we took a similar approach for detecting closing brackets. Unfortunately I only found an inferior version: b*2%7>3 \$\endgroup\$ – 2501 Apr 28 '17 at 18:26
  • \$\begingroup\$ Interesting approach! I developed a longer answer (for practicing) which I eventually golfed down to practically this, except interestingly enough, instead of the first decrement in your post, I had an increment instead. :) \$\endgroup\$ – HyperNeutrino May 1 '17 at 6:04
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That's brilliant! \$\endgroup\$ – Pavel Apr 28 '17 at 22:54
  • \$\begingroup\$ Shorter approach: delete the second part of the string instead of matching the first part. I like how you measured the length of the string, btw! \$\endgroup\$ – Leo Apr 29 '17 at 7:58
  • \$\begingroup\$ @Leo That's really neat! You can post that as a separate answer :) \$\endgroup\$ – Martin Ender Apr 29 '17 at 8:02
  • \$\begingroup\$ Ok, this new trick for balanced strings is wonderful :D \$\endgroup\$ – Leo Jul 6 '17 at 17:01
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I think that instead of n-1&2, -n&2 also works? \$\endgroup\$ – Adnan Apr 28 '17 at 18:51
  • \$\begingroup\$ @Adnan Hmm, I think you're right. Thanks! \$\endgroup\$ – ETHproductions Apr 28 '17 at 18:54
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to the site! \$\endgroup\$ – DJMcMayhem Apr 28 '17 at 20:05
  • 1
    \$\begingroup\$ You don't have to name lambdas, you can remove the g= \$\endgroup\$ – Pavel Apr 29 '17 at 1:44
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I saw you had answered on the home page and knew it was going to use some sort of regex \$\endgroup\$ – Christopher Apr 28 '17 at 22:20
  • \$\begingroup\$ @Christopher Eh, this one barely uses any regex at all (as opposed to the other Retina answer I just posted...). \$\endgroup\$ – Martin Ender Apr 28 '17 at 22:28
  • \$\begingroup\$ Sheesh. Regex much? \$\endgroup\$ – Christopher Apr 28 '17 at 23:00
  • \$\begingroup\$ Why isn't this working? \$\endgroup\$ – Leaky Nun Apr 29 '17 at 4:53
  • \$\begingroup\$ @LeakyNun Because (?!(2)) is just (?!2). You probably meant (?(2)(?!)) or (?2)!). You also forgot to escape a ] and the final + needs to be *. \$\endgroup\$ – Martin Ender Apr 29 '17 at 7:21
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Doesn't PHP need to start with <?php ? \$\endgroup\$ – Pavel Apr 28 '17 at 17:17
  • \$\begingroup\$ @Phoenix: There's a standalone PHP interpreter that doesn't require the starting tag. That's what's normally used for golfing. \$\endgroup\$ – user62131 Apr 28 '17 at 17:18
  • \$\begingroup\$ @ais523 In this case PHP runs from the command line with the -R option \$\endgroup\$ – Jörg Hülsermann Apr 28 '17 at 17:20
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Pavel Apr 30 '17 at 4:46
  • 1
    \$\begingroup\$ Much appreciated! :) \$\endgroup\$ – Ray Hamel Apr 30 '17 at 4:56
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

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   [[]<>[]]
\$\endgroup\$
  • \$\begingroup\$ Any comment, downvoter. \$\endgroup\$ – Khaled.K Apr 30 '17 at 22:46
  • \$\begingroup\$ I wasn't the downvoter, but I don't think it helps that there was already a much shorter C submission. \$\endgroup\$ – Ørjan Johansen May 2 '17 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.