Dos palabras son isomorfos si tienen el mismo patrón de repeticiones de letras. Por ejemplo, ambos ESTATE
y DUELED
tienen patrónabcdca
ESTATE
DUELED
abcdca
Como las letras 1 y 6 son iguales, las letras 3 y 5 son iguales y nada más. Esto también significa que las palabras están relacionadas por un cifrado de sustitución, aquí con la coincidencia E <-> D, S <-> U, T <-> E, A <-> L
.
Escriba código que tome dos palabras y verifique si son isomorfos. Pocos bytes ganan.
Entrada: Dos cadenas de letras mayúsculas no vacías A..Z
. Si lo desea, puede tomarlos como una colección de dos cadenas o como una sola cadena con un separador.
Salida: Un valor de Verdad consistente para pares que son isomorfos, y un valor de Falsey consistente si no lo son. Las cadenas de diferentes longitudes son entradas válidas que nunca son isomorfos.
Casos de prueba:
Cierto:
ESTATE DUELED
DUELED ESTATE
XXX YYY
CBAABC DEFFED
RAMBUNCTIOUSLY THERMODYNAMICS
DISCRIMINATIVE SIMPLIFICATION
Falso:
SEE SAW
ANTS PANTS
BANANA SERENE
BANANA SENSES
AB CC
XXY XYY
ABCBACCBA ABCBACCAB
ABAB CD
Siéntase libre de agregar más casos de prueba que considere útiles.
Tabla de clasificación
Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.
Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:
# Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
ABAB CD
(para enfoques tipo zip)Respuestas:
J, 4 bytes
Uso
Explicación
=
con 1 argumento crea una tabla de igualdad que compara los elementos de la entrada y su protuberancia.-:
con 2 argumentos verifica su igualdad (como==
generalmente lo hace). Esto también funciona para matrices de diferentes tamaños (o incluso para diferentes tipos).f&g
aplica g tanto de entrada por separado y luego se aplica f a los dos resultados juntos asíx f&g y == f(g(x), g(y))
.Entonces, en nuestro caso, comparamos las dos tablas de igualdad.
Pruébelo en línea aquí.
fuente
&
, lo más cercano que podrías hacer en K probablemente sería~/{x=/:x}'
, que es un poco más largo.=
tuviera otro uso que no sea para contar sucesos.K, 5 bytes
¡Esto tiene una solución deliciosamente elegante en K!
El operador "grupo" (monádico
=
) crea precisamente la firma que queremos para la palabra isomorfismo; reuniendo vectores de los índices de cada elemento de un vector, con los grupos ordenados por apariencia:Tomando un par de cadenas como vector, solo necesitamos aplicar el grupo a cada elemento (
=:'
) y luego reducir con "match" (~
), el operador de igualdad profunda:fuente
Python 2, 41 bytes
fuente
CJam, 9 bytes
Imprime
1
si las palabras son isomorfos y0
si no lo son.Pruébelo en línea en el intérprete de CJam .
Cómo funciona
fuente
JavaScript, ES7,
62 55 54 5251 bytesLa lógica es simple. Simplemente convierto ambas entradas en sus valores de índice de caracteres correspondientes, convierto esa matriz en una cadena y la comparo.
Pruebe el código anterior usando el fragmento a continuación.
Mostrar fragmento de código
2 bytes guardados gracias a @ edc65
fuente
+0
en lugar de+""
?Bash + coreutils, 38
Tenga en cuenta que estamos usando la idea habitual de la verdad / falsedad aquí: cero significa ÉXITO o VERDADERO y no cero significa error o FALSO:
fuente
Haskell,
3329EDITAR:
Esto es demasiado tarde, pero encontré esta mejora con los solicitantes, que se agregaron al preludio solo en marzo de 2015.
Versión antigua:
la función de verificación es
(%)
esto funciona generando para cada cadena su "registro de igualdad": para cada dos índices ij, registra si tienen caracteres iguales. el registro está ordenado de modo que el registro para dos índices i, j siempre esté en el mismo lugar * y, por lo tanto, verificar la igualdad de los registros devolvería si las cadenas tienen o no el mismo patrón.
por ejemplo, el registro de igualdad de "ABC" es
[1,0,0,0,1,0,0,0,1]
(1 para verdadero, 0 para falso): allí esTrue
donde se compara cualquier índice consigo mismo. cualquier otro lugar es falso. (omitir estos controles puede ser más eficiente, pero es más difícil en términos de golf)* si las cadenas son de la misma longitud. de lo contrario, devuelve falso solo porque los registros son de diferentes longitudes
fuente
Haskell,
4541 bytesDevoluciones
True
oFalse
, por ejemplo,"ESTATE" ! "DUELED"
->True
.Utiliza el método map-char-to-first-index como se ve en muchas otras respuestas. Las listas de asociaciones son útiles, porque las entradas anteriores triunfan.
"aba"
se convierte[(a,1),(b,2),(a,3)]
dondelookup
siempre buscaa
->1
.Editar: @Mauris encontró 4 bytes para guardar.
fuente
(flip lookup$zip l[1..])
por(`lookup`zip l[1..])
.Brainfuck,
169168162144140131130Compatible con bff de Alex Pankratov (intérprete de brainfuck usado en SPOJ e ideone) y BFI de Thomas Cort (usado en Anarchy Golf).
La entrada esperada es dos cadenas separadas por una pestaña, sin nueva línea después de la segunda cadena. La salida es
1
para isomorfos y0
para no isomorfos, lo cual es conveniente para verificar los resultados visualmente, aunque no es la opción más corta. ( Actualización: versión más corta con\x01
y\x00
como salida y\x00
como separador en la parte inferior de la respuesta).Demostración sobre ideona.
Este problema resulta ser muy bueno para el brainfuck.
La idea básica con la indexación es ir hacia atrás desde el final del prefijo de cadena actual. Si el carácter no se ha producido anteriormente, podemos tomar la longitud del prefijo de la cadena. Por ejemplo:
La indexación en el código es en realidad un poco diferente, pero utiliza el mismo principio.
El diseño de la memoria está en bloques de 5:
c
significa carácter,i
índice yp
anterior (índice). Cuando se procesa la primera cadena, todas lasp
ranuras son cero. La celda a la izquierda dec
se usa para contener una copia del carácter actual del que estamos tratando de encontrar el índice. La celda a la izquierda de la corrientei
se usa para mantener un-1
para una fácil navegación del puntero.Hay muchas condiciones que deben considerarse cuidadosamente. Al final, verificamos si hay isomorfos comparando los
(i,p)
pares, y llegamos al grupo de celdas cero a la izquierda del(i,p)
par más a la izquierda si y solo si las cadenas son isomorfos. Aquí hay una versión comentada del código para que sea más fácil de seguir:Actualizar:
Aquí hay una versión que imprime
\x01
para isomorfos y\x00
para no isomorfos. Esto podría decirse que es una interpretación más precisa de Truthy y Falsey para el cerebro, debido a la forma[
y el]
trabajo. La única diferencia está al final.Adicional: ahora se usa
\x00
como separador para guardar 10 bytes.fuente
JavaScript (ES6), 62
Usando una función auxiliar
h
que asigna cada palabra a una matriz que contiene la posición de cada letra en la palabra, por ejemplo: PASS -> [1,2,3,3]. Devuelve verdadero si la funciónh
aplica las dos palabras da el mismo resultado.fuente
R, 78
De-golf:
fuente
all( (g=...)(x)==g(y))
es más corto queidentical
...Ruby, 83 bytes
Es una función
f
que toma dos argumentos y devuelvetrue
ofalse
.Explicación:
fuente
t=->x{z=?`;x.chars.to_a.uniq.map{|c|x.gsub!(c,z.succ!)};x};f=->a,b{t[a]==t[b]}
y podríat=->x{h={};i=9;x.gsub!(/./){|c|h[c]||h[c]=i+=1}};f=->a,b{t[a]==t[b]}
Java, 107
Mapea cada personaje de
s
yt
a su ubicación, y verifica la igualdad.Expandido:
fuente
Python 3, 85 bytes
fuente
g
es la función principal,f
es auxiliar. Hay una elección confusa de variableg
dentrof
, pero es una variable ligada no relacionada.g=
Es opcional según la decisión que permite funciones anon, lo que ahorra dos caracteres.Pyth, 9 bytes
Toma entrada de la siguiente forma:
Si eso no es aceptable, el siguiente código es de 10 bytes:
y usa este formulario de entrada:
Utiliza el índice de char en la representación de cadena.
fuente
F
funciona el pliegue. ¿Qué es<binary>F
?<binary>F<seq>
está<binary>
doblado<seq>
. Es equivalente a intercalar<binary>
entre cada par de elementos de<seq>
. Por lo tanto,<binary>F
en una secuencia de 2 elementos simplemente aplica la función a la secuencia, equivalente a.*
Pyth o*
Python.Q
estaba implícito en Pyth?Matlab, 50 bytes
La función se define como anónima para ahorrar espacio.
Ejemplo:
fuente
Octava, 26 bytes
fuente
==
es la matriz igualdad elemento a elemento, y desdes
ys'
son de diferentes tamaños, "radiodifusión" de Octave automáticamente intenta obtener matrices del mismo tamaño para operar en - que en este caso significa la repetición de la filas
y la columnas'
05AB1E , 6 bytes
Pruébalo en línea!
Toma la entrada como una lista:
['ESTATE', 'DUELED']
Explicaciones:
fuente
APL (Dyalog) ,
54 bytes-1 gracias a la pista de ngn.
Función de prefijo tácito anónimo que toma una lista de dos cadenas como argumento.
Pruébalo en línea!
Este es un producto interno, pero en lugar de lo habitual
+
y×
utiliza≡
similitud.
y⍳
el ɩ ndex (la primera aparición de cada elemento)⍨
con la lista completa de dos elementos de palabras usadas como ambos argumentosSi llamamos a las palabras
A
yB
, entonces podemos derivar la solución anterior de la siguiente manera:≡.⍳⍨ A B
A B ≡.⍳ A B
(A⍳A) ≡ (B⍳B)
(⍳⍨A) ≡ (⍳⍨B)
≡/ ⍳⍨¨ A B
Solución previa
Función de prefijo tácito anónimo que toma una lista de dos cadenas como argumento.
Pruébalo en línea!
≡
similitud/
a través de⍳
el ɩ ndex (la primera aparición de cada elemento ...)⍨
selfie (... en sí mismo)¨
de cadafuente
Mathematica, 46 bytes
fuente
Ruby, 50 bytes.
Código ruby 30 bytes más corto. Escrito antes de echar un vistazo a las soluciones, verifica para cada carácter de ambas cadenas si el índice de la primera aparición de ese carácter coincide; es decir. transforma una cadena a su forma normalizada,
01121
etc. y las compara.Casos de prueba en ideone Como una ventaja adicional, esto rompe el resaltado del código de ideone.
fuente
Casco , 5 bytes
Pruébalo en línea!
Explicación
fuente
PCRE, 84 bytes
El asunto debe ser dos palabras separadas por espacios, como en el OP. Aquí hay una explicación superficial:
fuente
Ruby, 31 bytes
Un proceso que toma una serie de cadenas y comprueba si alguno es isomorfo entre sí.
tr s,'a-z'
con estos argumentos se normaliza una cadenas
al reemplazar cada letra con la enésima letra del alfabeto, donden
es el índice más grande con el que aparece esa letra en la cadena. Por ejemplo, seestate
conviertefbedef
, como lo hacedueled
.fuente
Cobra, 72 bytes
fuente
AB CC
caso de prueba Falso?JavaScript (ES5),
14298Muy grande, pero todavía no vi una versión ES5.
for(l=j=2;j--;){c=prompt();for(i=c.length;i--;)c=c.replace(RegExp(c[i],"g"),i);b=l==c;l=c}alert(b)
Simplemente reemplaza cada aparición de la primera letra con su valor de índice inverso. Repite esto para cada personaje.
Hace lo mismo para ambas entradas y compara el patrón generado.
La comparación es bastante fea, pero no quiero usar una matriz para almacenarla y compararla.
fuente
;l=c
afor(l=j=2;j--;
y guardar un byte?Perl, 38 bytes
Correr como
perl -E '($_,$a)=@ARGV;eval"y/$_/$a/";say$_~~$a' RAMBUNCTIOUSLY THERMODYNAMICS
Imprime 1 si es verdadero, nada si es falso.
fuente
Lisp común, 76 bytes
Pruébalo en línea!
fuente
C ++,
213196162 bytes-51 bytes gracias a Zacharý
Para llamar a lambda, debe pasar 2 argumentos que son
std::string
de tipo de datosCódigo para probar:
para el código que pone a prueba, incluyendo
iostream
ystring
se requiere un archivo de cabecerafuente
e
argumento defind
, sí, funcionaJavaScript (ES6),
525150 bytesEsta versión no utiliza la comprensión de la matriz y toma datos utilizando la sintaxis de curry.
Mostrar fragmento de código
fuente