En este desafío, se le pasan dos palabras: su trabajo es determinar si son adyacentes .
Dos letras son adyacentes si:
- Son la misma letra, o
- Son lexicográficamente adyacentes.
Por ejemplo, J es adyacente a I , J y K solamente. Z no es adyacente a A
Dos palabras son adyacentes si:
- Son de la misma longitud, y
- Cada letra es adyacente a una letra única en la otra palabra.
Por ejemplo, CAT es adyacente a SAD , como C> D, A> A, T> S .
FREE no es adyacente a GRRD (cada E necesita una letra para emparejarse) .
De entrada y salida
Se le pasan dos cadenas y necesita devolver un valor verdadero si son adyacentes, de lo contrario, un valor falso. Debe regresar dentro de un minuto para todos los casos de prueba a continuación.
Puede suponer que las cadenas solo contendrán letras alfabéticas en mayúsculas.
Las dos cadenas pueden pasarse como una lista, o concatenarse, con o sin comillas.
Casos de prueba
Verdad:
A A
A B
C B
DD CE
DE FC
ABCD BCDE
AACC DBBB
DJENSKE FDJCLMT
DEFGHIJKL HJLEHMCHE
IKLIJJLIJKKL LJLJLJLJLJHI
ACEGIKMOQSUWY BLNPRDFTVHXJZ
QQSQQRRQSTTUQQRRRS PQTTPPTTQTPQPPQRTP
ELKNSDUUUELSKJFESD DKJELKNSUELSDUFEUS
Falsy
A C
A Z
B J
JK J
CC BA
CE D
DJENSKE GDJCLMT
DEFGHIJKL HJLHMCHE
IJKLIJKLKIJL LIJLLHJLJLLL
AWSUKMEGICOQY RSHXBLJLNQDFZ
QQSQQRRQSTTUQQQRRS PQTTPPTTQTPQPPQRTT
ELKNSDUVWELSKJFESD DKJELKNSUELSDUFEUS
Este es el código de golf , por lo que gana la respuesta válida más corta.
fuente
"A A"
?{'string1' 'string2'}
Sería aceptable una sola matriz del formulario ?Respuestas:
CJam,
141312 bytesPruébalo en línea! o verificar todos los casos de prueba a la vez .
Algoritmo
Let s y t ser ordenados dos palabras de la misma longitud. Para s y t a ser lexicográficamente adyacente (LA), es necesario y suficiente que todos los pares de sus caracteres correspondientes son también LA.
La condición es claramente suficiente para todas las palabras y necesaria para palabras de longitud 1 .
Ahora, supongamos que s y t tienen longitud n> 1 , y sea una y b ser los primeros caracteres, resp., De s y t .
Dado que s y t son LA, hay una cierta biyectiva φ entre los personajes de s y los personajes de t tal que x y φ (x) se Ángeles para todo x en s , lo que significa que | x - φ (x) | ≤ 1 para todas las x en s .
Deje c = φ (a) y d = φ -1 (b) . Debido a la minimidad de a y de b , a ≤ d (1) y b ≤ c (2) .
Además, desde b y d , y a y c , y LA, d ≤ b + 1 (3) y c ≤ a + 1 (4) .
Al combinar (1) y (3) , y (2) y (4) , obtenemos que a ≤ d ≤ b + 1 y b ≤ c ≤ a + 1 , de donde deducimos que a - 1 ≤ b ≤ a + 1 y, por tanto, que una y b son lA.
Ahora, combinando (1) y (4) , y (2) y (3) , obtenemos que c - 1 ≤ a ≤ d y d - 1 ≤ b ≤ c , de donde deducimos que c - 1 ≤ d ≤ c + 1 y, por tanto, que c y d son LA.
Por lo tanto, si redefinimos φ por φ (a) = b y φ (D) = c , | x - φ (x) | ≤ 1 se mantendrá para todas las x en s y, en particular, para todas las x en s [1:] .
De esta manera, es [0] = A y T [0] = b , y s [1:] y t [1:] , son LA.
Como s [1:] tiene una longitud n - 1 , esto demuestra la necesidad por inducción.
Código
fuente
C->Y, D->X
, y esas pueden simplemente no cruzarse.MATL , 10
1217bytesEsto utiliza el enfoque de Dennis : ordenar primero y comparar caracteres en posiciones coincidentes.
La entrada es una matriz de cadenas, con el formato
{'CAT 'SAD'}
.La salida es una matriz de ceros y unos. Un resultado es verdadero si contiene todos (se acuerda que es verdadero).
Utiliza la versión actual (10.2.1) , que es anterior a este desafío.
EDITAR: Se
Xl
ha cambiado el nombre de la función|
en las versiones más nuevas del idioma (yo
ya no es necesario). El siguiente enlace incluye esas modificaciones.Pruébalo en línea!
Explicacion :
Enfoque antiguo, que acepta las cadenas como entradas separadas: 12 bytes :
EDITAR : el código en el enlace ha sido modificado según los cambios en el idioma; Ver comentario arriba.
Pruébalo en línea !
Explicacion :
fuente
[1 0 1]
es falsa en MATL. Eso es útil[0 0]
es verdadera?C, 233 bytes
Puede probarlo guardando eso como
adj.h
y luego usando esteadj.c
archivo:Luego compila usando
gcc adj.c -o adj
. El resultado es:fuente
Python 2, 90 bytes
Función anónima simple, tengo que tener una verificación de longitud por separado porque
zip
solo contaminaré. Hay una función similar enitertools
(zip_longest
) que rellenaría cadenas vacías, pero sería bastante costoso.Prueba con
produce:
fuente
JavaScript (ES6), 86
90 94Editar 4 bytes guardados thx @Neil
Editar 2 4 bytes guardar thx @ Mwr247
Nota: comprobación de adyacencia en un par de letras. Tome el par como base 36 número n , si las letras son iguales, entonces
n = a*36+a = a*37
. Si hay una diferencia de 1, entoncesn = a*36+a+1 = a*37+1
on = a*36+a-1 = a*37-1
. Entoncesn % 37
debe ser 0, 1 o 36. Yn%37%36
debe ser 0 o 1.Nota 2: el '0' agregado se utiliza para garantizar que ayb tengan la misma longitud. Es más corto que
a.length==b.length
fuente
''
en lugar del primero,'0'
ya que no cambia el valor del análisis.b
clasificación con la referencia de caracteres:(a,b)=>[...[...a].sort(),0].every((x,i)=>parseInt(x+([...b].sort()[i]||0),36)%37%36<2)
= 86 bytesJavaScript ES6,
117 bytes116 bytes111 bytes109 bytesCasos de prueba
Crédito
fuente
[...s]
lugar des.split('')
?Pyth,
3731 bytes¡Pruébelo en línea con todos los casos de prueba!
Afeitado de 6 bytes mediante el uso de la notación reducida de reducción (en
-F
lugar de.U-bZ
)Solución inspirada en Dennis
Primera sumisión a codegolf!
Explicación
Podemos dividir la expresión en dos partes, que se comparan con la
&
salida del resultado. Trataré de explicar escribiendo algunos pseudo-PythonPrimero comprobamos que la longitud de las dos palabras es la misma
Luego, aplicamos el método de Dennis:
Luego usamos el
-
operador para filtrar todos los elementos de esa lista que no están en[Z1
([0, 1]
), y verificamos que el resultado sea una lista vacía conqY
fuente
JavaScript (ES6), 87 bytes
Utiliza una verificación de rango simétrico centrado en cero dividiendo por el valor máximo, luego truncando con un bit "o" (
|
). Más corto que tener que hacer dos controles, o uno conMath.abs()
.fuente
Haskell,
6763 bytesEjemplo de uso:
f "FREE" "GRRD"
->False
.Cómo funciona (nota:
f
está parcialmente libre de puntos y el segundo parámetrob
no aparece en la definición):Editar: @xnor encontró 4 bytes para guardar. ¡Gracias!
fuente
id x
No es justox
? ¿O qué tal[pred x..succ x]
?\x->map($x)[pred,id,succ]
, así queid
solo quedaban restos. Por supuesto lo..
supera todo. ¡Gracias!C, 172 bytes
Casos de prueba
fuente
PowerShell, 140 bytes
Podría ser posible acortar esto. Actualmente no es competitivo con Python o JavaScript, pero utiliza un enfoque ligeramente diferente, así que pensé que lo publicaría.
Explicación
Este código es realmente confuso para alguien que no domina PowerShell, por lo que intentaré descomponerlo en inglés lo mejor que pueda ...
Comenzamos con la entrada de
param($a,$b)
forma normal.El resto del código es en realidad una declaración, y se puede dividir
(...)-and(...)
para probar dos declaraciones booleanas con el-and
operador.Los parens de la izquierda se pueden dividir
(... -eq ...)
para probar la igualdad de dos objetos. En este caso, los objetos son la.Count
s (es decir, la longitud) de dos nuevas matrices de caracteres. Cada par interno($a=[char[]]$a|sort)
toma la palabra de entrada original, la vuelve a lanzar como una matriz de caracteres, luego la ordena y la vuelve a guardar en la misma variable. Hacemos eso para ambos$a
y$b
. El lado izquierdo verifica que las palabras de entrada tengan la misma longitud. Si no tienen la misma longitud, esta mitad de la declaración booleana externa fallará y seFalse
generará.Moviéndonos hacia el lado derecho, nuevamente estamos probando dos declaraciones booleanas con
(... -and ...)
. El lado izquierdo comprueba si algo es mayor que o igual a negativo 1 con-ge-1
. El algo es el elemento cero de una matriz construida$c
, que es creada por:0..($a.count-1)
|%{...}
$a
y restamos el valor ASCII del carácter indexado en$b
|sort
ed por valor numéricoEl otro lado de la declaración toma el valor máximo
$c[-1]
de la matriz y asegura que sea menor o igual que 1 con-le1
.Por lo tanto, si las dos cadenas de entrada son realmente adyacentes, la
$c
matriz será algo así@(-1,-1,-1...0,0,0...1,1,1)
. Entonces el primer elemento será-1
y el último elemento será1
. Si no son adyacentes, la diferencia en los valores ASCII para un par particular será< -1
o> 1
, por lo que esta mitad de la prueba booleana externa fallará y seFalse
generará.Solo si ambos lados pasan se emitirán
True
y, por lo tanto, las cadenas son LA.fuente
Óxido,
269264 bytesExpandido:
Casos de prueba:
fuente
APL, 59 bytes (caracteres)
(61 si tenemos que suministrar {y}, 63 con f ←)
No soy el mejor APLer, pero es demasiado divertido.
(0=+/2≤|¨∊-/{⎕av⍳⍵}¨(⍺{⌈/⍴¨⍺⍵}⍵)⍴¨⍺[⍋⍺]⍵[⍋⍵])∧=/⍴¨∊¨⍺⍵
=/⍴¨∊¨⍺⍵
son las entradas igualmente largas?∧
y todo lo siguiente(⍺{⌈/⍴¨⍺⍵}⍵)⍴¨⍺[⍋⍺]⍵[⍋⍵]
clasifica ambas entradas y dales forma para que sean tan largas como las más largas (se ajustan si las haces más largas de lo que son)|¨∊-/{⎕av⍳⍵}
convierta ambos vectores de caracteres en vectores int de sus valores ascii, reste un vector y obtenga todos los valores absolutos0=+/2≤
resumir valores mayores o iguales a dos y verificar si el resultado es igual a 0fuente
K (oK) , 27 bytes
Solución:
Pruébalo en línea!
Ejemplos:
Explicación:
Primero ordene cada cadena, luego rellene para que tenga la misma longitud, luego tome una de la otra (valores ASCII de caracteres), resultado cuadrado ya que no hay incorporado
abs
, tome la diferencia máxima y verifique si eso es menor que 2.fuente
J, 27 bytes
sin golf
explicado
&(3&u:@/:~)
ordena ambos argumentos y los convierte a números ascii,:
crea una matriz de 2 xn, donde n es el número de caracteres de los argumentos-/
resta una fila de la otra, dando una lista de longitud n que representa la distancia de los caracteres correspondientes(2>|)
devuelve 1 si el valor absoluto de la distancia es menor que 2, de lo contrario 0*/
multiplica todos esos0
sys1
juntos: por lo tanto, el resultado final es 1 si todos los pares de caracteres correspondientes son adyacentes.Pruébalo en línea!
fuente