Encuentra el primer paréntesis

22

Este fue uno de una serie de desafíos previos al cumpleaños de Brain-Flak. Descubre más aquí .

Reto

Para este desafío, su objetivo será encontrar el primer par de corchetes coincidentes en una cadena de ()[]{}<>corchetes totalmente coincidentes . Para tomar prestada la definición de DJMcMayhem de una cadena totalmente coincidente:

  • A los efectos de este reto, un "soporte" es cualquiera de los siguientes caracteres: ()[]{}<>.

  • Un par de paréntesis se considera "coincidente" si los paréntesis de apertura y cierre están en el orden correcto y no tienen caracteres dentro de ellos, como

    ()
    []{}
    

    O si cada subelemento dentro de él también coincide.

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

    Los subelementos también se pueden anidar en varias capas de profundidad.

    [(){<><>[()]}<>()]
    <[{((()))}]>
    
  • Una cadena se considera "Totalmente coincidente" si y solo si cada par de corchetes tiene el corchete de apertura y cierre correcto en el orden correcto.

Entrada

La entrada consistirá en una sola cadena no vacía o matriz de caracteres que contiene solo los caracteres ()[]{}<>, y se garantiza que coincida completamente. Usted puede tomar la entrada de cualquier manera razonable que se corresponde con nuestros E / S por defecto .

Salida

La salida de su programa o función será el índice del paréntesis que cierra el primero. La salida debe ser 0o 1indexada. Una vez más, la salida puede estar en cualquier forma razonable que se corresponde con nuestros E / S por defecto .

Casos de prueba

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

Este es el , ¡la menor cantidad de bytes gana!

Pavel
fuente
3
Puntos de bonificación si responde en Brain-Flak ofc :)
Erik the Outgolfer
1
@EriktheOutgolfer Hecho
DJMcMayhem
1
Esta técnica es muy útil para escribir implementaciones ineficientes de BF.
Esolanging Fruit

Respuestas:

2

V , 4 bytes

%Dø.

Pruébalo en línea!

Esto, a diferencia de la mayoría de las respuestas V, utiliza la indexación 0. Estoy extremadamente orgulloso de esta respuesta y de lo lejos que ha llegado mi idioma. Explicación:

%       " 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
fuente
¿No hay repetitivo que necesitas para hacer coincidir <>?
Pavel
@Pavel En vim, sí. Pero no en V.
DJMcMayhem
27

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

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

Pruébalo en línea!

136 bytes de código, más un byte para -a. Uno indexado.

¡530 bytes de golf! Ese es probablemente el golf más grande que he hecho.

¡14 bytes guardados gracias a Riley!

Esto abusa de una fórmula del paréntesis de apertura / cierre: si toma los valores ASCII, increméntelos en uno y tome el módulo de 4, los abridores ( ({[<) siempre obtendrán 0o 1, mientras que los cerradores ( )}]>) siempre obtendrán 2 o 3.

Explicación:

#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
fuente
8
Por el amor de Dios, qué demonios es esto.
Leaky Nun
Básicamente, todo el mundo ahora está usando n-1&2/ n+1&2/ -n&2o n%7&2para distinguir los corchetes de apertura y cierre ...
ETHproductions
@ETHproductions No estoy seguro de si Brain-Flak puede calcular eficientemente &2, pero lo investigaré.
DJMcMayhem
Oh, pensé que lo eras. Debes estar haciendo algo similar para distinguir entre 0/ 1y 2/ 3... aunque ahora que lo miro, solo estás disminuyendo si es positivo. Un truco genial también :-)
ETHproductions
1
El (TOS+1)%4puede ser más corto: Pruébelo en línea!
MegaTom
11

05AB1E , 17 16 10 bytes

-1 gracias a carusocomputing

-6 gracias a Adnan por su sorprendente percepción de que "después de aumentar, el segundo último bit es 0 para un paréntesis de apertura y 1 para un paréntesis de cierre"

Ç>2&<.pO0k

Pruébalo en línea!

