Напишите программу или функцию, которая принимает восьмибайтовую строку, содержащую один из каждого символа, ()[]{}<>расположенного любым образом, так чтобы четыре соответствующих типа скобок совпадали. Например, ]<([){}>неверный ввод, потому что квадратные скобки не совпадают (хотя все остальные совпадают).

Выведите или верните целое число от 0до 6, обозначающее, сколько из шести возможных пар четырех типов скобок заблокировано. Пары типа скобок считаются блокированными, если между скобками другого типа встречается ровно одна скобка одного типа. Так ([)]и [(])сцепляются , но ()[], [](), ([])и [()]нет.

Самый короткий код в байтах побеждает.

Примеры ввода / вывода

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

CJam, 18

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

Спасибо isaacg за некоторые идеи игры в гольф :)
Попробуйте онлайн или попробуйте все примеры

Объяснение:

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

Python 2, 163 байта

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

Это смотрит на вещи между каждой парой соответствующих скобок и подсчитывает количество отдельных левых или правых скобок. Сумма этих значений, деленная на два, является выходной.

Я уверен, что это может быть гораздо лучше, чем я.

GNU sed -r, 147

Выход в унарном соответствии с этим мета-ответом .

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

Примечание. Замените \tдействительными tabсимволами, чтобы получить правильный результат. Тем не менее, программа будет работать в любом случае с GNU sed.

Попробуйте онлайн .

Perl, 77 байт

76 код + 1 переключатель

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

Принимает ввод из STDIN, и программа должна быть запущена заново для каждого ввода.

объяснение

1. Замените все закрывающие скобки их открытыми аналогами ( y/.../.../).
2. Затем для каждого символа входной строки ( for$x...) увеличьте счетчик для символа ( $h{$x}++).
3. Если это второй раз, когда мы видим символ, определите расстояние между двумя вхождениями ( length $1) и удалите оба вхождения этого символа из строки. Например, если строка была ([{([{<<, есть два символа [и {между двумя (s. После обработки (s, строка становится, [{[{<<и мы добавляем 2 к общему количеству ( $z) блокирующих скобок.
4. Результат взят из $z( $_=$z)

Pyth, 20 байтов

JmC/CdTzlsm@FPcsJd{J

Тестирование

JmC/CdTzВо-первых, это преобразует каждую пару символов в один символ путем сопоставления каждого входного символа с его кодом символа ( Cd), деленным на 10 ( / T), который одинаков для каждой пары, но различен для всех пар. Результирующее число преобразуется обратно в символ для целей, которые будут раскрыты позже ( C). Результирующий список символов сохраняется в J.

lsm@FPcsJd{J: Теперь мы сопоставляем уникальные символы в J( {J). Мы начнем с обрезки строки, образованной конкатенацией, Jиспользуя текущий символ в качестве delimeter ( csJd). Пара скобок перекрывает текущую пару, если она появляется во второй группе или в первой или третьей группе. Чтобы избежать двойного счета, мы просто посчитаем первый и второй случай группы. Итак, мы удаляем третью группу ( P) и берем пересечение оставшихся групп ( @F). Наконец, мы объединяем символы перекрытия ( s) и печатаем длину resut ( l).

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)

Сильно основано на моем решении CJam.

Retina , 128 108 64 62 55 байт

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

Где <empty>представляет собой пустую висячую строку. Для целей подсчета поместите каждую строку в отдельный файл и замените их \nдействительными символами перевода строки. Для удобства вы можете использовать этот эквивалентный код с -sфлагом из одного файла:

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

Выход одинарный .

объяснение

Первый (говорит Retina выполнить весь код в цикле, пока итерация не прекратит изменять строку. В этом случае он всегда будет повторяться четыре раза, по одному разу для каждого типа скобок.

T`)]>}`([<{

Это просто превращает каждую закрывающую скобку в соответствующую открывающую скобку, чтобы мы могли сопоставить соответствующие скобки с простой обратной ссылкой позже. (Эта стадия становится недоступной после первой итерации. Она включается только в цикл, потому что Tуже требуется обратная пометка, поэтому добавление (стоит только один вместо двух байтов.)

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

Это заменяет крайнюю левую пару скобок символами новой строки. Мы используем, \Dчтобы отличить скобки от 1s, которые мы добавим позже в цикле для подсчета. В (.*)конце гарантируется, что будет заменена только одна пара (поскольку совпадения не могут перекрываться).

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

Все регулярные выражения в предвкушении, так что это соответствует позиции . Более конкретно, он соответствует одной позиции для каждой пары скобок, которая была разделена другими скобками, которые мы только что превратили в новые строки. А 1вставляется в каждую из этих позиций. Мы можем просто оставить 1s там, потому что они не влияют ни на одно из других регулярных выражений (потому что они \Dгарантируют, что мы не совпадем с ними случайно).

\n
<empty>

Наконец, мы удаляем символы новой строки (т. Е. Заполнители для текущего типа скобок) - это означает, что мы сократили оставшуюся проблему до строки длиной 6, содержащей только 3 типа скобок, но в остальном она работает точно так же.

В конце 1останутся только те s, которые мы вставили, и их количество точно соответствует количеству блокирующих скобок.

JavaScript (ES7), 121 117 байт

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

Вау. Это было весело. Я набросал идею ответа, когда впервые появился этот вызов, но его длина превышала 150 байтов, и я не хотел прикладывать усилия для его игры в гольф. Вчера я наткнулся на эту идею в своей записной книжке и решил, что не перестану думать об этом, пока полностью не поиграю в нее. В итоге я написал два совершенно новых алгоритма, первый из которых оказался на несколько байт короче, после того, как вы проиграли около 25 байт с кучей хитов.

Как это работает

Сначала мы устанавливаем переменные aи bв 0. aявляется 4-битным двоичным массивом пар скобок, в котором мы сейчас находимся, и b16-разрядным двоичным массивом пар скобок, которые связаны вместе.

Далее мы перебираем каждый символ cв xи каждый символ dв '0123'. Сначала мы определяем , какой тип кронштейна cнаходится с e=c.charCodeAt()/26-1|0. Десятичные коды символов каждого типа скобок:

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

Делив на 26, вычитая 1 и настил, мы сопоставляем их с 0, 1, 2 и 3 соответственно.

Далее мы проверяем, равно ли это число текущему значению d. Если это так, мы либо входим, либо выходим из dтипа th скобки, поэтому мы переключаем dбит th aс помощью a^=1<<d. Если это не так, но мы находимся внутри dскобки, нам нужно перевернуть eбит в d4-битной секции b. Это делается так:

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

(a>>d&1)Возвращает dбит в a. Если мы находимся внутри dскобочного типа, это возвращает 1; в противном случае возвращается 0. Затем мы сдвигаем это влево на d*4+eбиты, а XOR b- на результат. Если мы находимся внутри dскобочного типа, то это XOR d*4+eбит b; в противном случае это ничего не делает.

В конце всего цикла bбудет содержаться число 1-бит, равное удвоенному желаемому возвращаемому значению. Но нам все еще нужно выяснить, сколько это битов. Вот где fвходит подфункция:

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

Если y0, это просто возвращает 0. В противном случае, он принимает последний бит yс y%2, а затем добавляет результат yповторного выполнения всех функций, кроме последнего, через функцию. Например:

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

Мы пробегаем bэту функцию и делим результат на 2, и наш ответ есть.

Oracle SQL 11.2, 206 байт

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;

Без гольфа:

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