Introducción
Hay 3 clavos en la pared. Tienes un trozo de cuerda que se fija al marco con ambos extremos. Para colgar la imagen, enredaste la cuerda con las uñas. Pero antes de dejar ir la imagen: ¿Puedes predecir si la imagen se va a caer, solo mirando cómo se enrolla la cuerda alrededor de las uñas?
En el primer ejemplo, la imagen no se caerá. En el segundo ejemplo, la imagen se va a caer.
Reto
Dado el camino de la cuerda alrededor de las N
uñas, determine si la imagen se va a caer o no. Devuelva un valor verdadero si la imagen va a caer, y un valor falso de lo contrario.
Detalles
- Puede suponer que las uñas y la imagen están organizadas en una forma regular
N+1
, con la imagen en la parte inferior. - Puede suponer que no hay nudos en la cuerda, es decir, la cuerda se puede desenrollar continuamente desde uno de los dos extremos.
- Cada clavo se enumera en sentido horario con una letra del alfabeto. Puede suponer que hay como máximo 26 uñas (AZ).
- Una envoltura en sentido horario alrededor de un clavo se denota con la letra minúscula, una envoltura en sentido antihorario se denota con una letra mayúscula.
El primer ejemplo de arriba se codificará como BcA
, el segundo ejemplo se codifica como CAbBac
.
Para el lector inclinado: este problema es equivalente a determinar si un elemento del grupo libre , generado por el conjunto de clavos, es la identidad o no. Esto significa que es suficiente cancelar repetidamente subcadenas como aA
o Aa
hasta que haya alcanzado un punto fijo. Si el punto fijo es una cadena vacía, este es el elemento neutral, de lo contrario no lo es.
Ejemplos
Picture will fall:
Aa
CAbBac
aBbA
DAacAaCdCaAcBCBbcaAb
ARrQqRrUuVHhvTtYyDdYyEKRrkeUWwua
AKkQqEeVvBESWwseYQqyXBbxVvPpWwTtKkVHLlWwNBbAanYYyyhWwEJZUuNnzjYyBLQqQqlEGgebeEPLlTtZzpUuevZzSsbXSGgsUuLlHhUQquPpHUuFfhTZzIitGgFAaBRrBbbYXxOoDZTDdtzVvXxUudHhOVvoUuXKkxyBEeLlbFfKkHhfVAaQqHAaJjODdoVvhSsZzMZzmPpXNBbnxBbUuSSsUuDRrdNnUusJDIiUuIidCEGgeMmcLlDPOopdTEeQqCAETtNnYyeGUuPEFfSsWwHheAaBbpgCcOHUuhAaCcoEFBbfeaFHhfcCFFffNncGFfgtjMVUuKAakvKkXxLlTMmtmOFfoUuXSsYZzLXxlyxUuRPZzTtprSsWwRrPLlpGgMmKRrDHhdRCcUurYNnKCckykXJjxWwUSsJjKkLlKkuBbBbOoWwWwIiUuPDdBbCcWHBbCFfcDdYBbLlyVvSsWGgEewCchDdYywAaJjEepPpPpQXxZzFfLGXxglNnZzYDdyqCcKWXxwXxQqXTtxkFfBSSAasTFftZzsXGgxSsLlLlbZzAaCCccXVvYyxTIiOoBbFftCVQqDdBbGgAavQqKkDPpKTCctRrkdcvAaQWOowLOolqVMmvZAaHCBbcPphIiRKkrLlzFMOomDIiXJjIixMmdNnMHhmfNTtIiKkSDdTtsVvHhnAaNSVvTUutNnXxsGIiXxPpPHhUupgNnAaAAOoaaIiHJjhVvLlnYyXxQqSsTtKJjkBbNnVvEYCcFfMHGghBbmNnEeJTtjJjWYywyeNWwDIiZYyzOodnMQqmVvCcQqxVvGNnEeNBbngVvUGgYyBbDdVvIiAAaauPpQKDdEekNnVLlvHhGSDIidPZzpsPCcpgQqKkQqNOonLlIiLlJjqPAaPXxTtppYyCPpHhCIicARBbracXxWwXEVUuUuGgZHhzBSsbvGgFfeVvxLlNKknWwBLlIibWOowNnRSsrSEeKAakOosLZzZRrHhzTtTFfUuNnOKkotXxTtla
Picture will not fall:
A
BcA
ABCD
aBaA
bAaBcbBCBcAaCdCaAcaCAD
ARrQqRrUatuVHhvTYyDdYyEKRrkeUAua
AEEeQqNneHhLlAIiGgaECXxcJjZzeJFfVWwDdKkvYWwyTJjtCXxANIinaXWwxcTWwtUuWwMmTBbVWIiFLlWwZzfwPLlEepvWZzwKkEYEeWXxwySXTtEexRIiNBbnWAaTtQqNnBMSsWwOombwWwPVPpGPpgYyvDdpBbrQqHhUusKRrDAVvadLlWwOZzokGJCXSSssXxxJPpGIigZzjJjLlOoNRrnPpcMZzmjgJjNDEeQqWKkNTtnSswIidCcnYBGgbyJSsjPpIiMmMmMmSNnWVvwZzIQqLXHhxTPptlisOoeTtTtYMmVvPpyKNnMFfmkXxSVvsCGJjXxgXYJPpjWwQIiXxqyDdxFfDdAaRNnJjrctHBbZzhEQqMmeCcRBbrGgAaAaJNnRrYyWwSDdVvsJOojQGgWWwIBbiwRrqJjjWwOoFPMmDdRrQOoqNnRrDPJjpMmdPpGFfVvWUuwgpWCcNnPpwfUXCcZzJjUSsuXxxUuuRGgHhrSQqJjOosMMTtmHhmKkXxDdLlWwjSUuAaMmKYyksZzVvPZzVEeVvvHhZZOozBbzMmZCczYyGgISsiQqpXxMmXxEMmeRrAGgaGgMOGgomZFfDdzSSssBGPpgbTtBbOoRWWwGgLJjlEeGgLDdRrUulNnZzJjJjUKkuXxFfwATtaZzLVvlWwSsMmrBAaELleGBLFflbgHhbIFfiBbPpTWZzwKkKLASsaTJYyjtBbBbWwIiZCcWwzIiZLlUTtuBbYyBbIizTJjtLTtDOOoBbodBbllSsUGgLlAKkauYykUuUNnPpuDFfAaLNVvnVvlHhdMmBAaBbIiVRrGWOoPpwgWXwKkvJjOoTtYCUucVGgYyLlVvFfvRrMmySsDdbtICZzcNnINSOosDQAaXoxRGgKkrqdZznDdXxZzMGgmiJjNnACcMQqmaNnWZzUOuwTVvAJjSsaRrGgSsTtOMmRroVvRrtAVGgvMmaINniDGCcOogRrWwMVvYFfyTtmTtVvOoOIiodRrGgAxaSsGgiJja
Respuestas:
Retina , 21 bytes
Pruébalo en línea!
Al igual que la solución de flawr, esto simplemente elimina repetidamente pares mayúsculas / minúsculas adyacentes y luego verifica si el resultado está vacío o no.
En cuanto a cómo uno coincide con un par mayúscula / minúscula:
fuente
MATLAB, 76 bytes
Octava,827977 bytes¡Esta podría ser la primera vez que veo que MATLAB es en realidad más corto que Octave (en un byte completo)!
Nueva respuesta en MATLAB:
Respuesta en octava:
Guardado
trescinco bytes gracias a flawr.~nnz(c)
es más corto queisempty(c)
, y'Aa'
es dos bytes más corto que[0,32]
.¡Pruébelo en línea en la versión Octave!
Explicación:
c=input('')
pide al usuario su aporte. Lo definimosk='Aa'
como una matriz de caracteres.while k++<1e5
: Mientras bucle donde ambos elementos enk
se incrementan cada iteración,Aa
,Bb
,Cc
y así sucesivamente. El bucle continuará hasta que el elemento más grande sea1e5
, que debería ser lo suficientemente alto para la mayoría de las cadenas. Se puede aumentar9e9
sin aumentar el recuento de bytes.Tomaremos la
strrep
función en pasos, comenzando desde el medio.Al usar
mod(k,64)
, obtendremos lo siguiente cuando lleguemos al final del alfabeto (si volvemos a convertir losk
caracteres):Como puede ver, habrá algunos símbolos en el medio, pero luego se ajustará y comenzará con el alfabeto nuevamente, pero ahora con las letras minúsculas primero. Esta es una forma muy corta de verificar ambos
Aa
yaA
.['',65+mod(k,64)]
concatena los valores numéricos de lamod
llamada, con una cadena vacía, convirtiendo los números en caracteres.strrep
se utiliza para eliminar elementos de la cadenac
y devolverlo. Buscará todas las apariciones dek
la cadena y la reemplazará con una cadena vacía.Después de las
1e5
iteraciones, tendremos una cadena vacía o una cadena no vacía. Verificamos si hay elementos en elc
usonnz(c)
. Volvemosnot(nnz(c))
, por lo tanto,1
si está vacío, y0
si quedan caracteres enc
fuente
Minkolang 0.15 , 30 bytes
Pruébalo aquí!
Explicación
La naturaleza toroidal de Minkolang se aprovecha aquí para eliminar la necesidad de un bucle externo. La idea general aquí es verificar si los dos elementos superiores de la pila están separados por 32 unidades (lo que significa que son un par mayúscula / minúscula), y si lo están, desactívelos. Como esto se hace "en tiempo real", por así decirlo, la anidación de pares se maneja correctamente.
fuente
Haskell, 62 bytes
Pruébalo en línea
Crédito a flawr para el
abs
y Laikoni para elfromEnum
mapa .La función auxiliar
%
toma una cadena ya simplificadal
y antepone el símboloa
antes de simplificar el resultado. Sil
comienza con el carácter inverso aa
, se cancelan. De lo contrario,a
simplemente se antepone. Tenga en cuenta que no se necesita más simplificación en esta etapa.La función principal
f
antecede y simplifica cada personaje a su vez a través de afoldr
. Luego, verifica si el resultado está vacío.Para verificar si dos caracteres son casos opuestos y, por lo tanto, deben cancelarse, vea si sus valores ASCII difieren en 32. Cada elemento se procesa
fromEnum
antes de pasar a%
.fuente
05AB1E , 17 bytes
Pruébalo en línea!
Explicación
fuente
Haskell ,
98 97 8581 bytesEsta es solo una implementación ingenua que intenta repetidamente cancelar las letras adyacentes hasta que no haya más cambios, y luego determina el resultado a partir de eso.
¡Gracias @nimi por -12 bytes y @xnor por otros -4 bytes!
Pruébalo en línea! o Verifique todos los ejemplos!
fuente
f=null.until(\a->r a==a)r.map fromEnum
debería guardar dos bytes.(\a->r a==a)
puede ser((==)=<<r)
.=r l
al
, la idea es que es suficiente hacer solo un reemplazo por ejecución.=<<
, parece mágico XD=<<
es como>>=
pero con los argumentos intercambiados. La expresión a menudo aparece como en la forma((==)=<<r)
que significa "es invariante bajor
".Mathematica, 102 bytes
Función sin nombre que toma una cadena alfabética como entrada y devuelve
True
oFalse
.El corazón de la implementación es crear una función que elimine cualquier par de cancelación, como
"Pp"
o"gG"
, de una cadena. La expresión{Join[a=Alphabet[],A=ToUpperCase@a],A~Join~a}
produce un par ordenado de listas de caracteres, siendo la primera lista{"a","b",...,"Z"}
y el segundo ser{"A","B",...,"z"}
. Entonces#<>#2&~MapThread~
produce una lista donde se han concatenado los elementos correspondientes de estas dos listas, es decir,{"aA","bB",...,"Zz"}
. La expresión divertida""|##&@@
entonces (a través de la magia de la secuencia de argumentos##
) produce una lista de alternativas"" | "aA" | "bB" | ... | "Zz"
; finalmente,StringDelete[...]
es una función que elimina cualquier aparición de cualquiera de esas alternativas de una cadena.Ahora es suficiente aplicar repetidamente esa función a la cadena de entrada hasta que el resultado no cambie, lo que se logra con
~FixedPoint~#
, y luego probar si el resultado es la cadena vacía con""==
.fuente
JavaScript (ES6), 73 bytes
A diferencia de .NET, JavaScript no tiene forma de desactivar la distinción entre mayúsculas y minúsculas en el medio de una coincidencia, por lo que tenemos que encontrar todas las subcadenas de letras repetidas entre mayúsculas y minúsculas, y luego eliminar cualquier par de caracteres adyacentes que no coincidan, lo que en este punto debe ser un par mayúscula / minúscula.
fuente
Perl, 28 bytes
Explicación:
Perl permite incluir una expresión regular generada dinámicamente dentro de una expresión regular estándar.
Las
.
coincide con cualquier cosa.El
(??{
es el comienzo de la expresión regular generada.La
$&
variable contendrá toda la cadena coincidente hasta ahora, que en este caso es lo que.
coincida.El
^
operador realiza xor numérico o xor de cadena, dependiendo de los valores de los operandos. En este caso, será la cadena xor.El
' '
es solo una cadena que contiene un espacio, que convenientemente tiene el valor ascii (o unicode!) De 32. Cuando un espacio se corrige con un carácter en el rango az o AZ, cambiará de mayúscula a minúscula o tornillo de banco viceversaEl
})
es el final de la expresión regular generada.1 while s/whatever//
buscará repetidamente un patrón y lo reemplazará con la cadena vacía.$_
es la variable por defecto. Esta variable es sobre lo que Perl hace cosas divertidas y emocionantes cuando no especificas otra variable. Aquí lo estoy usando para devolver un valor verdadero o falso, ya que una cadena de longitud cero es falsa y una cadena de longitud distinta de cero que no es igual"0"
es verdadera. También estoy asumiendo que la cadena de entrada se colocó originalmente en ella.Pruébalo aquí
fuente
!
antes de la final$_
. Si mantenerlo de esta manera está bien con usted, puede guardar 4 bytes cambiándolo as/.(??{$&^' '})//&&redo
+1 byte para la-p
bandera. No funcionará en una subrutina de la forma en que lo tiene ahora porque en{ code }
realidad no es un bucle (por&&redo
lo tanto , no funcionará), sino que lo-p
coloca dentro de unwhile
bucle.' '
con$"
. Eche un vistazo a esto para ver cómo se ve el código.Prólogo (SWI) , 151 bytes
Toma mucho tiempo correr en los casos falsos más largos debido al retroceso.
Pruébalo en línea!
Sin golf
fuente
MATL , 20 bytes
Pruébalo en línea! O verifique todos los casos de prueba (lleva un tiempo).
Explicación
fuente
Mathematica, 65 bytes
fuente
JavaScript (Node.js) , 47 bytes
Pruébalo en línea!
fuente
Python 3 , 71 bytes
Pruébalo en línea!
fuente