Ç          # 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
Riley
fuente
žuParece utilizable aquí.
Urna mágica de pulpo
žu8ÝÈÏasí que no, no realmente jajaja. En el mejor de los casos, seguirá siendo de 5 bytes. Estaba pensando más en dividirme en los pares de llaves, y quitar las llaves hasta que solo quede un par, incrementar el contador en 2 por cada par eliminado. Sin embargo, no tengo idea si eso es menos. Probándolo atm.
Urna mágica del pulpo
Por 10 bytes: Ç>2&<.pO0k.
Adnan
1
Solo jugando con los valores ASCII. Tenga en cuenta que después de incrementar, el segundo último bit es 0para un corchete de apertura y 1para un corchete de cierre.
Adnan
11

Vim, 23 bytes

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

Pruébalo en línea!

Estoy realmente triste por esta respuesta. Esta solución es bellamente elegante y corta, pero, por defecto, vim no considera <y >debe coincidir, por lo que necesito 13 bytes de código repetitivo. De lo contrario, esto sería solo 10 bytes.

Hubiera publicado una respuesta V, pero eso sería solo un byte más corto, es decir, cambiar Vra Ò, ya que Vres un vim-idioma común.

Esto está indexado en 1 pero podría modificarse trivialmente para indexarse ​​en 0 cambiando el 1a 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
DJMcMayhem
fuente
1
Publica una respuesta en V y luego :)
Erik the Outgolfer
10

Gelatina , 11 10 9 bytes

O’&2’+\i0

Pruébalo en línea!

Explicación

La idea aquí era encontrar una "fórmula mágica" que pueda distinguir los corchetes de apertura de cierre. Originalmente utilicé O%7&2(es decir, "tome el código ASCII, módulo 7, bit a bit y 2"), pero @ETHproductions sugirió O’&2(que reemplaza el módulo 7 con una disminución); ambos devuelven 0 para un tipo de soporte y 2 para el otro. Restar 1 ( ) convertirá estos resultados en -1 y 1.

El resto del código es +\. +\produce una suma acumulativa Si un conjunto de paréntesis coincide correctamente, contendrá el mismo número de -1s y 1s, es decir, su suma acumulativa será 0. Entonces solo necesitamos devolver el índice del primer 0 en la lista resultante; podemos hacer eso con i0.


fuente
Fascinante cómo tomamos un enfoque similar para detectar corchetes de cierre. Desafortunadamente solo encontré una versión inferior:b*2%7>3
2501
Enfoque interesante! Desarrollé una respuesta más larga (para practicar) que eventualmente reduje a prácticamente esto, excepto que, curiosamente, en lugar de la primera disminución en su publicación, tuve un incremento. :)
HyperNeutrino
9

Retina , 26 24 bytes

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

Pruébalo en línea!

El resultado está basado en 1.

Explicación

Una solución Retina muy diferente que se basa esencialmente en una expresión regular única (y muy legible ...). Esto usa una nueva técnica que descubrí ayer para unir cadenas equilibradas usando grupos de equilibrio .

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

