Найти первый матч в скобках

22

Это была одна из серии задач, которые привели к дню рождения Брейн-Флака. Узнайте больше здесь .

Вызов

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

  • Для этого вызова, «скобка» представляет собой любая из этих символов: ()[]{}<>.

  • Пара скобок считается "совпавшей", если открывающая и закрывающая скобки расположены в правильном порядке и в них нет символов, например

    ()
    []{}
    

    Или если каждый подэлемент внутри него также совпадает.

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

    Субэлементы также могут быть вложены в несколько слоев.

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

вход

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

Выход

Результатом вашей программы или функции будет индекс скобки, закрывающей первую. Выход должен быть 0или 1индексироваться. Опять же, вывод может быть любым разумным способом, который соответствует нашим значениям по умолчанию для ввода / вывода .

Тестовые случаи

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

Это , побеждает меньше байтов!

Павел
источник
3
Бонусные баллы, если вы ответите в Brain-Flak ofc :)
Эрик Outgolfer
1
@EriktheOutgolfer Done
DJMcMayhem
1
Этот метод очень полезен для написания неэффективных реализаций BF.
Esolanging Fruit

Ответы:

2

V , 4 байта

%Dø.

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

Это, в отличие от большинства ответов V, использует 0-индексирование. Я очень горжусь этим ответом и тем, как далеко зашёл мой язык. Объяснение:

%       " 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
источник
Разве вам не нужен шаблон для сопоставления <>?
Павел
@Pavel В VIM, да. Но не в В.
DJMcMayhem
27

Brain-Flak , 685, 155, 151 , 137 байт

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

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

136 байт кода плюс один байт для -a. Один проиндексирован.

530 байтов в игре! Это, наверное, самый большой гольф, который я когда-либо делал.

14 байтов сохранено благодаря Райли!

Это нарушает формулу открывающей / закрывающей скобки: если вы берете значения ASCII, увеличиваете его на единицу и берете по модулю 4, openers ( ({[<) всегда получает 0или 1, тогда как closers ( )}]>) всегда получает 2 или 3.

Объяснение:

#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
источник
8
Ради любви к Богу, что это такое?
Утренняя монахиня
В основном все сейчас используют n-1&2/ n+1&2/ -n&2или n%7&2различают открывающие и закрывающие скобки ...
ETHproductions
@ETHproductions Я не уверен, может ли мозговой зенит эффективно вычислять &2, но я посмотрю на это.
DJMcMayhem
О, я так и думал. Вы должны делать что-то похожее, чтобы различать 0/ 1и 2/ 3... хотя теперь, когда я смотрю на это, вы просто уменьшаете, если положительный результат.
Крутой
1
(TOS+1)%4Может быть короче: Попробуйте его в Интернете!
MegaTom
11

05AB1E , 17 16 10 байт

-1 благодаря carusocomputing

-6 спасибо Аднану за его удивительное понимание того, что «после приращения второй последний бит равен 0 для открывающей скобки и 1 для закрывающей скобки»

Ç>2&<.pO0k

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

Ç          # 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
Райли
источник
žuкажется пригодным для использования здесь.
Волшебная урна осьминога
žu8ÝÈÏтак что нет, не очень. В лучшем случае это все равно будет 5 байтов. Я больше думал о разделении на пары фигурных скобок и удалении фигурных скобок до тех пор, пока не останется только одна пара, увеличивая счетчик на 2 для каждой удаленной пары. Я понятия не имею, если это меньше, хотя. Попробуй это, атм.
Волшебная урна осьминога
Для 10 байт: Ç>2&<.pO0k.
Аднан
1
Просто возиться со значениями ASCII. Обратите внимание, что после увеличения второй последний бит предназначен 0для открывающей скобки и 1для закрывающей скобки.
Аднан
11

Vim, 23 байта

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

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

Мне очень грустно об этом ответе. Это решение красиво элегантно и коротко, но по умолчанию vim не учитывает <и не >может быть сопоставлено, поэтому мне нужно 13 байтов стандартного кода. В противном случае это будет всего 10 байтов.

Я бы написал V-ответ, но он был бы всего на один байт короче, а именно изменился Vrна Ò, так Vrкак это обычная vim-идиома.

Это 1-индексированный, но может быть тривиально изменен, чтобы быть 0-индексированным, изменив на 1a 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
источник
1
Отправьте
10

Желе , 11 10 9 байт

O’&2’+\i0

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

объяснение

Идея здесь состояла в том, чтобы найти «волшебную формулу», которая может отличить открывающие и закрывающие скобки. Первоначально я использовал O%7&2(то есть "взять код ASCII, по модулю 7, поразрядно и 2"), но предложил @ETHproductions O’&2(который заменяет модуль 7 с уменьшением); оба возвращают 0 для одного вида скобок и 2 для другого. Вычитание 1 ( ) превратит эти результаты в -1 и 1.

