Andersen parte de un juego de word ladder en el que se puede cambiar una letra, quitarla, añadirla o reordenar la palabra. Los caminos con anagramas son difíciles de ver, así que escribió un solucionador y, al tardar más de un segundo, se puso a optimizarlo. Aquí solo trata la parte de encontrar todos los anagramas de un diccionario; el solucionador completo queda para otro post.
La versión base usa como clave la palabra con las letras ordenadas y un HashMap<String, Vec<String>>. Con el diccionario Scrabble (178.690 entradas) tarda 31 ms, unos 173 ns por palabra. Después elimina las asignaciones de Vec: como hay unas 161.000 claves para 178.000 palabras, casi todas son únicas. Guarda los casos únicos directamente y encadena el resto con una lista enlazada sobre arrays de u32, usando el bit alto para distinguir ambos casos. Baja a 20 ms.
El siguiente paso sustituye el ordenado de cadenas por un vector de recuentos de letras, con 4 bits por letra empaquetados en un u128 (26 × 4 = 104 bits). Baja a 5,6 ms (31 ns por palabra). Cambiar el hash por defecto de Rust por FxHashMap, de rustc_hash, lo deja en 4,1 ms (23 ns por palabra).
Para pasar a 64 bits usa una numeración de Gödel: un primo por letra y, como identificador de cada palabra, el producto de sus primos. Con la asignación ingenua (a=2, b=3, c=5…) hay desbordamiento ya en la palabra 365, «ABORTIVENESSES». Andersen optimizó la asignación mirando las 3.157 palabras de 15 letras: E=2, I=3, S=17, N=19, T=29 y J=101, porque la palabra más larga con dos J solo tiene 12 letras. Un programa partía del orden por frecuencia y, ante cada palabra que desbordaba, cambiaba primos por otros menores. El resultado es una tabla que no desborda con ninguna palabra del diccionario Scrabble y da un identificador canónico sin colisiones. El texto se corta antes de mostrar los tiempos finales de esta versión.
Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.