Find ( M) y return ( !) todas las coincidencias de la expresión regular ^.(?<-1>([[({<])*.)*. Esa expresión regular omite el primer carácter de la cadena y luego usa grupos de equilibrio para realizar un seguimiento de la profundidad de anidación. Cualquiera de [({<aumentar la profundidad (seguimiento por grupo 1) y cualquier otro personaje disminuye la profundidad (en principio, .permite que la profundidad se reduzca abriendo también los corchetes, pero dado que la expresión regular se combina con avidez, el rastreador nunca intentará eso ) El truco extraño es que el (?<-1>...)grupo de encierro 1funciona porque el estallido de un grupo de equilibrio ocurre al final del grupo. Esto ahorra dos bytes sobre el enfoque estándar en el formulario((open)|(?<-2>close))*. La coincidencia necesariamente se detiene en el soporte que cierra el primero, porque lo omitimos, por lo que no se tiene en cuenta en la profundidad de la pila (y la profundidad de la pila no puede ser negativa).

La longitud de esta coincidencia es el índice basado en 0 del soporte que estamos buscando.


Simplemente cuente el número de coincidencias vacías en esta cadena. La expresión regular vacía siempre coincide una vez más que los caracteres en la cadena, por lo que esto nos da el índice basado en 1 del soporte que estamos buscando.

Martin Ender
fuente
¡Eso es brillante!
Pavel
Enfoque más corto : elimine la segunda parte de la cadena en lugar de hacer coincidir la primera parte. ¡Me gusta cómo midiste la longitud de la cuerda, por cierto!
Leo
@Leo ¡Eso está muy bien! Puede publicar eso como una respuesta separada :)
Martin Ender
Ok, este nuevo truco para cuerdas equilibradas es maravilloso: D
Leo
6

Retina , 24 bytes

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


Pruébalo en línea!

Esto está inspirado en la solución de Martin Ender .

Explicación

La primera línea es una expresión regular que coincide con un carácter seguido de una cadena equilibrada que va hasta el final de la cadena principal (para una explicación detallada de cómo se usan los grupos de equilibrio en esta expresión regular, vea la respuesta de Martin). Dado que las expresiones regulares buscan coincidencias de izquierda a derecha, esto encontrará el subfijo correcto más largo equilibrado, es decir, todo después del parche que cierra el primero, más el paréntesis en sí.

La siguiente línea está vacía, por lo que reemplazamos la coincidencia con una cadena vacía, lo que significa que ahora solo necesitamos contar los caracteres restantes para obtener el resultado deseado (indexado a 0).

La última línea vacía cuenta el número de coincidencias de la cadena vacía en la cadena, que es uno más que el número de caracteres en la cadena, equivalente al resultado indexado 1.

León
fuente
Ayer encontré una nueva técnica para hacer coincidir cadenas equilibradas que ahorra dos bytes en nuestras dos respuestas: tio.run/##K0otycxL/K@q4Z7wX0/D3kbX0E4jOlqj2iZWU0tPU0uFi@v/… (y probablemente una docena más que he escrito en el pasado ...)
Martin Ender
5

Perl 5 , 28 bytes

Ahorró 6 bytes usando solo en .lugar de [>})\]], de la respuesta Retina de Martin Ender .

27 bytes de código + -pbandera.

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

Pruébalo en línea!

La expresión regular recursiva, qué hermoso invento.
La expresión regular busca un corchete de apertura ( [<{([]), seguido de una llamada recursiva ( ?0), seguido de un corchete de cierre ( .). Todo esto sin codicia ( +?) por lo que coincide lo más corto posible desde el principio. El índice del final del partido es la respuesta, y a medida que sucede, se puede encontrar en $+[0].

Dada
fuente
4

JavaScript (ES6), 55 53 52 bytes

Guardado 1 byte gracias a @Adnan

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

Para cada paréntesis de apertura, tomar su código de char mod 4 nos da 0 o 3; para los corchetes de cierre, nos da 1 o 2. Por lo tanto, podemos distinguir entre abrir y cerrar corchetes negando el código de caracteres del corchete (que voltea los bits y resta 1) y tomando el segundo bit menos significativo; es decir, n&2.

ETHproducciones
fuente
Creo que en lugar de n-1&2, ¿ -n&2también funciona?
Adnan
@Adnan Hmm, creo que tienes razón. ¡Gracias!
ETHproductions
4

C, 75 72 56 55 54 45 bytes

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

Míralo trabajar en línea .

Si desea que la salida esté indexada en 1 en lugar de indexada en 0, reemplace la última 0con 1.

2501
fuente
4

Python 2.7 + Numpy, 85 79 bytes

Mi primer intento de código de golf:

from numpy import*
lambda s:list(cumsum([(ord(x)+1&2)-1for x in s])).index(0)
acidtobi
fuente
1
Bienvenido al sitio!
DJMcMayhem
1
No tiene que nombrar lambdas, puede eliminar el g =
Pavel
4

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

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

Corre con el -a bandera.

Pruébalo en línea!

Explicación:

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

Simplemente funciona, está bien.

MegaTom
fuente
3

Retina , 34 bytes

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

Pruébalo en línea!

El resultado está basado en 0.

Explicación

^.
!

Reemplace el primer carácter con a !. Esto hace que el soporte que estamos buscando sea incomparable.

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

Convierta paréntesis, corchetes y llaves en corchetes angulares. Dado que se garantiza que la cadena coincida completamente, no nos importan los tipos reales, y esto ahorra algunos bytes en el siguiente paso.

+T`p`!`<!*>

Repetidamente ( +) reemplaza cada personaje en todas las coincidencias de <!*>con !s. Es decir, combinamos pares de corchetes que no contienen más corchetes sin procesar y los convertimos en otros signos de exclamación. Esto convertirá toda la cadena, excepto el corchete de cierre sin igual, en signos de exclamación.

\G!

Cuente el número de signos de exclamación iniciales, que es igual a la posición basada en 0 del primer signo de no exclamación (es decir, el paréntesis no coincidente). Los \Ganclajes coinciden con los anteriores, por lo que esto no cuenta los !s después de dicho paréntesis.

Martin Ender
fuente
Vi que había respondido en la página de inicio y sabía que iba a usar algún tipo de expresión regular
Christopher
@Christopher Eh, este apenas usa expresiones regulares (a diferencia de la otra respuesta de Retina que acabo de publicar ...).
Martin Ender
Sheesh Regex mucho?
Christopher
¿Por qué no funciona esto ?
Leaky Nun
@LeakyNun Porque (?!(2))es justo (?!2). Probablemente quisiste decir (?(2)(?!))o (?2)!). También olvidaste escapar de a ]y la final +debe ser *.
Martin Ender
2

PHP, 116 bytes

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

Versión en línea

Jörg Hülsermann
fuente
¿PHP no necesita comenzar <?php?
Pavel
@ Phoenix: hay un intérprete PHP independiente que no requiere la etiqueta de inicio. Eso es lo que normalmente se usa para jugar al golf.
@ ais523 En este caso, PHP se ejecuta desde la línea de comandos con la opción -R
Jörg Hülsermann
2

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

Función recursiva que usa el segundo LSB ordinal como una bandera para el truco abierto vs cerrado utilizado por muchos encontrados por Adnan (y probablemente otros). La cola golpea cuando la suma acumulativa de -1para abrir y 1para cerrar llega a cero. El índice se mantiene en una variable, ya que es más barato en bytes que el uso len(r), la indexación se basa en 1.

Pruébalo en línea!

Jonathan Allan
fuente
2

Ruby, 35 34 bytes

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

Basado en la respuesta de Dada Perl5 . La salida está indexada en 1. Requiere que se invoque al intérprete de Ruby con la -nopción ( while getsbucle implícito ).

Editar: Esto también es 35 34 bytes, pero es otro posible punto de partida para reducir aún más esta respuesta.

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

Edit2: Eliminado espacios innecesarios después p.

Edit3: Un par de respuestas de 34 bytes más.

~/[<{(\[](\g<0>)*[>})\]]/;p$&.size
p~/[<{(\[](\g<0>)*[>})\]]/+$&.size
Ray Hamel
fuente
2
Bienvenido a PPCG!
Pavel
1
¡Muy apreciado! :)
Ray Hamel
2

Python 3 , 59 55 50 49 bytes

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

La salida está indexada en 0. La fórmula para determinar la dirección del soporte fue descubierta por @ETHProductions y mejorada por @Adnan.

Pruébalo en línea!

Dennis
fuente
1

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. <>Por supuesto, los caracteres son especiales en Batch, así que no solo tengo que citarlos por completo, sino que ni siquiera puedo hacer trucos como hacerlos gotoetiquetas.

Neil
fuente
1

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}
Neil
fuente
0

C, 127 bytes

Probar en línea

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

Salida

2   ()
4   (<>)
8   <[]{<>}>
2   {}{}{}{}
8   [[]<>[]]
Khaled.K
fuente
Cualquier comentario, downvoter.
Khaled.K
No era el votante negativo, pero no creo que ayude que ya hubiera una presentación de C mucho más corta.
Ørjan Johansen