Остальная часть кода есть +\. +\производит накопленную сумму. Если набор скобок правильно сопоставлен, он будет содержать одинаковое количество -1 и 1, то есть его совокупная сумма будет равна 0. Тогда нам просто нужно вернуть индекс первого 0 в результирующем списке; мы можем сделать это с i0.


источник
Удивительно, как мы использовали подобный подход для определения закрывающих скобок. К сожалению, я нашел только худшую версию:b*2%7>3
2501
Интересный подход! Я разработал более длинный ответ (для практики), который я в конечном итоге применил практически к этому, за исключением достаточно интересного, вместо первого декремента в вашем посте, у меня вместо этого был прирост. :)
HyperNeutrino
9

Сетчатка , 26 24 байта

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

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

Результат основан на 1.

объяснение

Совсем другое решение Retina, основанное на единственном (и очень читаемом ...) регулярном выражении. Это использует новую технику, которую я обнаружил вчера для сопоставления сбалансированных строк с использованием балансировочных групп .

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

Найти ( M) и вернуть ( !) все совпадения регулярного выражения ^.(?<-1>([[({<])*.)*. Это регулярное выражение пропускает первый символ строки, а затем использует балансировочные группы для отслеживания глубины вложения. Любое [({<увеличение глубины (отслеживание по группам 1) и любой другой символ уменьшает глубину (в принципе, .позволяет также уменьшать глубину, открывая скобки, но поскольку регулярное выражение сопоставляется жадно, средство отслеживания никогда не будет пытаться это сделать ). Странный трюк заключается в том, что (?<-1>...)включающая группа 1работает, потому что выталкивание из уравновешивающей группы происходит в конце группы. Это экономит два байта по сравнению со стандартным подходом в форме((open)|(?<-2>close))*, Совпадение обязательно останавливается на скобке, которая закрывает первую, потому что мы ее пропустили, поэтому она не учитывается в глубине стека (и глубина стека не может быть отрицательной).

Длина этого соответствия - это основанный на 0 индекс скобки, которую мы ищем.


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

Мартин Эндер
источник
Это блестяще!
Павел
Краткий подход : удалите вторую часть строки вместо соответствия первой части. Мне нравится, как вы измерили длину струны, кстати!
Лев
@ Leo Это действительно здорово! Вы можете опубликовать это как отдельный ответ :)
Мартин Эндер,
Хорошо, этот новый трюк для сбалансированных струн замечательный: D
Лев
6

Сетчатка , 24 байта

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


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

Это вдохновлено решением Мартина Эндера .

объяснение

Первая строка - это регулярное выражение, которое соответствует символу, за которым следует сбалансированная строка, идущая до конца основной строки (подробное объяснение того, как балансировочные группы используются в этом регулярном выражении, см. В ответе Мартина). Поскольку регулярные выражения ищут совпадения слева направо, будет найден самый длинный сбалансированный правильный подфикс, то есть все, что после скобки, закрывающей первый, плюс сама скобка.

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

Последняя пустая строка подсчитывает количество совпадений пустой строки в строке, что на один больше, чем количество символов в строке, что эквивалентно результату с 1 индексом.

Лео
источник
Вчера я нашел новую технику для сопоставления сбалансированных строк, которая экономит два байта в обоих наших ответах: tio.run/##K0otycxL/K@q4Z7wX0/D3kbX0E4jOlqj2iZWU0tPU0uFi@v/… (и, вероятно, дюжину других, которые я написал в прошлое ...)
Мартин Эндер
5

Perl 5 , 28 байт

Сохранено 6 байтов, используя .вместо этого ответ Retina[>})\]] Мартина Эндера .

27 байт кода + -pфлаг.

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

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

Рекурсивное регулярное выражение, какое прекрасное изобретение.
Регулярное выражение ищет открывающую скобку ([<{([] ), за которой следует рекурсивный вызов ( ?0), а затем закрывающая скобка ( .). Все это без жадности ( +?), поэтому оно соответствует как можно короче с самого начала. Индекс конца матча является ответом, и, как это происходит, его можно найти в $+[0].

папа
источник
4

JavaScript (ES6), 55 53 52 байта

Сохранено 1 байт благодаря @Adnan

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

Для каждой открывающей скобки, взяв ее код-код, мод 4 дает нам 0 или 3; для закрывающих скобок это дает нам 1 или 2. Таким образом, мы можем различить открывающую и закрывающую скобки, отрицая кодовую скобку скобки (которая переворачивает биты и вычитает 1) и беря второй младший значащий бит; то есть n&2.

ETHproductions
источник
Я думаю, что вместо n-1&2, -n&2также работает?
Аднан
@ Аднан Хм, я думаю ты прав. Благодарность!
ETHproductions
4

C, 75 72 56 55 54 45 байт

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

Видеть это работает онлайн .

Если вы хотите, чтобы выходные данные были проиндексированы 1 вместо 0, замените последний 0на 1.

2501
источник
4

Python 2,7 + Numpy, 85 79 байт

Моя первая попытка кода в гольф:

from numpy import*
lambda s:list(cumsum([(ord(x)+1&2)-1for x in s])).index(0)
acidtobi
источник
1
Добро пожаловать на сайт!
DJMcMayhem
1
Вам не нужно называть лямбды, вы можете удалить g =
Павел
4

Brain-Flak , 97 байт (96 для кода, 1 для флага)

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

Беги с -aфлагом.

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

Объяснение:

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

Это просто работает, хорошо.

MegaTom
источник
3

Сетчатка , 34 байта

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

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

Результат основан на 0.

объяснение

^.
!

Заменить первый символ на !. Это приводит к тому, что скобка, которую мы ищем, не имеет себе равных.

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

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

+T`p`!`<!*>

Повторно ( +) заменять каждый символ во всех совпадениях <!*>с на !s. То есть мы сопоставляем пары скобок, которые не содержат дальнейших необработанных скобок, и превращаем их в дополнительные восклицательные знаки. Это превратит всю строку за исключением непревзойденной закрывающей скобки в восклицательные знаки.

\G!

Подсчитайте количество начальных восклицательных знаков, которое равно нулю позиции первого не восклицательного знака (то есть непревзойденной скобки). Каждый из \Gякорей соответствует предыдущему, поэтому это не учитывает! s после указанной скобки.

Мартин Эндер
источник
Я видел, что вы ответили на главной странице и знали, что будет использоваться какое-то регулярное выражение
Кристофер,
@ Кристофер Эх, этот почти не использует никаких регулярных выражений (в отличие от другого ответа Retina, который я только что опубликовал ...).
Мартин Эндер
Sheesh. Regex много?
Кристофер
Почему не это работает?
Утренняя монахиня
@ LeakyNun Потому что (?!(2))это просто (?!2). Вы, вероятно, имели в виду (?(2)(?!))или (?2)!). Вы также забыли сбежать, ]и финал +должен быть *.
Мартин Эндер
2

PHP, 116 байт

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

Онлайн версия

Йорг Хюльсерманн
источник
Не нужно ли начинать с PHP <?php?
Павел
@ Phoenix: есть отдельный интерпретатор PHP, который не требует начального тега. Это то, что обычно используется для игры в гольф.
@ ais523 В этом случае PHP запускается из командной строки с параметром -R
Jörg Hülsermann
2

Python , 76 байт

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

Рекурсивная функция, которая использует порядковый 2-й LSB в качестве флага для трюка open vs close, используемого многими, найденными Аднаном (и, возможно, другими). Хвост поражает, когда совокупная сумма -1для открытия и 1закрытия достигает нуля. Индекс хранится в переменной, так как он стоит дешевле, чем при использованииlen(r) , индексирование основано на 1.

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

Джонатан Аллан
источник
2

Рубин, 35 34 байта

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

На основании ответа Даля Perl5 . Выход 1 индексируется. Требуется, чтобы интерпретатор Ruby вызывался с -nпараметром (неявнымwhile gets цикл).

Изменить: Это также 35 34 байтов, но это еще одна возможная отправная точка для дальнейшего сокращения этого ответа.

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

Edit2: удалены ненужные пробелы после p.

Edit3: еще пара 34-байтовых ответов.

~/[<{(\[](\g<0>)*[>})\]]/;p$&.size
p~/[<{(\[](\g<0>)*[>})\]]/+$&.size
Рэй Хэмел
источник
2
Добро пожаловать в PPCG!
Павел
1
Очень признателен! :)
Рэй Хэмел
2

Python 3 , 59 55 50 49 байт

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

Вывод 0 проиндексирован. Формула для определения направления скобки была впервые обнаружена @ETHProductions и улучшена @Adnan.

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

Деннис
источник
1

Пакет, 172 байта

@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-индексироваться. <>Это, конечно, специальные символы в пакетном режиме, поэтому я не только должен цитировать все подряд, но я даже не могу делать такие трюки, как создание их gotoярлыков.

Нил
источник
1

R, 126 байт

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}
Нил
источник
0

C 127 байтов

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

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

Выход

2   ()
4   (<>)
8   <[]{<>}>
2   {}{}{}{}
8   [[]<>[]]
Khaled.K
источник
Любой комментарий, downvoter.
Khaled.K
Я не был downvoter, но я не думаю, что это помогает, что было уже намного более короткое представление C.
Орджан Йохансен