Interlocking Brackets

Question

Write a program or function that takes in an eight byte string containing one of each of the characters ()[]{}<> arranged in any way such that the four respective bracket types match. For example, ]<([){}> is invalid input because the square brackets don't match (though all the others do).

Print or return an integer from 0 to 6 that denotes how many of the six possible pairings of the four bracket types are interlocked. Bracket type pairs are considered interlocked if exactly one bracket of one type occurs between the brackets of the other type. So ([)] and [(]) are interlocked but ()[], [](), ([]), and [()] are not.

The shortest code in bytes wins.

Input/Output Examples

()[]{}<> : 0
([{<>}]) : 0
<>{[]}() : 0
{<>([])} : 0
<(>)[{}] : 1
<[({)}]> : 1
[{<}]>() : 2
{<>([}]) : 2
<{(>})[] : 3
[(]<){>} : 3
<([>{)}] : 4
(<{[>})] : 4
(<[{)>}] : 5
<{[(>})] : 5
[{<(]}>) : 6
(<{[)>}] : 6

Answer 1

CJam, 18

l7~f&_f{\/~;&}s,2/

Thanks isaacg for some golfing ideas :)
Try it online or try all examples

Explanation:

l         read a line of input
7~f&      clear the lowest 3 bits of each character
           the goal is to convert brackets of the same type to the same char
_         duplicate the resulting string, let's call it S
f{…}      for each character in S, and S (the char and S are pushed every time)
  \       swap the character with S
  /       split S around that character, resulting in 3 pieces:
           before, between, after
  ~       dump the pieces on the stack
  ;       pop the last piece
  &       intersect the first 2 pieces
          after the loop, we have an array of strings
          containing the chars interlocking to the left with each char of S
s         join all the string into one string
,         get the string length
2/        divide by 2, because S has duplicated characters

Answer 2

Python 2, 163 bytes

def f(b,e='([{<)]}>',q=range(4)):
 b=[b[b.index(e[j])+1:b.index(e[j+4])]for j in q]
 print sum(sum(abs(b[k].count(e[j])-b[k].count(e[j+4]))for j in q)for k in q)/2

This looks at the stuff between each pair of matching brackets and counts the number of individual left or right brackets present. The sum of these divided by two is the output.

I'm sure it could be golfed a lot more by better golfers than me.

Answer 3

GNU sed -r, 147

Output is in unary as per this meta-answer.

y/([{</)]}>/
s/.*/\t& & & & /
:b
y/)]}>/]}>)/
s/\S*>(\S*)>\S* /\1\t/
t
s/\S* //
:
s/(\t\S*)(\S)(\S*)\2(\S*\t)/\1\3\4/
t
s/\S *$/&/
tb
s/\s//g
s/../1/g

Note: Replace \t with actual tab characters to get the correct score. However, the program will work either way with GNU sed.

Try it online.

Answer 4

Retina, 128 108 64 62 55 bytes

