Este Code Golf se inspiró en el reciente artículo del Daily WTF ¡ No puedes manejar lo verdadero! , que presenta una comparación de cadenas escrita como:
String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())
Imagine el problema que le habría causado al equipo de Steve si el String.hashCode
método de Java se implementara de una manera tal "YES".hashCode() == "NO".hashCode()
. Entonces, el desafío que propongo aquí es:
Escriba, en la menor cantidad de caracteres posible, una función hash (la llamaré
h
) con un parámetro de cadena y un valor de retorno entero, tal queh("YES")
sea igual ah("NO")
.
Por supuesto, esto sería trivial con una función como def h(s): return 0
, que genera una colisión hash para cada cadena. Para hacer este desafío más interesante, debe cumplir con la siguiente regla adicional:
De los otros 18 277 cuerdas posibles que constan de tres o menos letras mayúsculas (ASCII
^[A-Z]{0,3}$
), tiene que haber no hay colisiones hash.
Aclaración (señalado por Heiko Oberdiek): la cadena de entrada puede contener caracteres que no sean A-Z
, y su código debe ser capaz de codificar cadenas arbitrarias. (Sin embargo, puede suponer que la entrada es una cadena de caracteres en lugar de un puntero nulo o un objeto de algún otro tipo de datos). Sin embargo, no importa cuál sea el valor de retorno para las cadenas que no coinciden ^[A-Z]{0,3}$
, siempre que Es un número entero.
Además, para ofuscar la intención de esta función:
Su código no debe incluir ninguna de las letras 'Y', 'E', 'S', 'N' u 'O' (en mayúsculas o minúsculas) dentro de caracteres o literales de cadena.
Por supuesto, esta restricción no se aplica a las palabras reservadas, por lo que else
, return
, etc están muy bien.
YESNO
para verificar esta excepción específica.Respuestas:
GolfScript: 19 caracteres (24 caracteres para funciones con nombre)
Este es el cuerpo de la función. Asignarlo a una función con nombre
h
requiere cinco caracteres más:(Se puede omitir el punto y coma final, si no le importa dejar una copia del código en la pila).
El núcleo de la función hash es
26base
, que calcula la suma (26 n - k · a k ; k = 1 .. n ), donde n es el número de caracteres en la entrada y a k denota el código ASCII de la k -ésima Carácter de entrada. Para entradas que consisten en letras mayúsculas ASCII, esta es una función hash sin colisiones. El resto del código compara el resultado con 2107 (el código hash deNO
) y, si son iguales, agrega 59934 para obtener 2701 + 59934 = 62041, el código hash deYES
.Por ejemplo, salida, vea esta demostración en línea con casos de prueba.
fuente
h('DXP') == h('KK') == 65884
.lambda w:sum(ord(c)*26**i for i,c in enumerate(reversed(w*9)))%102983
)Python 2.x de 32 bits (19)
RSA usa un módulo de semiprime, y eso lo hace seguro, por lo que usar uno con mi algoritmo hash seguramente lo hará aún mejor. 1
Esta es una función matemática pura, funciona para todas las cadenas (demonios, funciona para cualquier objeto Python hashable), ¡y no contiene ningún tipo de condición o carcasa especial! Python de 32 bits normalmente se puede llamar como
python-32
en la mayoría de los sistemas que tienen ambos instalados 2 .He probado esto y devuelve 18,278 valores diferentes para las 18,279 cadenas mayúsculas de 3 letras o menos. Asignar esto a una función requiere 11 bytes más:
y
h('YES') == h('NO') == 188338253
.Python 2.x de 64 bits (19)
El mismo trato que el anterior.
Para llegar a estos números, se utilizó un poco de matemática modular. Estaba buscando una función
f
y un módulon
tal quehash(f('YES')) % n == hash(f('NO')) % n
. Esto es equivalente a una prueba quen
divided = hash(f('YES')) - hash(f('NO'))
, es decir, solo tenemos que verificar los factores ded
valores adecuados den
.Lo ideal
n
es cerca de 20000 ** 2 para reducir la posibilidad de una colisión de paradoja de cumpleaños. Encontrar un adecuadon
resulta ser un poco de prueba y error, jugar con todos los factores ded
(generalmente no hay muchos) y diferentes opciones para la funciónf
. Tenga en cuenta que la prueba y el error solo son necesarios porque quería hacer lon
más pequeño posible (para jugar al golf). Si eso no fuera un requisito, podría elegird
como mi módulo, que generalmente es lo suficientemente grande.Tenga en cuenta también que no puede realizar este truco usando solo
f(s) = s
(la función de identidad) porque el carácter más a la derecha de la cadena tiene esencialmente una relación lineal (en realidad unaXOR
relación) con el hash final (los otros caracteres contribuyen de una manera mucho más no lineal) ) Por lo tanto, la repetición de la cadena garantiza que las diferencias entre las cadenas se amplifiquen para eliminar el efecto de cambiar solo el carácter más a la derecha.1 Esto es una tontería patente.
2 El hash de cadenas de Python depende de la versión principal (2 frente a 3) y el bitness (32 bits frente a 64 bits). No depende de la plataforma AFAIK.
fuente
hash('YES'*9)
tiene34876679
como factor, mientras quehash('NO'*9)
tiene34876679+537105043
como factor. Pero, ¿cómo sabías que537105043
era un buen módulo? es decir, no hizo otras colisiones?Perl,
534940 bytesPrueba:
Los valores hash para
YES
yNO
son los mismos y hay 18279 cadenas^[A-Z]{0,3}$
, que están libres de colisión, excepto la única colisión paraYES
yNO
.Sin golf:
Versión anterior, 49 bytes.
Como el nuevo algoritmo es ligeramente diferente, mantengo la versión anterior.
Prueba:
Sin golf:
Ediciones:
"\0"
como byte de relleno ahorra 4 bytes en comparación con$"
.fuente
5457241
y de dónde20047
vienes? ¿Cómo se calculan estos números? Gracias por adelantado.YES
en hexadecimal es594553
. 0x594553 = 5850451.NO
en hexadecimal es4e4f
. 0x4e4f = 20047.Python: 63
Una solución increíblemente pobre:
Funciona interpretando cadenas alfanuméricas como números de base 36 y devolviendo 0 para todo lo demás. Hay un caso especial explícito para verificar un valor de retorno de 852 (NO), y devolver 44596 (YES) en su lugar.
fuente
try:
y toda la tercera línea. También puede guardar algunas picaduras al tener todas las líneas lógicas en la misma línea real, separadas por punto y coma (def h(s):r=int(s,36);return(r,44596)[r==852]
)Pure Bash, 29 bytes (cuerpo de la función)
Esto simplemente trata la cadena de entrada como un número base 36 y la convierte a decimal, luego trata el
NO
caso especial .Salida:
fuente
Ruby, 51 bytes
código de prueba:
salida:
fuente
Javascript ( ES6 ) 54 bytes
fuente
Java -
9477Desenrollado:
Narrativa - para
f(s) = BigInteger(s.getBytes())
:f("YES") xor f("NO") = 5835548
f("YES") xor 5835548 = f("NO")
f("YES") - (f("YES") xor 5835548) = f("NO") - (f("NO") xor 5835548)
tengo razón?fuente
CJam, 15 bytes
Funciona como la solución de GolfScript a continuación. Pruébalo en línea.
GolfScript, 17 bytes
Este enfoque se basa en las respuestas de nneonneo e Ilmari Karonen .
Cómo funciona
Elegir un algoritmo
Comenzamos con
{b base}:h
, es decir, la cadena de entrada se considera un número base-b. Mientrasb > 25
,h
es inyectiva.Obtenemos una colisión para las cadenas "SÍ" y "NO" si modificamos
h
de la siguiente manera:,{x base n}:h
donden
es un divisor de"YES" h "NO" h -
.Desafortunadamente, esto significa que también tendremos una colisión por, por ejemplo,
YET
yNP
. Para evitar esto, tenemos que modificar el número de base-b de una manera no lineal antes de tomar el módulo.La forma más corta de lograr esto en GolfScript es multiplicar el número base-b consigo mismo (es decir, cuadrarlo).
h
es ahora{base b .* n %}:h
.Todo lo que queda por hacer es encontrar valores adecuados para
b
yn
. Podemos lograr esto por la fuerza bruta:Los valores más cortos posibles para
b n
son:Pruebas
fuente
JavaScript (ES6) - 38 caracteres (33 cuerpo de función char)
Casos de prueba:
Explicación:
Antes que nada, permíteme presentarte
NaN
- "No es un número" - en JavaScript. Es un numero:Al igual que:
Su propiedad especial es que nunca se iguala a sí mismo . Mi función devuelve
1
si la cadena esYES
oNO
, yNaN
para cualquier otra cadena.Por lo tanto, esto no rompe las reglas, porque no habría colisión de hash para ninguna otra cadena;) (se
NaN !== NaN
muestra arriba en casos de prueba).Y mi sueño se hace realidad: ¡derrotar a Bash, Perl y Ruby en la longitud del código!
Código sin golf:
Si ese valor es
"WUVT"
o"Tk8="
, regrese1
. De lo contrario, regresecual seria
NaN
.fuente
^\d+$
. Y JS trataNaN
como un número. Puedes multiplicarlo por un número, sumar, dividir, restar como con los números. Es una propiedad especial de JavaScript. No hay daño en usarlo. Eso es lo que llamamos flexión de reglas ;)Object.is()
y afirmar que sigue siendo una colisión ...==
) para la comparación, lo que garantizará que no ocurra una colisión hash para ninguna cadena aparte de "SÍ" o "NO".NaN
que no cuenta como colisión parece barato, esta solución tiene colisiones con cuerdasNA
a travésNP
yYEQ
por medioYET
Python 92
La función hash concatena los valores ordinales de los caracteres ASCII, la declaración de impresión asegura que las dos entradas deseadas colisionen.
fuente
ECMAScript 6 (30 bytes)
Intenté evitar la asignación de variables, el retorno y la palabra clave de función, y esta parece ser una excelente manera de evitar todas esas tonterías (también se parece a la programación funcional, en cierto modo). A diferencia de otras soluciones, no depende de
btoa
oatob
, que no es ECMAScript 6, sino HTML5.0+
es necesario, por lo que podría analizar cadenas arbitrarias.fuente
a=>parseInt(0+a,36)-852||43744
Java - 45 (¿o 62?)
No tengo idea de cómo calificar de manera justa dado lo que uno necesita para ejecutar un programa en Java, ¿debo incluir la definición de la función? Siéntase libre de editar y ajustar mi puntaje adecuadamente. Actualmente estoy anotando de la misma manera que la respuesta @OldCurmudgeon. Agregue 17 para
int h(String t){}
si es necesario:Sin golfista con arnés de prueba:
fuente
Y el más flojo es ...
Transportador, 145 caracteres
Básicamente este programa hace algún tipo de base 26 en los caracteres. Después de eso, comprueba si el hash es igual a 12999 (El código hash de YES) y si es así imprime 404 (el código hash de NO), de lo contrario, solo imprimirá el código hash.
Conveyor es un lenguaje creado por mí que actualmente se encuentra en etapas beta, pero puede encontrar un intérprete junto con algunos ejemplos y código fuente aquí: https://github.com/loovjo/Conveyor
fuente
C # 4.5 (112 bytes)
Versión de trabajo (?) Del intento del monorraíl subterráneo, en C #. Concatena los bytes de la cadena en un entero de 32 bits (solo funciona con hasta 4 caracteres), luego OR el resultado contra el resultado de "SÍ" y "NO" respectivamente, luego OR juntos.
Si bien puede colisionar en algún momento, no debería suceder para ningún ^ [AZ] {2,3} $ que no sea "SÍ" y "NO".
fuente
Sin comentarios - 31 (contenido de la función: 26)
Solución bastante simple. ;) Funciona para todas y cada una de las cadenas UTF-8.
EXPLICACIÓN:
'
es, obviamente, la función. Primero, verifica si*
(es entrada) es igual a|,,|+|"#|
(|NO|
). Si es así, devuelve|, |+|-%3|
(|YES|
); de lo contrario, solo devuelve*
.fuente
C 54
Convierta la cadena a entero - "NO" y multiplíquelo por el mismo valor + "NO" - "SÍ" para obtener 0 para "NO" y "SÍ" y distinto de cero para cualquier otra cadena en el rango especificado.
Todos los valores en la máquina con Windows 7 si hay alguna preocupación endian.
fuente
Stax ,
1211 bytesEjecutar y depurarlo
Traduce la entrada como base-36, resta 852, luego reemplaza 0 con 43744. Es un puerto de la excelente solución de Konrad .
fuente
CoffeeScript - 36
Debería regresar
1
paraYES
yNO
, y cualquier tontería confusa queatob
produzca para todo lo demás que no sea una cadena base64.El equivalente de JavaScript ( no el código JS del compilador CS):
fuente
_
cuando la entrada no es "SÍ" o "NO".Aquí hay uno súper cojo. TAN LO QUE NO FUNCIONA INCLUSO
Python 2.7 - 79 bytesPrimero obtenemos la suma de (valor ascii de cada personaje) * 100 ^ (la posición de ese personaje en la cadena). Luego multiplicamos (ese resultado - 7978) y (ese resultado - 836989) para obtener nuestra respuesta final. 7978 y 836989 son los resultados para "SÍ" y "NO" del primer bit, por lo que para SÍ y NO estamos multiplicando por 0.
Esto no debería tener ninguna colisión? No tengo ganas de probar contra 18000 posibles contraejemplos, pero si hubo una colisión involuntaria, puedo lanzar otro 0 sobre eso
100
y realmente no debería haber ninguna colisión.Decepcionado porque no podía usar un
lambda
para esto, pero no quería hacer el cálculo completo dos veces, así que tuve que guardarlo en una variable.Por favor, no dejes que esto gane. Es súper cojo y no lo merezco.
fuente