Esse foi um de uma série de desafios que antecederam o aniversário de Brain-Flak. Saiba mais aqui .

Desafio

Para esse desafio, seu objetivo será encontrar o primeiro par de colchetes correspondentes em uma sequência de ()[]{}<>colchetes totalmente compatível . Para emprestar a definição de DJMcMayhem de uma sequência totalmente correspondente:

• Para o propósito deste desafio, um "suporte" é qualquer um desses caracteres: ()[]{}<>.

• Um par de colchetes é considerado "correspondente" se os colchetes de abertura e fechamento estiverem na ordem correta e não tiverem caracteres dentro deles, como

  ()
  []{}
  

  Ou se todos os subelementos dentro dele também corresponderem.

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

  Os subelementos também podem ser aninhados com várias camadas de profundidade.

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

• Uma string é considerada "Totalmente correspondida" se, e somente se, cada par de colchetes tiver o colchete de abertura e fechamento correto na ordem correta.

Entrada

A entrada consistirá em uma única string não vazia ou matriz de caracteres contendo apenas os caracteres ()[]{}<>e é garantida uma correspondência completa. Você pode tirar a entrada de qualquer forma razoável que corresponde com os nossos I / O padrão .

Saída

A saída do seu programa ou função será o índice do suporte que fecha o primeiro. A saída deve ser 0ou 1indexada. Novamente, a saída pode ser de qualquer forma razoável que corresponde com os nossos I / O padrão .

Casos de teste

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

Isso é código-golfe , o menor número de bytes vence!

V , 4 bytes

%Dø.

Experimente online!

Isso, diferentemente da maioria das respostas em V, usa indexação 0. Estou extremamente orgulhoso dessa resposta e de quão longe meu idioma chegou. Explicação:

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

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

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

Experimente online!

136 bytes de código, mais um byte para -a. Um indexado.

530 bytes jogados fora! Esse é provavelmente o maior golfe que já fiz.

14 bytes salvos graças a Riley!

Isso abusa de uma fórmula dos parênteses de abertura / fechamento: se você pegar os valores ASCII, aumente em um e o módulo 4, os abridores ( ({[<) sempre obterão 0ou 1, enquanto os fechos ( )}]>) sempre obterão 2 ou 3.

Explicação:

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

05AB1E , 17 16 10 bytes

-1 graças à carusocomputação

-6 obrigado a Adnan por sua incrível percepção de que "depois de incrementar, o segundo último bit é 0 para um colchete de abertura e 1 para um colchete de fechamento"

Ç>2&<.pO0k

Experimente 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

Vim, 23 bytes

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

Experimente online!

Estou muito triste com esta resposta. Esta solução é lindamente elegante e curta, mas, por padrão, o vim não considera <e >deve ser correspondido, portanto, preciso de 13 bytes de código padrão . Caso contrário, isso seria apenas 10 bytes.

Eu teria postado uma resposta em V, mas isso seria apenas um byte mais curto, ou seja, mudar Vrpara Ò, já que Vré um idioma comum para o vim.

Isso é indexado em 1, mas pode ser modificado trivialmente para ser indexado em 0, alterando o 1para 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

Geléia , 11 10 9 bytes

O’&2’+\i0

Experimente online!

Explicação

A idéia aqui era encontrar uma "fórmula mágica" capaz de distinguir os colchetes de abertura e fechamento. Eu originalmente usei O%7&2(ou seja, "pegue o código ASCII, módulo 7, bit a bit e 2"), mas o @ETHproductions sugeriu O’&2(que substitui o módulo 7 por um decréscimo); ambos retornam 0 para um tipo de suporte e 2 para o outro. Subtrair 1 ( ’) transformará esses resultados em -1 e 1.

O restante do código é +\. +\produz uma soma cumulativa. Se um conjunto de colchetes for correspondido corretamente, ele conterá o mesmo número de -1s e 1s, ou seja, sua soma acumulada será 0. Então, basta retornar o índice do primeiro 0 na lista resultante; nós podemos fazer isso com i0.

Retina , 26 24 bytes

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

Experimente online!

O resultado é baseado em 1.

Explicação

Uma solução Retina muito diferente, baseada essencialmente em um único (e muito legível ...) regex. Isso usa uma nova técnica que eu descobri ontem para combinar seqüências equilibradas usando grupos de balanceamento .

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

