Soportes entrelazados

30

Escriba un programa o función que tome una cadena de ocho bytes que contenga uno de cada uno de los caracteres ()[]{}<>dispuestos de cualquier manera de manera que coincidan los cuatro tipos de paréntesis respectivos. Por ejemplo, ]<([){}>es una entrada no válida porque los corchetes no coinciden (aunque todos los demás sí).

Imprima o devuelva un número entero de 0a 6que denote cuántos de los seis posibles emparejamientos de los cuatro tipos de paréntesis están enclavados. Los pares de tipo de paréntesis se consideran entrelazados si se produce exactamente un paréntesis de un tipo entre los paréntesis del otro tipo. Así ([)]y [(])están entrelazados, pero ()[], [](), ([]), y [()]no lo son.

El código más corto en bytes gana.

Ejemplos de entrada / salida

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

Respuestas:

17

CJam, 18

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

Gracias Isaac por algunas ideas de golf :)
Pruébelo en línea o pruebe todos los ejemplos

Explicación:

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
aditsu
fuente
1
Oh, ¿entonces eres el tipo que creó CJam? ¡Me debes todas las respuestas que perdí que fueron golpeadas por las respuestas de CJam! ;)
kirbyfan64sos
66
@ kirbyfan64sos bueno, será mejor que comiences a aprenderlo también si quieres ganar :)
aditsu
99
7~f&? Ya me gusta esta respuesta, y ni siquiera he leído el resto.
Dennis
11

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

Esto analiza las cosas entre cada par de corchetes coincidentes y cuenta el número de corchetes individuales izquierdo o derecho presentes. La suma de estos dividida por dos es la salida.

Estoy seguro de que los golfistas mejores que yo podrían jugar mucho más.

Pasatiempos de Calvin
fuente
31
Bueno, sucedio. Calvin publicó una respuesta. Los tiempos finales están sobre nosotros.
Alex A.
4

GNU sed -r, 147

La salida está en unario según esta meta-respuesta .

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

Nota: Reemplace \tcon tabcaracteres reales para obtener la puntuación correcta. Sin embargo, el programa funcionará de cualquier manera con GNU sed.

Pruébalo en línea .

Trauma digital
fuente
3

Perl, 77 bytes

76 código + 1 interruptor

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

Toma información de STDIN y el programa debe iniciarse de nuevo para cada entrada.

