Una actividad que a veces hago cuando estoy aburrido es escribir un par de caracteres en pares coincidentes. Luego dibujo líneas (sobre las partes superiores nunca debajo) para conectar estos personajes. Por ejemplo, podría escribir y luego dibujaría las líneas como:
O podría escribir
Una vez que he dibujado estas líneas, trato de dibujar bucles cerrados alrededor de los fragmentos para que mi bucle no se cruce con ninguna de las líneas que acabo de dibujar. Por ejemplo, en el primero, el único bucle que podemos dibujar es alrededor de todo, pero en el segundo podemos dibujar un bucle alrededor de solo s (o todo lo demás)
Si jugamos un poco con esto, descubriremos que algunas cadenas solo se pueden dibujar para que los bucles cerrados contengan todas o ninguna de las letras (como nuestro primer ejemplo). Llamaremos a estas cadenas cadenas bien vinculadas.
Tenga en cuenta que algunas cadenas se pueden dibujar de múltiples maneras. Por ejemplo, se puede dibujar de las dos formas siguientes (y una tercera no incluida):
Si se puede dibujar una de estas formas de modo que se pueda hacer que un bucle cerrado contenga algunos de los caracteres sin intersectar ninguna de las líneas, entonces la cadena no está bien vinculada. (entonces no está bien vinculado)
Tarea
Su tarea es escribir un programa para identificar cadenas que estén bien vinculadas. Su entrada consistirá en una cadena donde cada carácter aparece un número par de veces, y su salida debe ser uno de dos valores consistentes distintos, uno si las cadenas están bien vinculadas y el otro en caso contrario.
Además, su programa debe ser un significado de cadena bien vinculado
Cada personaje aparece un número par de veces en su programa.
Debería generar el valor verdadero cuando se pasa a sí mismo.
Su programa debe poder producir la salida correcta para cualquier cadena que conste de caracteres de ASCII imprimible o de su propio programa. Con cada personaje apareciendo un número par de veces.
Las respuestas se puntuarán como sus longitudes en bytes, siendo menos bytes una mejor puntuación.
Insinuación
Una cadena no está bien vinculada si existe una subcadena estricta contigua no vacía, de modo que cada carácter aparezca un número par de veces en esa subcadena.
Casos de prueba
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False
fuente
abcbca -> False
.there
.Respuestas:
Regex (ECMAScript 2018 o .NET),
1401261181009882 bytes^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)
Esto es mucho más lento que la versión de 98 bytes, porque
^\1
queda de la búsqueda anticipada y, por lo tanto, se evalúa después. Vea a continuación un cambio simple que recupera la velocidad. Pero debido a esto, los dos TIO a continuación se limitan a completar un conjunto de casos de prueba más pequeño que antes, y el .NET es demasiado lento para verificar su propia expresión regular.Pruébalo en línea! (ECMAScript 2018) ¡
Pruébelo en línea! (.RED)
Para eliminar 18 bytes (118 → 100), robé descaradamente una optimización realmente agradable de la expresión regular de Neil que evita la necesidad de poner una mirada hacia adelante dentro de la mirada negativa hacia atrás (produciendo una expresión regular sin restricciones de 80 bytes). Gracias Neil!
¡Eso se volvió obsoleto cuando dejó caer unos increíbles 16 bytes más (98 → 82) gracias a las ideas de jaytea que llevaron a una expresión regular sin restricciones de 69 bytes! Es mucho más lento, ¡pero eso es golf!
Tenga en cuenta que los
(|(
no-ops para hacer que la expresión regular esté bien vinculada tienen el resultado de hacer que se evalúe muy lentamente en .NET. No tienen este efecto en ECMAScript porque las coincidencias opcionales de ancho cero se tratan como no coincidencias .ECMAScript prohíbe los cuantificadores de afirmaciones, por lo que esto hace que el golf sea más difícil para los requisitos de fuentes restringidas . Sin embargo, en este punto está tan bien jugado que no creo que levantar esa restricción en particular abriría más posibilidades de golf.
Sin los caracteres adicionales necesarios para que pase las restricciones (
10169 bytes):^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))
Es lento, pero esta edición simple (por solo 2 bytes adicionales) recupera toda la velocidad perdida y más:
^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))
Lo escribí usando lookahead molecular (
10369 bytes) antes de convertirlo en lookbehind de longitud variable:^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))
Y para ayudar a que mi expresión regular esté bien vinculada, he estado usando una variación de la expresión regular anterior:
(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1
Cuando se usa con
regex -xml,rs -o
, esto identifica una subcadena estricta de la entrada que contiene un número par de cada carácter (si existe). Claro, podría haber escrito un programa sin expresiones regulares para hacer esto por mí, pero ¿dónde sería la diversión en eso?fuente
Jalea, 20 bytes
Pruébalo en línea!
La primera línea se ignora. Solo está allí para satisfacer la condición de que cada personaje aparezca un número par de veces.
La siguiente línea primero
Ġ
enruta los índices por su valor. Si luego tomamos la longitud de cada sublista en la lista resultante (Ẉ
), obtenemos el número de veces que aparece cada carácter. Para verificar si alguno de estos no es par, obtenemos el últimoḂ
de cada recuento y preguntamos si existeẸ
un valor verdadero (distinto de cero).Por lo tanto, este enlace auxiliar devuelve si una subcadena no se puede marcar.
En el enlace principal, tomamos todas las subcadenas de la entrada (
Ẇ
),Ṗ
desactivamos la última (para que no verifiquemos si se puede encerrar en un círculo toda la cadena) y ejecutamos el enlace auxiliar (Ç
) en una€
subcadena ach. El resultado es entonces si todas lasẠ
subcadenas no pueden encerrarse en un círculo.fuente
J , 34 bytes
Pruébalo en línea!
-8 bytes gracias a FrownyFrog
original
J , 42 bytes
Pruébalo en línea!
explicación
fuente
abc
, solo la entrada de Perl no "falla" en ella. (Sin embargo, tiene otros problemas.)1:@':.,02|~*'=1(#.,)*/@(0=2|#/.~)\.\
2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\
también parece válidoPython 3.8 (prelanzamiento) , 66 bytes
Pruébalo en línea!
La era de las expresiones de asignación está sobre nosotros. Con PEP 572 incluido en Python 3.8, el golf nunca será el mismo. Puede instalar la versión preliminar del desarrollador 3.8.0a1 aquí .
Las expresiones de asignación le permiten usar
:=
para asignar una variable en línea mientras evalúa ese valor. Por ejemplo,(a:=2, a+1)
da(2, 3)
. Por supuesto, esto puede usarse para almacenar variables para su reutilización, pero aquí vamos un paso más allá y lo usamos como un acumulador en una comprensión.Por ejemplo, este código calcula las sumas acumulativas
[1, 3, 6]
Observe cómo con cada paso por la comprensión de la lista, la suma acumulativa
t
aumentax
y el nuevo valor se almacena en la lista producida por la comprensión.Del mismo modo,
b:=b^{c}
actualiza el conjunto de caracteresb
para alternar si incluye caracteresc
y evalúa el nuevo valor deb
. Por lo tanto, el código[b:=b^{c}for c in l]
itera sobre caracteresc
enl
y se acumula el conjunto de caracteres visto un número impar de veces en cada prefijo no vacío.Esta lista se verifica en busca de duplicados al convertirla en una comprensión establecida y ver si su longitud es menor que la de
s
, lo que significa que algunas repeticiones se colapsaron. Si es así, la repetición significa que en la porción des
visto entre esos momentos cada carácter encontró un número par de números, haciendo que la cadena no esté bien vinculada. Python no permite conjuntos de conjuntos por no ser compartibles, por lo que los conjuntos internos se convierten en cadenas.El conjunto
b
se inicializa como argumentos opcionales y se modifica con éxito en el ámbito de la función. Me preocupaba que esto hiciera que la función no sea reutilizable, pero parece restablecerse entre ejecuciones.Para la restricción de fuente, los caracteres no apareados se rellenan en un comentario al final. Escribir en
for(c)in l
lugar defor c in l
cancelar los padres adicionales de forma gratuita. Lo colocamosid
en el conjunto inicialb
, que es inofensivo ya que puede comenzar como cualquier conjunto, pero el conjunto vacío no se puede escribir{}
porque Python creará un diccionario vacío. Dado que las letrasi
y sed
encuentran entre las que necesitan emparejamiento, podemos poner la funciónid
allí.Tenga en cuenta que el código genera booleanos negados, por lo que se dará correctamente
False
sobre sí mismo.fuente
Python 2 , 74 bytes
Pruébalo en línea!
Itera a través de la cadena, haciendo un seguimiento
P
del conjunto de caracteres vistos un número impar de veces hasta ahora. La listad
almacena todos los valores pasados deP
, y si ve el actualP
ya end
, esto significa que en los caracteres vistos desde ese momento, cada carácter ha aparecido un número par de veces. Si es así, verifique si hemos pasado por toda la entrada: si lo hemos hecho, acepte porque toda la cadena está emparejada como se esperaba y, de lo contrario, rechace.Ahora sobre la restricción de la fuente. Los personajes que necesitan emparejarse se rellenan en varios lugares inofensivos, subrayados a continuación:
Se
f<s
evalúa0
mientras se emparejaf
, aprovechando que el nombre de la función tambiénf
se define (cuando se llama a la función).0^0
Absorbe un^
símbolo.El
0
inP={0}
es lamentable: en Python se{}
evalúa como un dict vacío en lugar de un conjunto vacío como queremos, y aquí podemos poner cualquier elemento que no sea de carácter y será inofensivo. Sin embargo, no veo nada de repuesto, y lo he puesto0
y duplicadobmn0
, costando 2 bytes. Tenga en cuenta que los argumentos iniciales se evalúan cuando se define la función, por lo que las variables que definimos nosotros mismos no se pueden poner aquí.fuente
Perl 6 , 76 bytes
Pruébalo en línea!
A Cualquiera que sea lambda que devuelva un cruce de ninguno o ninguno de los cruces que pueden ser boolificados a un valor verdadero / falso. Sin embargo, recomendaría no eliminar el
?
que boolifica el resultado de retorno, de lo contrario, la salida se vuelve bastante grande .Esta solución es un poco más compleja de lo que es necesario, debido a varias funciones implicadas ser disociados, por ejemplo
..
,all
,>>
,%%
etc. sin la restricción fuente, esto podría ser 43 bytes:Pruébalo en línea!
Explicación:
fuente
Perl 5
-p
,94,86,78 bytessalida 0 si está bien enlazado 1 de lo contrario.
78 bytes
86 bytes
94 bytes
Cómo funciona
-p
con el}{
truco final a la salida$\
al finalm-.+(?{
..})(?!)-
, para ejecutar código sobre todas las subcadenas no vacías (.+
primero coincide con toda la cadena y después de ejecutar el código entre(?{
..})
retrocesos debido a un error forzado(?!)
$Q|=@q&grp,
basura debido a la restricción de origen$\|=
entero a nivel de bit o asignación, si hay casi un 1,$\
será 1 (verdadero), por defecto está vacío (falso)$&eq$_
el caso en el que el sbustring es la cadena completa se grabó en bits sin^
"ninguna ocurrencia de caracteres extraños"($g=$&)=~/./g
copiar la subcadena coincidente en$g
(porque se sobrescribirá después de la próxima coincidencia de expresiones regulares) y devolver la matriz de caracteres de la subcadena./^/
basura que se evalúa a 1grep
1&(@m=$g=~/\Q$_/g),
para cada carácter en la subcadena, obtenga la matriz de caracteres para que$g
coincida, la matriz en escalar evalúa su tamaño ygrep
filtrar los caracteres con una ocurrencia impar1&x
es equivalente ax%2==1
fuente
Retina ,
15096 bytesPruébalo en línea! El enlace incluye casos de prueba, incluido él mismo. Editar: bajó un poco la expresión regular original con la ayuda de @Deadcode, luego retrocedió un poco menos de manera extravagante para mantener el diseño de origen. Explicación:
Afirme que no
\3
existe una subcadena que coincida con las siguientes restricciones.Afirme que la subcadena no es la cadena original completa.
Afirma que no hay un carácter
\6
tal que:Para pasar la restricción de diseño de origen, reemplacé
((((
con(?:(^?(?:(
y((
con(|(
. Todavía tenía una restricción fuente de))
la izquierda y los caracteres!()1<{}
sobra, así que cambié una+
en{1,}
e insertó el inútil(?!,<)?
para consumir el resto.fuente
C # (compilador interactivo de Visual C #) ,
208206200198 bytesPruébalo en línea!
-2 bytes gracias a @KevinCruijssen!
Finalmente lo puse por debajo de 200, por lo que podría haber terminado jugando al golf por ahora :) Terminé creando un segundo TIO para probar las cosas en función de una respuesta anterior.
Pruébalo en línea!
Cosas que hicieron difícil esta tarea:
==
no estaba permitido++
no estaba permitidoAll()
función Linq no estaba permitidaCódigo comentado a continuación:
fuente
Python 2 , 108 bytes
Pruébalo en línea!
-2 gracias a Ørjan Johansen .
fuente
Brachylog , 16 bytes
Pruébalo en línea!
Imprime
false.
para instancias verdaderas ytrue.
para instancias falsas. La versión TIO es demasiado lenta para manejarse sola, pero está claramente bien vinculada ya que es una cadena con caracteres únicos repetidos dos veces.Explicación
fuente
05AB1E ,
2220 bytesEmite
1
si la cadena está bien vinculada y0
si la cadena no está bien vinculada.Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
El programa base es
ŒsKεsS¢ÈP}à
( 11 bytes ), que genera0
si está bien vinculado y1
si no está bien vinculado. El trailingÈ
(is_even) es un semi-no-op que invierte la salida,1
por lo tanto, para cadenas bien vinculadas y0
para cadenas no bien vinculadas. Las otras partes son no-ops para cumplir con las reglas del desafío.fuente