Encontre ( M) e retorne ( !) todas as correspondências da expressão regular ^.(?<-1>([[({<])*.)*. Essa regex ignora o primeiro caractere da sequência e usa grupos de balanceamento para acompanhar a profundidade do aninhamento. Qualquer [({<aumento da profundidade (monitorado por grupo 1) e qualquer outro caractere diminui a profundidade (em princípio, isso .permite que a profundidade seja diminuída abrindo colchetes também, mas como a regex é correspondida avidamente, o backtracker nunca tentará isso ) O truque estranho é que o (?<-1>...)grupo fechado 1que funciona porque o popping de um grupo de balanceamento acontece no final do grupo. Isso economiza dois bytes sobre a abordagem padrão no formulário((open)|(?<-2>close))*. A correspondência necessariamente para no colchete que fecha o primeiro, porque a ignoramos, por isso não é contabilizado na profundidade da pilha (e a profundidade da pilha não pode ficar negativa).

A duração dessa correspondência é o índice baseado em 0 do suporte que estamos procurando.

Basta contar o número de correspondências vazias nessa sequência. O regex vazio sempre corresponde mais uma vez do que os caracteres na string, portanto, isso nos fornece o índice baseado em 1 do colchete que estamos procurando.

Retina , 24 bytes

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

Experimente online!

Isso é inspirado na solução de Martin Ender .

Explicação

A primeira linha é um regex que corresponde a um caractere seguido por uma string balanceada até o final da string principal (para uma explicação detalhada de como os grupos de balanceamento são usados ​​nessa regex, consulte a resposta de Martin). Como as expressões regulares procuram correspondências da esquerda para a direita, este encontrará o subfixe adequado mais longo e equilibrado, ou seja, tudo depois do colchete que fecha o primeiro, além do próprio colchete.

A linha a seguir está vazia, portanto substituímos a correspondência por uma sequência vazia, o que significa que agora precisamos contar apenas os caracteres restantes para obter o resultado desejado (indexado a 0).

A última linha vazia conta o número de correspondências da cadeia vazia na cadeia, que é um a mais que o número de caracteres na cadeia, equivalente ao resultado indexado em 1.

Perl 5 , 28 bytes

Economizou 6 bytes usando apenas em .vez de [>})\]], da resposta Retina de Martin Ender .

27 bytes de código + -psinalizador.

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

Experimente online!

Regex recursiva, que bela invenção.
A regex procura um colchete de abertura ( [<{([]), seguido por chamada reccursiva ( ?0), seguido por um colchete de fechamento ( .). Tudo isso de forma não avidamente ( +?), para que corresponda o mais curto possível desde o início. O índice do final da partida é a resposta, e como acontece, ele pode ser encontrado em $+[0].

JavaScript (ES6), 55 53 52 bytes

Guardado 1 byte graças a @Adnan

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

Para cada colchete de abertura, usar seu código de char mod 4 nos dá 0 ou 3; para os colchetes de fechamento, ele nos fornece 1 ou 2. Portanto, podemos distinguir entre colchetes de abertura e fechamento negando o código de char do colchete (que inverte os bits e subtrai 1) e obtendo o segundo bit menos significativo; isto é, n&2.

C, 75 72 56 55 54 45 bytes

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

Veja como funciona online .

Se você deseja que a saída seja indexada em 1 em vez de indexada em 0, substitua a última 0por 1.

Python 2.7 + Numpy, 85 79 bytes

Minha primeira tentativa no código de golfe:

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

Brain-Flak , 97 bytes (96 para código, 1 para sinalizador)

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

Corra com a -abandeira.

Experimente online!

Explicação:

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

Apenas funciona, ok.

Retina , 34 bytes

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

Experimente online!

O resultado é baseado em 0.

Explicação

^.
!

Substitua o primeiro caractere por a !. Isso faz com que o suporte que procuramos seja incomparável.

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

Converta parênteses, colchetes e colchetes em colchetes angulares. Como a string é garantida para ser totalmente correspondida, não nos importamos com os tipos reais, e isso salva alguns bytes na próxima etapa.

+T`p`!`<!*>

Repetidamente ( +) substitua cada caractere em todas as correspondências de <!*>com !s. Ou seja, combinamos pares de colchetes que não contêm mais colchetes não processados ​​e os transformamos em outros pontos de exclamação. Isso transformará a cadeia inteira, exceto o colchete de fechamento incomparável, em pontos de exclamação.

\G!

Contar o número de pontos de exclamação iniciais, que é igual à posição com base em 0 do primeiro ponto de exclamação (ou seja, o colchete sem correspondência). As \Gâncoras combinam cada uma com a anterior, e é por isso que isso não conta os !s após o referido colchete.

PHP, 116 bytes

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

Versão Online

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

Função recursiva que usa o 2º LSB ordinal como um sinalizador para o truque de abertura versus fechamento usado por muitos encontrados por Adnan (e provavelmente outros). Cauda bate quando a soma acumulada de -1para aberto e 1para próximo atinge zero. O índice é mantido em uma variável, pois é mais barato em bytes do que em uso len(r), a indexação é baseada em 1.

Experimente online!

Ruby, 35 34 bytes

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

Com base na resposta Perl5 da Dada . A saída é indexada em 1. Requer que o interpretador Ruby seja chamado com a -nopção ( while getsloop implícito ).

Edit: Isso também é 35 34 bytes, mas é outro possível ponto de partida para reduzir ainda mais essa resposta.

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

Edit2: Removidos espaços desnecessários depois p.

Edit3: Mais algumas respostas de 34 bytes.

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

Python 3 , 59 55 50 49 bytes

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

A saída é indexada em 0. A fórmula para determinar a direção do suporte foi descoberta pela primeira vez por @ETHProductions e aprimorada por @Adnan.

Experimente online!

Lote, 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 indexado. <>É claro que s são caracteres especiais no Lote, então não só tenho que citar todo o texto, como também não posso fazer truques, como marcá-los goto.

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}

C, 127 bytes

Experimente on-line

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

Saída

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