Explicación

  1. Reemplace todos los soportes de cierre con sus contrapartes abiertas ( y/.../.../).
  2. Luego, para cada carácter en la cadena de entrada ( for$x...), incremente un contador para el carácter ( $h{$x}++).
  3. Si es la segunda vez que vemos al personaje, obtenga la distancia entre las dos ocurrencias ( length $1) y elimine ambas ocurrencias de este carácter de la cadena. Por ejemplo, si la cadena era ([{([{<<, hay dos caracteres [y {entre los dos (s. Después de que (se procesan los s, la cadena se convierte [{[{<<y agregamos 2 al número total ( $z) de paréntesis entrelazados.
  4. El resultado se toma de $z( $_=$z)
svsd
fuente
3

Pyth, 20 bytes

JmC/CdTzlsm@FPcsJd{J

Banco de pruebas

JmC/CdTz: Primero, esto convierte cada par de símbolos en un solo carácter al asignar cada carácter de entrada a su código de caracteres ( Cd) dividido por 10 ( / T), que es el mismo para cada par pero diferente entre todos los pares. El número resultante se convierte de nuevo en un personaje para los fines que se revelarán más adelante ( C). La lista resultante de caracteres se guarda en J.

lsm@FPcsJd{J: Ahora, asignamos los caracteres únicos en J( {J). Comenzamos cortando la cadena formada mediante la concatenación Jusando el carácter actual como el delímetro ( csJd). Un par de paréntesis se superpone al par actual si aparece en el segundo grupo y en el primer o tercer grupo. Para evitar el doble conteo, solo contaremos el primer y segundo caso de grupo. Entonces, eliminamos el tercer grupo ( P) y tomamos la intersección de los grupos restantes ( @F). Finalmente, concatenamos los caracteres superpuestos ( s) e imprimimos la longitud del resut ( l).

isaacg
fuente
3

Pitón 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)

Basada en mi solución CJam.

aditsu
fuente
3

Retina , 128 108 64 62 55 bytes

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

Donde <empty>representa una línea final vacía. Para fines de conteo, coloque cada línea en un archivo separado y reemplace los caracteres \ncon saltos de línea reales. Para su comodidad, puede usar este código equivalente con la -smarca de un solo archivo:

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

La salida es unaria .

Explicación

El primero (le dice a Retina que ejecute todo el código en un bucle hasta que una iteración deje de cambiar la cadena. En este caso, siempre iterará cuatro veces, una para cada tipo de paréntesis.

T`)]>}`([<{

Esto simplemente convierte cada corchete de cierre en el corchete de apertura correspondiente, de modo que podamos hacer coincidir los corchetes correspondientes con una simple referencia posterior más adelante. (Esta etapa se convierte en un no-op después de la primera iteración. Solo se incluye en el bucle, porque Tya requería un backtick, por lo que agregar el (costo solo es uno en lugar de dos bytes).

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

Esto reemplaza el par de corchetes más a la izquierda con nuevas líneas. Usamos \Dpara distinguir los corchetes de los 1s que agregamos más adelante en el ciclo para contar. Al (.*)final se asegura que solo se reemplaza un par (porque las coincidencias no pueden solaparse).

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

Toda la expresión regular está en una búsqueda anticipada, por lo que coincide con una posición . Más específicamente, coincide con una posición para cada par de corchetes que ha sido separado por los otros corchetes que acabamos de convertir en nuevas líneas. A 1se inserta en cada una de estas posiciones. Podemos dejar los 1s allí, porque no afectan a ninguna de las otras expresiones regulares (porque los \Ds se aseguran de que no coincidamos accidentalmente).

\n
<empty>

Finalmente, eliminamos las nuevas líneas (es decir, los marcadores de posición para el tipo actual de corchetes); esto significa que hemos reducido el problema restante a una cadena de longitud 6 que contiene solo 3 tipos de corchetes, pero de lo contrario funciona exactamente igual.

Al final, solo 1quedarán los s que insertamos, y su cantidad corresponde exactamente al número de paréntesis entrelazados.

Martin Ender
fuente
2

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

Guau. Eso fue divertido. Esbocé una idea de respuesta cuando apareció este desafío por primera vez, pero tenía más de 150 bytes de longitud y no quería esforzarme por jugarlo. Me encontré con esta idea en mi cuaderno ayer y decidí que no dejaría de pensar en ello hasta que lo hubiera jugado por completo. Terminé escribiendo dos algoritmos completamente nuevos, el primero de los cuales terminó varios bytes más cortos después de jugar alrededor de 25 bytes con toneladas de pirateo de bits.

Cómo funciona

Primero establecemos variables ay bto 0. aes una matriz binaria de 4 bits de los pares de paréntesis en los que estamos actualmente, y bes una matriz binaria de 16 bits cuyos pares de paréntesis están unidos entre sí.

A continuación, recorrer cada carácter cen x, y cada carbón den '0123'. Primero determinamos con qué tipo de soporte cestá e=c.charCodeAt()/26-1|0. Los códigos de caracteres decimales de cada tipo de paréntesis son los siguientes:

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

Al dividir por 26, restar 1 y piso, los asignamos a 0, 1, 2 y 3, respectivamente.

Luego verificamos si este número es igual al valor actual de d. Si es así, estamos entrando o saliendo del dtipo de soporte th, por lo que cambiamos el dbit th acon a^=1<<d. Si no lo es, sino que están dentro del dtipo de soporte XX, tenemos que darle la vuelta al eésimo bit en la dsección de 4 bits º de b. Esto se hace así:

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

(a>>d&1)Devuelve el dbit de entrada a. Si estamos dentro del dtipo de soporte, esto devuelve 1; de lo contrario, devuelve 0. A continuación, desplazamos esto a la izquierda por d*4+ebits, y XOR bpor el resultado. Si estamos dentro del dtipo de corchete, este XOR es el d*4+ebit de b; de lo contrario, no hace nada.

Al final de todo el bucle, bcontendrá un número de 1 bits igual al doble del valor de retorno deseado. Pero aún necesitamos averiguar cuántos bits es esto. Ahí es donde fentra la subfunción :

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

Si yes 0, esto simplemente devuelve 0. De lo contrario, toma el último bit de ywith y%2, luego agrega el resultado de ejecutar todo excepto el último bit a ytravés de la función nuevamente. Por ejemplo:

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

Realizamos besta función y dividimos el resultado entre 2, y ahí está nuestra respuesta.

ETHproducciones
fuente
1

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;

Sin golf:

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  
Jeto
fuente