En este desafío de código , escribirá una función hash en 140 bytes 1 o menos del código fuente. La función hash debe tomar una cadena ASCII como entrada y devolver un entero sin signo de 24 bits ([0, 2 24 -1]) como salida.
Su función hash será evaluada para cada palabra en este gran diccionario de inglés británico 2 . Su puntaje es la cantidad de palabras que comparten un valor hash con otra palabra (una colisión).
El puntaje más bajo gana, lazos rotos por el primer cartel.
Caso de prueba
Antes de enviar, pruebe su secuencia de comandos de puntuación en la siguiente entrada:
duplicate
duplicate
duplicate
duplicate
Si le da un puntaje que no sea 4, tiene errores.
Reglas aclaratorias:
- Su función hash debe ejecutarse en una sola cadena, no en una matriz completa. Además, su función hash no puede hacer ninguna otra E / S que la cadena de entrada y el entero de salida.
- Las funciones hash incorporadas o una funcionalidad similar (por ejemplo, cifrado para codificar bytes) no está permitido.
- Su función hash debe ser determinista.
- Contrariamente a la mayoría de los otros concursos, se permite la optimización específica para la entrada de puntuación.
1 Sé que Twitter limita los caracteres en lugar de los bytes, pero por simplicidad usaremos bytes como límite para este desafío.
2 Modificado de wbritish-huge de Debian , eliminando cualquier palabra que no sea ASCII.
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's
? Que...?D=340275
palabras yR=2^24
salidas hash, un hash aleatorio tieneD^2/(2*R) = 3450
pares de colisión esperados , algunos de los cuales se superponen. Hay unD^3/(6*R^2) = 23
triple de colisión esperado y un número insignificante de colisiones más grandes, lo que significa que estos triples son probablemente disjuntos. Esto da unas6829
palabras esperadas que comparten un valor hash, ~70
en triples y el resto en pares. La desviación estándar se estima en118
, por lo que obtener<6200
un hash aleatorio es aproximadamente un evento de 5 sigma.Respuestas:
Muy bien, iré a aprender un idioma de golf.
CJam, 140 bytes, 3314 palabras en colisión
Define un bloque (función anónima). Para probar, puede agregar
qN%%N*N
para tomar la lista de palabras separadas por nueva línea en stdin y escribir una lista de hashes separados por nueva línea en stdout. Código de Python equivalente:Pyth, 140 bytes,
35353396 palabras en colisiónDefine una función llamada
y
. Para probar, puede agregarjmyd.z
para tomar la lista de palabras separadas por nueva línea en stdin y escribir una lista de hashes separados por nueva línea en stdout. Código de Python equivalente:Límites teóricos
¿Qué tan bien podemos esperar hacer? Aquí hay una gráfica de x, el número de palabras en colisión, frente a y, la entropía en bytes requerida para obtener como máximo x palabras en colisión. Por ejemplo, el punto (2835, 140) nos dice que una función aleatoria obtiene como máximo 2835 palabras en colisión con probabilidad 1/256 ** 140, por lo que es extremadamente improbable que alguna vez podamos hacerlo mucho mejor que eso con 140 bytes de código
fuente
Python,
53334991Creo que este es el primer contendiente en obtener una puntuación significativamente mejor que un oráculo aleatorio.
fuente
def H(s):n=int(s.encode('hex'),16);return n%...
ahorra 5 bytes, en caso de que pueda usarlos de alguna manera ...2**24 == 8**8
.Python 2, 140 bytes, 4266 palabras en colisión
Realmente no quería comenzar con la cuestión de los bytes no imprimibles debido a su capacidad de ajuste clara, pero bueno, no lo comencé. :-PAGS
Python 2, 140 bytes imprimibles,
466244714362 palabras en colisiónInspirado por la forma de la solución de kasperd, obviamente, pero con la importante adición de una transformación afín en el espacio del módulo y parámetros completamente diferentes.
fuente
n%(8**8-ord('…'[n%70]))
sin otros cambios de parámetros, solo logré llegar a 4995, por lo que parece que su nuevo optimizador ha alcanzado el mío. ¡Ahora esto se pone más interesante!CJam,
4125393737913677Este enfoque divide el dominio y el codominio en 110 conjuntos disjuntos, y define una función hash ligeramente diferente para cada par.
Puntuación / Verificación
El siguiente puerto a Python se puede usar con el fragmento de puntuación oficial:
fuente
h
En ese puerto de Python corresponde a un CJam incorporado?b
(conversión de base).Python,
64466372Esta solución logra un recuento de colisiones más bajo que todas las entradas anteriores, y solo necesita 44 de los 140 bytes permitidos para el código:
fuente
%(2**24-1)
, así que creo que sería bueno pedir una aclaración[0, 2**24-1]
que palabras en inglés, sería matemáticamente imposible hacer un hash donde todos los valores de ese rango fueran posibles.CJam, 6273
XOR cada carácter con 49 , reduzca la cadena resultante a través de x, y ↦ 245x + y , y tome el módulo de residuo 16,777,213 (el primo más grande de 24 bits).
Puntuación
fuente
JavaScript (ES6), 6389
La función hash (105 bytes):
La función de puntuación (NodeJS) (170 bytes):
Llamar como
node hash.js dictionary.txt
, dondehash.js
está el script,dictionary.txt
es el archivo de texto del diccionario (sin la nueva línea final), yF
se define como la función de hashing.¡Gracias Neil por eliminar 9 bytes de la función hash!
fuente
((...)>>>0)%(1<<24)
usted, probablemente pueda usar(...)<<8>>>8
.i
.Mathematica, 6473
El siguiente paso ... en lugar de sumar los códigos de caracteres, los tratamos como los dígitos de un número base-151, antes de tomarlos módulo 2 24 .
Aquí hay un breve guión para determinar la cantidad de colisiones:
Acabo de probar todas las bases sistemáticamente desde ahora
1
, y hasta ahora la base 151 produjo la menor cantidad de colisiones. Intentaré un poco más para bajar un poco más el puntaje, pero la prueba es un poco lenta.fuente
Javascript (ES5), 6765
Esto es CRC24 reducido a 140 Bytes. Podría jugar más golf pero quería obtener mi respuesta :)
Validator en node.js:
fuente
Python, 340053
Una puntuación terrible de un algoritmo terrible, esta respuesta existe más para dar un pequeño script de Python que muestra la puntuación.
Para anotar:
fuente
Python,
639063766359Puede considerarse una modificación trivial a la respuesta de Martin Büttner .
fuente
[0, 2**24-1]
. Lo único que no está permitido es emitir cualquier número que no esté dentro de ese rango, por ejemplo,-1
o2**24
.Python, 9310
Sí, no el mejor, pero al menos es algo. Como decimos en criptografía, nunca escriba su propia función hash .
Esto es exactamente 140 bytes de largo, también.
fuente
Matlab,
3082886206848Construye el hash asignando un número primo a cada combo de carácter / posición ascii y calculando su producto para cada módulo de palabra, el primo más grande menor que 2 ^ 24. Tenga en cuenta que para las pruebas, moví la llamada a primos fuera del probador directamente antes del bucle while y la pasé a la función hash, porque la aceleró en aproximadamente un factor de 1000, pero esta versión funciona y es autónoma. Puede bloquearse con palabras de más de 40 caracteres.
Ensayador:
fuente
double
explícitamente. También podría usar ennumel
lugar delength
. ¡Sin embargo, no estoy seguro de qué haría con todos esos bytes adicionales!Ruby, 9309 colisiones, 107 bytes
No es un buen contendiente, pero quería explorar una idea diferente de otras entradas.
Asigne los primeros n primos a las primeras n posiciones de la cadena, luego sume todos los primos [i] ** (código ascii de la cadena [i]), luego mod 2 ** 24-1.
fuente
Java 8,
70546467Esto está inspirado (pero no copiado) de la función incorporada java.lang.String.hashCode, así que siéntase libre de rechazar de acuerdo con la regla # 2.
Para anotar:
fuente
hashes
conMap<Integer, Integer> hashes = new HashMap<>()
y luego cuenta el número de palabras para cada hash, puede explicarlas correctamente.Python,
699568626732Solo una simple función RSA. Bastante cojo, pero supera algunas respuestas.
fuente
C ++:
711266946483647964126339 colisiones, 90 bytesImplementé un algoritmo genético ingenuo para mi matriz de coeficientes. Actualizaré este código a medida que encuentre mejores. :)
Función de prueba:
fuente
C #, 6251
6335Las constantes 533 y 733
889 y 155dan la mejor puntuación de todas las que he buscado hasta ahora.fuente
tcl
88 bytes, 6448/3233 colisiones
Veo que la gente ha estado contando el número de palabras que colisionan o el número de palabras colocadas en cubos no vacíos. Doy ambos recuentos: el primero está de acuerdo con la especificación del problema, y el segundo es lo que más pósters han estado informando.
fuente
proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}
... ¿verdad?Python 3, 89 bytes, 6534 colisiones hash
Todos los grandes números mágicos que ves aquí son constantes falsas.
fuente
JavaScript, 121 bytes,
3268325032446354 (3185) colisionesLos parámetros (13, 7809064, 380886, 2, 266324) son por prueba y error.
Todavía optimizable, creo, y todavía hay espacio para agregar parámetros adicionales, trabajando para una mayor optimización ...
Verificación
3268> 3250: se modificó el tercer parámetro de 380713 a 380560.
3250> 3244: se modificó el tercer parámetro de 380560 a 380886.
3244> 6354 - Cambié el segundo parámetro de 7809143 a 7809064, y descubrí que he usado el método de cálculo incorrecto; P
fuente
Aquí hay algunas construcciones similares, que son bastante "visibles" y hacen posible la optimización de parámetros incrementales. ¡Maldición, es difícil bajar de 6k! Suponiendo que el puntaje tiene una media de 6829 y un estándar de 118, también calculé la probabilidad de obtener puntajes tan bajos al azar.
Clojure A, 6019, Pr = 1: 299.5e9
Clojure B, 6021, Pr = 1: 266.0e9
Clojure C, 6148, Pr = 1: 254.0e6
Clojure, 6431, Pr = 1: 2.69e3 (algo diferente)
Esta fue mi función hash ad-hoc original, tiene cuatro parámetros ajustables.
fuente
r
). Pero aún así, mi algoritmo de búsqueda es esencialmente fuerza bruta, y no estoy seguro de si la elección inicial del multiplicador der
es importante o no.f(n) % (8^8 - g(n))
.Ruby, 6473 colisiones, 129 bytes
La variable @p se llena con todos los números primos por debajo de 999.
Esto convierte los valores ascii en números primos y toma su módulo de producto como un primo grande. El factor de fudge de 179 trata con el hecho de que el algoritmo original era para usar en la búsqueda de anagramas, donde todas las palabras que son reordenamientos de las mismas letras obtienen el mismo hash. Al agregar el factor en el bucle, hace que los anagramas tengan códigos distintos.
Podría eliminar ** 0.5 (prueba sqrt para prime) a expensas de un peor rendimiento para acortar el código. Incluso podría hacer que el buscador de números primos se ejecute en el bucle para eliminar nueve caracteres más, dejando 115 bytes.
Para probar, lo siguiente intenta encontrar el mejor valor para el factor de fudge en el rango de 1 a 300. Se supone que el archivo de palabras está en el directorio / tmp:
fuente
tcl
# 91 bytes, 6508 colisiones91 bytes, 6502 colisiones
La computadora todavía está realizando una búsqueda para evaluar si hay un valor que causa menos colisiones que la base
147875, que sigue siendo el registrador.fuente