(T`)]>}`([<{
(\D)(.*)\1(.*)
\n$2\n$3
(?=(\D).*\n.*\1)
1
\n
<empty>

Where <empty> represents an empty trailing line. For counting purposes, put each line in a separate file, and replace the \n with actual linefeed characters. For convenience, you can use this equivalent code with the -s flag from a single file:

(T`)]>}`([<{
(\D)(.*)\1(.*)
#$2#$3
(?=(\D)[^#]*#[^#]*\1)
1
#
<empty>

Output is unary.

Explanation

The first ( tells Retina to execute the entire code in a loop until an iteration stops changing the string. In this case, it will always iterate four times, once for each bracket type.

T`)]>}`([<{

This simply turns each closing bracket into the corresponding opening bracket, so that we can match corresponding brackets with a simple backreference later on. (This stage becomes a no-op after the first iteration. It's only included in the loop, because the T already required a backtick, so adding ( cost only one instead of two bytes.)

(\D)(.*)\1(.*)
\n$2\n$3

This replaces the left-most pair of brackets with newlines. We use \D to distinguish brackets from the 1s we add later in the loop for counting. The (.*) at the end ensures that only one pair is replaced (because matches cannot overlap).

(?=(\D).*\n.*\1)
1

The entire regex is in a lookahead, so this matches a position. More specifically it matches one position for each pair of brackets which has been separated by the other brackets we just turned into newlines. A 1 is inserted into each of these positions. We can just leave the 1s there, because they don't affect any of the other regexes (because the \Ds ensure that we don't match them accidentally).

\n
<empty>

Finally, we remove the newlines (i.e. the placeholders for the current type of brackets) - this means that we've reduced the remaining problem to a string of length 6 containing only 3 types of brackets, but otherwise it works exactly the same.

At the end, only the 1s we inserted will be left, and their amount corresponds exactly to the number of interlocking brackets.

Answer 5

Perl, 77 bytes

76 code + 1 switch

perl -pe 'y/)]}>/([{</;for$x(/./g){$h{$x="\\$x"}++&&s!$x(.*)$x!$z+=length$1,$1!e}$_=$z'

Takes input from STDIN and the program must be started fresh for every input.

Explanation

1. Replace all closing brackets with their open counterparts (y/.../.../).
2. Then, for every character in the input string (for$x...), increment a counter for the character ($h{$x}++).
3. If this is the second time we're seeing the character, get the distance between the two occurances (length $1) and remove both occurances of this character from the string. For example, if the string was ([{([{<<, there are two characters [ and { between the two (s. After the (s are processed, the string becomes [{[{<< and we add 2 to the total number ($z) of interlocking brackets.
4. The result is taken from $z ($_=$z)

Answer 6

Python 3, 107

t=0
s=""
for x in input():s+=chr(ord(x)&~7)
for x in s:a=s.split(x);t+=len(set(a[0])&set(a[1]))
print(t//2)

Loosely based on my CJam solution.

Answer 7

Pyth, 20 bytes

JmC/CdTzlsm@FPcsJd{J

Test suite

JmC/CdTz: First, this converts each symbol pair to a single character by map each input character to its character code (Cd) divided by 10 (/ T), which is the same for each pair but different between all pairs. The resultant number is converted back into a character for purposes to be revealed later (C). The resultant list of characters is saved to J.

lsm@FPcsJd{J: Now, we map over the unique characters in J ({J). We start by chopping the string formed by concatenating J using the current character as the delimeter (csJd). A pair of brackets overlaps the current pair if it appears in the second group and either the first or third group. To avoid double counting, we'll just count the first and second group case. So, we remove the third group (P) and take the intersection of the remaining groups (@F). Finally, we concatenate the overlap characters (s) and print the length of the resut (l).

Answer 8

JavaScript (ES7), 121 117 bytes

x=>(a=b=0,[for(c of x)for(d of'1234')(e=c.charCodeAt()/26|0)==d?a^=1<<d:b^=(a>>d&1)<<d*4+e],f=y=>y&&y%2+f(y>>1))(b)/2

Wow. That was fun. I sketched out an answer idea when this challenge first came out, but it was over 150 bytes long and I didn't want to put in the effort to golf it. I ran across this idea in my notebook yesterday and decided I wouldn't stop thinking about it until I had fully golfed it. I ended up writing out two entirely new algorithms, the first of which ended up several bytes shorter after golfing off around 25 bytes with tons of bit-hacking.

How it works

First we set variables a and b to 0. a is a 4-bit binary array of which bracket pairs we are currently inside, and b is a 16-bit binary array of which bracket pairs are linked together.

Next, we loop through each character c in x, and each char d in '0123'. First we determine what type of bracket c is with e=c.charCodeAt()/26-1|0. The decimal char codes of each bracket type are as follows:

() => 40,41
<> => 60,62
[] => 91,93
{} => 123,125

By dividing by 26, subtracting 1, and flooring, we map these to 0, 1, 2, and 3, respectively.

Next we check if this number is equal to the current value of d. If it is, we are either entering or exiting the dth bracket type, so we flip the dth bit in a with a^=1<<d. If it's not, but we are inside the dth bracket type, we need to flip the eth bit in the dth 4-bit section of b. This is done like so:

b^=(a>>d&1)<<d*4+e

(a>>d&1) Returns the dth bit in a. If we are inside the dth bracket type, this returns 1; otherwise, it returns 0. Next, we shift this left by d*4+e bits, and XOR b by the result. If we are inside the dth bracket type, this XORs the d*4+eth bit of b; otherwise, it does nothing.

At the end of all the looping, b will contain a number of 1-bits equal to twice the desired return value. But we still need to figure out how many bits this is. That's where the sub-function f comes in:

f=y=>y&&y%2+f(y>>1)

If y is 0, this simply returns 0. Otherwise, it takes the last bit of y with y%2, then adds the result of running all but the last bit y through the function again. For example:

f(y)         => y && y%2 + f(y>>1)
f(0b1001101) =>       1  + f(0b100110) = 4
f(0b100110)  =>       0  + f(0b10011)  = 3
f(0b10011)   =>       1  + f(0b1001)   = 3
f(0b1001)    =>       1  + f(0b100)    = 2
f(0b100)     =>       0  + f(0b10)     = 1
f(0b10)      =>       0  + f(0b1)      = 1
f(0b1)       =>       1  + f(0b0)      = 1
f(0b0)       => 0                      = 0

We run b through this function and divide the result by 2, and there is our answer.

Answer 9

Oracle SQL 11.2, 206 bytes

WITH v AS(SELECT b,MIN(p)i,MAX(p)a FROM(SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p FROM DUAL CONNECT BY LEVEL<9)GROUP BY b)SELECT COUNT(*)FROM v x,v y WHERE x.i<y.i AND x.a<y.a AND y.i<x.a;

Un-golfed :

WITH v AS( -- Compute min and max pos for each bracket type
           SELECT b,MIN(p)i,MAX(p)a 
           FROM   ( -- replace ending brackets by opening brakets and split the string  
                    SELECT SUBSTR(TRANSLATE(:1,'])>}','[(<{'),LEVEL,1)b,LEVEL p 
                    FROM DUAL 
                    CONNECT BY LEVEL<9
                  )
           GROUP BY b
         )
SELECT COUNT(*)
FROM   v x,v y
WHERE  x.i<y.i AND x.a<y.a AND y.i<x.a -- Apply restrictions for interlocking brackets