Ayudame a reconocer a mi monstruo

35

Fondo

El juego de computadora NetHack data de 1987, antes de que el uso de gráficos en juegos de computadora se estableciera ampliamente. Hay muchos monstruos en el juego, y potencialmente muchos deben caber en la pantalla a la vez, por lo que los monstruos se dibujan de una manera muy mínima: un monstruo simplemente se dibuja como un personaje ASCII en la pantalla.

Además de que hay muchos monstruos, hay muchos tipos de monstruos. Puede ser importante saber cuál es cuál; tendrías que reaccionar de manera diferente al ver un gatito y ver un dragón. Como tal, la mayoría de ASCII se usa para representar monstruos; por ejemplo, un gatito es fy un dragón rojo es D. Esto significa que puede ser muy útil saber cómo se verá un monstruo dado, ya que te ayudará a reconocerlo si lo encuentras más adelante en el juego. (Tenga en cuenta que hay más tipos de monstruos que personajes ASCII, por lo que algunos de ellos comparten; un dragón rojo y un dragón azul son ambos D).

Tarea

Su programa debe tomar el nombre de un monstruo NetHack como entrada, y producir el personaje ASCII que lo representa dentro del juego como salida. El programa puede asumir que la entrada es de hecho el nombre de un monstruo de NetHack; puede, si desea bloquearse, producir resultados sin sentido, etc. si la entrada no es válida.

El siguiente fragmento de pila es un objeto JSON que proporciona la asignación completa de posibles entradas a sus salidas correspondientes:

Entonces, básicamente, la tarea aquí es "dado una clave en el diccionario representado por el objeto JSON anterior, devolver el valor correspondiente".

Tenga en cuenta que este desafío es, en cierto modo, una inversa ; en lugar de pasar de una entrada pequeña / vacía a una salida grande, pasará de una entrada grande a una salida pequeña. (Por lo tanto, hay mucha información redundante en la entrada, que puede ignorar o utilizar como desee). También es bastante similar al golf regex, excepto que a) se permite cualquier lenguaje (no solo regex), yb) hay más de dos salidas posibles. (Hemos tenido algunas tareas como esta antes, como estas dos , pero esta tarea es algo diferente porque el comportamiento de entrada / salida especificado tiene patrones más fuertes).

Aclaraciones

Puede usar cualquier formato de entrada y salida razonable (por ejemplo, puede producir la salida como un carácter, o como su código ASCII, o como una cadena de un carácter de longitud). Puede enviar una función en lugar de un programa completo, si lo prefiere.

Esto ya se menciona en las lagunas estándar, pero solo para reiterar: no puede almacenar la correspondencia entre la entrada y la salida en otro lugar que no sea el código fuente de su programa. Este desafío consiste básicamente en representar el comportamiento de entrada / salida en el menor espacio posible, por lo que no debe hacer cosas como descargar una lista de Internet, almacenar la correspondencia en un archivo externo, iniciar NetHack en modo de depuración y generar el monstruo en cuestión para ver cómo se ve, etc. (Además, no quiero tener que luchar contra los monstruos para probar tus presentaciones).

Condición de victoria

Este es el , por lo que la entrada ganadora será la entrada más corta, contada en bytes. ¡Buena suerte!

Peter Taylor
fuente
66
mail daemon> _ <
briantist
1
Sugerencia: tal vez también pueda organizar la lista de monstruos en orden de acuerdo con el símbolo ASCII que representan
Kritixi Lithos
2
Suspiro - ese fue un buen juego, esos eran los días ...
GreenAsJade
2
@GreenAsJade sigue siendo un buen juego. De hecho, se lanzó una nueva versión hace unos meses después de algunos años de inactividad
nmjcman101
1
¡ Ha aparecido un PUDINO MARRÓN salvaje !
Urna de pulpo mágico

Respuestas:

11

Jelly , 309 bytes en la codificación de Jelly

“Æ÷“¥s“ɲ“¡µ’;“ịƊ⁴çNṂ‘_\
OḌ;¢*5$%¥/µ“+⁷ż!¤ña¡jIȧƁfvḶg/Ọ=^ƝĠ0Ẇƭ³½N~=.Ɗ°ɗẇ⁵\ɦ*ɠPf⁾?ṾHḣ 2=⁹ƒ!©ƊĠṣƥ®Ƙ0Yƙ>!ȧtƊN0w,$ɠẎ46fẋ⁷(ṣẆm⁾ŻƓṫµsçwṣḂḲd0Ruṛ’ḃ21+\iµØW“&;:' ”;“¡3ȧ%⁾xƑ?{Ñṃ;Ċ70|#%ṭdṃḃ÷ƑĠẏþḢ÷ݳȦṖcẇọqƁe ʠ°oḲVḲ²ụċmvP[ỴẊẋ€kṢ ȯḂ;jɓỴẏeṾ⁴ḳḢ7Ẓ9ġƤṙb€xÇ4ɗ⁻>Ẉm!Ƈ)%Ḃẇ$ġ£7ȧ`ỵẈƘɗ¡Ṃ&|ƙƥ³ẏrṛbḋƙċ⁻ṁƲRṀẹṾ<ñ⁻Ṅ7j^ɓĊ’b58¤ị;0ị@
ḲÇ€t0”@;Ṫ

Pruébalo en línea!

Decidí que era hora de intentar mi propio desafío. El uso de Jelly (y su página de códigos de 8 bits) me da una ventaja del 12.5% ​​sobre los idiomas exclusivos de ASCII, y Jelly es conveniente para este desafío debido a que tiene operadores de conversión de base incorporados con nombres cortos, pero la mayoría de los ahorros se deben a un mejor algoritmo de compresión (este programa promedia menos de un byte por tipo de monstruo).

Algoritmo y explicación

Clasificación basada en palabras

Decidí que para obtener una buena puntuación, era necesario aprovechar más la estructura de la entrada que otras entradas. Una cosa que es muy notable es que muchos monstruos tienen nombres de la forma " especie adjetiva "; a y a son ambos tipos de dragón, y por lo tanto aparecen como . Algunos otros monstruos tienen nombres de la forma " trabajo de especies ", como el ; siendo un tipo de orco, esto aparece como . Los asuntos complicados son los no muertos; a es tanto un kobold como un zombie, y el último estado tiene prioridad en la denominación de monstruos de NetHack, por lo que nos gustaría clasificar esto como .red dragonblue dragonD orc shamanokobold zombieZ

Como tal, clasifiqué las palabras que aparecen en los nombres de los monstruos de la siguiente manera: un indicador es una palabra que sugiere fuertemente la clase de monstruo apropiada (por ejemplo sphere, sugiere fuertemente que el monstruo está en clase e); una palabra ambigua es una palabra que hace una sugerencia mucho menor ( lordno le dice mucho), y todas las demás palabras son palabras que no nos importan. La idea básica es que miremos las palabras en el nombre del monstruo desde el final hacia atrás hasta el comienzo, y seleccionamos el primer indicador que vemos. Como tal, era necesario asegurarse de que cada nombre de monstruo contuviera al menos un indicador, seguido completamente por palabras ambiguas. Como excepción, las palabras que aparecen en los nombres de monstruos que parecen un@(el grupo más grande) están clasificados como ambiguos. Cualquier cosa puede aparecer antes de un indicador; por ejemplo, los nombres de color (como red) siempre aparecen antes en un nombre que un indicador y, por lo tanto, se consideran no palabras (ya que nunca se examinan al determinar la identidad de un monstruo).

Al final, este programa se reduce a una tabla hash, como lo hacen los otros programas. Sin embargo, la tabla no contiene entradas para todos los nombres de monstruos, o para todas las palabras que aparecen en los nombres de monstruos; más bien, contiene solo los indicadores. Los hash de palabras ambiguas no aparecen en la tabla, pero deben asignarse a espacios vacíos (intentar buscar una palabra ambigua siempre aparecerá vacía). Para las no palabras, no importa si la palabra aparece en la tabla o no, o si el hash choca o no, porque nunca usamos el valor de buscar una no palabra. (La tabla es bastante escasa, por lo que la mayoría de las no palabras no aparecen en la tabla, pero algunas, como por ejemplo flesh, se encuentran en la tabla como consecuencia de colisiones hash).

Aquí hay algunos ejemplos de cómo funciona esta parte del programa:

  • woodchuckes una sola palabra larga (por lo tanto, un indicador), y la búsqueda en la tabla woodchucknos da la respuesta deseada r.
  • abbotTambién es una sola palabra larga, pero parece un @. Como tal, abbotse considera una palabra ambigua; la búsqueda en la tabla aparece vacía y devolvemos una respuesta de @forma predeterminada.
  • vampire lordconsiste en un indicador ( vampirecorrespondiente a V) y una palabra ambigua ( lordque no está en la tabla). Esto significa que verificamos ambas palabras (en orden inverso), luego damos la respuesta correcta de V.
  • gelatinous cubeconsiste en una no palabra ( gelatinouscorrespondiente a Hdebido a una colisión hash) y un indicador ( cubecorrespondiente a b). Como solo tomamos la última palabra que se encuentra en la tabla, esto regresa b, como se esperaba.
  • gnome mummyconsta de dos indicadores, gnomecorrespondientes Gy mummycorrespondientes a M. Tomamos el último indicador y obtenemos M, que es lo que queremos.

El código para manejar la clasificación basada en palabras es la última línea del programa Jelly. Así es como funciona:

ḲÇ€t0”@;Ṫ
Ḳ          Split on spaces
 ǀ        Call function 2 (table lookup) on each entry
   t0      Remove trailing zeroes (function 2 returns 0 to mean "not found")
     ”@;   Prepend an @ character
        Ṫ  Take the last result

Hay dos casos reales; si la entrada consiste completamente en palabras ambiguas, t0elimina la salida completa de las búsquedas de la tabla y obtenemos un @resultado por defecto; Si hay indicadores en la entrada, t0borrará cualquier cosa a la derecha del indicador más a la derecha, y nos dará el resultado correspondiente para ese indicador.

Tabla de compresión

Por supuesto, dividir la entrada en palabras no resuelve el problema por sí solo; Todavía tenemos que codificar la correspondencia entre los indicadores y las clases de monstruos correspondientes (y la falta de correspondencia de palabras ambiguas). Para hacer esto, construí una tabla dispersa con 181 entradas utilizadas (correspondientes a los 181 indicadores; ¡esto es una gran mejora sobre los 378 monstruos!), Y 966 entradas totales (correspondientes a los 966 valores de salida de la función hash). La tabla se codifica en el programa mediante el uso de dos cadenas: la primera cadena especifica los tamaños de los "espacios" en la tabla (que no contienen entradas); y la segunda cadena especifica la clase de monstruo que corresponde a cada entrada. Ambos están representados de manera concisa a través de la conversión de base.

En el programa Jelly, el código para la búsqueda de la tabla, junto con el programa en sí, se representa en la segunda línea, desde la primera en µadelante. Así es como funciona esta parte del programa:

“…’ḃ21+\iµØW“&;:' ”;“…’b58¤ị;0ị@
“…’                              Base 250 representation of the gap sizes
   ḃ21                           Convert to bijective base 21 
      +\                         Cumulative sum (converts gaps to indexes)
        i                        Find the input in this list
         µ                       Set as the new default for missing arguments

          ØW                     Uppercase + lowercase alphabets (+ junk we ignore)
            “&;:' ”;             Prepend "&;:' "
                    “…’          Base 250 representation of the table entries
                       b58       Convert to base 58
                          ¤      Parse the preceding two lines as a unit
                           i     Use the table to index into the alphabets
                            ;0   Append a zero
                              i@ Use {the value as of µ} to index into the table

La base biyectiva 21 es como la base 21, excepto que 21 es un dígito legal y 0 no lo es. Esta es una codificación más conveniente para nosotros porque contamos dos entradas adyacentes como que tienen un espacio de 1, para que podamos encontrar los índices válidos a través de la suma acumulativa. Cuando se trata de la parte de la tabla que contiene los valores, tenemos 58 valores únicos, por lo que primero decodificamos en 58 enteros consecutivos y luego decodificamos nuevamente usando una tabla de búsqueda que los asigna a los caracteres reales que se están utilizando. (La mayoría de estas son letras, por lo que comenzamos esta tabla de búsqueda secundaria con las entradas que no son letras &;:' , y luego agregamos una constante Jelly que comienza con los alfabetos en mayúsculas y minúsculas; también tiene otra basura pero no nos importa sobre eso.)

El valor centinela "índice no encontrado" de Jelly, si lo usa para indexar en una lista, devuelve el último elemento de la lista; por lo tanto, agregué un cero (un cero entero, aunque la tabla está hecha principalmente de caracteres) a la tabla de búsqueda para dar un centinela más apropiado para indicar una entrada faltante.

Función hash

La parte restante del programa es la función hash. Esto comienza simplemente, conOḌ; esto convierte la cadena de entrada en sus códigos ASCII y luego calcula el último código, más 10 veces el penúltimo código, más 100 veces el código anterior, y así sucesivamente (esto tiene una representación muy corta en Jelly porque se usa más comúnmente como un cadena → función de conversión de enteros). Sin embargo, si simplemente redujimos este hash directamente a través de una operación de módulo, terminaríamos necesitando una tabla bastante grande. Entonces, en cambio, empiezo con una cadena de operaciones para reducir la tabla. Cada uno funciona así: tomamos la quinta potencia del valor hash actual; luego reducimos el valor del módulo a una constante (cuya constante depende de la operación que estemos usando). Esta cadena ofrece más ahorros (en términos de reducción del tamaño de la tabla resultante) de lo que cuesta (en términos de la necesidad de codificar la cadena de operaciones en sí), de dos maneras: puede hacer la tablamucho más pequeño (966 en lugar de 3529 entradas), y el uso de múltiples etapas brinda más oportunidades para introducir colisiones beneficiosas (esto no sucedió mucho, pero existe una colisión de este tipo: ambas Deathy Yeenoghuhash hasta 806, lo que nos permite eliminar una. entrada de la mesa, ya que ambos van a&) Los módulos que se usan aquí son [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Por cierto, la razón para elevar a la quinta potencia es que si solo toma el valor directamente, los huecos tienden a permanecer del mismo tamaño, mientras que la exponenciación mueve los huecos y puede hacer que la mesa se distribuya de manera más uniforme después del encadenar en lugar de atascarse en un mínimo local (los huecos distribuidos de manera más uniforme permiten una codificación terser de los tamaños de huecos). Esto tiene que ser un poder extraño para evitar el hecho de que x ² = (- x ) ² introduciendo colisiones, y 5 funcionó mejor que 3.

La primera línea del programa codifica la secuencia de módulos usando la codificación delta:

“…’;“…‘_\
“…’       Compressed integer list encoding, arbitrary sized integers
   ;      Append
    “…‘   Compressed integer list encoding, small integers (≤ 249)
       _\ Take cumulative differences

El resto del programa, el inicio de la segunda línea, implementa la función hash:

OḌ;¢*5$%¥/
O           Take ASCII codepoints
 Ḍ          "Convert from decimal", generalized to values outside the range 0-9
  ;¢        Append the table of moduli from the previous line
         /  Then reduce by:
    *5$       raising to the power 5 (parsing this as a group)
       %¥     and modulusing by the right argument (parsing this as a group, too).

Verificación

Este es el script de Perl que utilicé para verificar que el programa funciona correctamente:

use warnings;
use strict;
use utf8;
use IPC::Run qw/run/;

my %monsters = ("Aleax", "A", "Angel", "A", "Arch Priest", "@", "Archon", "A",
"Ashikaga Takauji", "@", "Asmodeus", "&", "Baalzebub", "&", "Chromatic Dragon",
"D", "Croesus", "@", "Cyclops", "H", "Dark One", "@", "Death", "&", "Demogorgon",
"&", "Dispater", "&", "Elvenking", "@", "Famine", "&", "Geryon", "&",
"Grand Master", "@", "Green-elf", "@", "Grey-elf", "@", "Hippocrates", "@",
"Ixoth", "D", "Juiblex", "&", "Keystone Kop", "K", "King Arthur", "@",
"Kop Kaptain", "K", "Kop Lieutenant", "K", "Kop Sergeant", "K", "Lord Carnarvon",
"@", "Lord Sato", "@", "Lord Surtur", "H", "Master Assassin", "@", "Master Kaen",
"@", "Master of Thieves", "@", "Medusa", "@", "Minion of Huhetotl", "&",
"Mordor orc", "o", "Nalzok", "&", "Nazgul", "W", "Neferet the Green", "@", "Norn",
"@", "Olog-hai", "T", "Oracle", "@", "Orcus", "&", "Orion", "@", "Pelias", "@",
"Pestilence", "&", "Scorpius", "s", "Shaman Karnov", "@", "Thoth Amon", "@",
"Twoflower", "@", "Uruk-hai", "o", "Vlad the Impaler", "V", "Wizard of Yendor",
"@", "Woodland-elf", "@", "Yeenoghu", "&", "abbot", "@", "acid blob", "b",
"acolyte", "@", "air elemental", "E", "aligned priest", "@", "ape", "Y",
"apprentice", "@", "arch-lich", "L", "archeologist", "@", "attendant", "@",
"baby black dragon", "D", "baby blue dragon", "D", "baby crocodile", ":",
"baby gray dragon", "D", "baby green dragon", "D", "baby long worm", "w",
"baby orange dragon", "D", "baby purple worm", "w", "baby red dragon", "D",
"baby silver dragon", "D", "baby white dragon", "D", "baby yellow dragon", "D",
"balrog", "&", "baluchitherium", "q", "barbarian", "@", "barbed devil", "&",
"barrow wight", "W", "bat", "B", "black dragon", "D", "black light", "y",
"black naga hatchling", "N", "black naga", "N", "black pudding", "P",
"black unicorn", "u", "blue dragon", "D", "blue jelly", "j", "bone devil", "&",
"brown mold", "F", "brown pudding", "P", "bugbear", "h", "captain", "@",
"carnivorous ape", "Y", "cave spider", "s", "caveman", "@", "cavewoman", "@",
"centipede", "s", "chameleon", ":", "chickatrice", "c", "chieftain", "@",
"clay golem", "'", "cobra", "S", "cockatrice", "c", "couatl", "A", "coyote", "d",
"crocodile", ":", "demilich", "L", "dingo", "d", "disenchanter", "R", "djinni",
"&", "dog", "d", "doppelganger", "@", "dust vortex", "v", "dwarf king", "h",
"dwarf lord", "h", "dwarf mummy", "M", "dwarf zombie", "Z", "dwarf", "h",
"earth elemental", "E", "electric eel", ";", "elf mummy", "M", "elf zombie", "Z",
"elf", "@", "elf-lord", "@", "energy vortex", "v", "erinys", "&", "ettin mummy",
"M", "ettin zombie", "Z", "ettin", "H", "fire ant", "a", "fire elemental", "E",
"fire giant", "H", "fire vortex", "v", "flaming sphere", "e", "flesh golem", "'",
"floating eye", "e", "fog cloud", "v", "forest centaur", "C", "fox", "d",
"freezing sphere", "e", "frost giant", "H", "gargoyle", "g", "garter snake", "S",
"gas spore", "e", "gecko", ":", "gelatinous cube", "b", "ghost", " ", "ghoul",
"Z", "giant ant", "a", "giant bat", "B", "giant beetle", "a", "giant eel", ";",
"giant mimic", "m", "giant mummy", "M", "giant rat", "r", "giant spider", "s",
"giant zombie", "Z", "giant", "H", "glass golem", "'", "glass piercer", "p",
"gnome king", "G", "gnome lord", "G", "gnome mummy", "M", "gnome zombie", "Z",
"gnome", "G", "gnomish wizard", "G", "goblin", "o", "gold golem", "'",
"golden naga hatchling", "N", "golden naga", "N", "gray dragon", "D", "gray ooze",
"P", "gray unicorn", "u", "green dragon", "D", "green mold", "F", "green slime",
"P", "gremlin", "g", "grid bug", "x", "guard", "@", "guardian naga hatchling",
"N", "guardian naga", "N", "guide", "@", "healer", "@", "hell hound pup", "d",
"hell hound", "d", "hezrou", "&", "high priest", "@", "hill giant", "H",
"hill orc", "o", "hobbit", "h", "hobgoblin", "o", "homunculus", "i",
"horned devil", "&", "horse", "u", "housecat", "f", "human mummy", "M",
"human zombie", "Z", "human", "@", "hunter", "@", "ice devil", "&", "ice troll",
"T", "ice vortex", "v", "iguana", ":", "imp", "i", "incubus", "&", "iron golem",
"'", "iron piercer", "p", "jabberwock", "J", "jackal", "d", "jaguar", "f",
"jellyfish", ";", "ki-rin", "A", "killer bee", "a", "kitten", "f", "knight", "@",
"kobold lord", "k", "kobold mummy", "M", "kobold shaman", "k", "kobold zombie",
"Z", "kobold", "k", "kraken", ";", "large cat", "f", "large dog", "d",
"large kobold", "k", "large mimic", "m", "leather golem", "'", "lemure", "i",
"leocrotta", "q", "leprechaun", "l", "lich", "L", "lichen", "F", "lieutenant",
"@", "little dog", "d", "lizard", ":", "long worm", "w", "lurker above", "t",
"lynx", "f", "mail daemon", "&", "manes", "i", "marilith", "&", "master lich",
"L", "master mind flayer", "h", "mastodon", "q", "mind flayer", "h", "minotaur",
"H", "monk", "@", "monkey", "Y", "mountain centaur", "C", "mountain nymph", "n",
"mumak", "q", "nalfeshnee", "&", "neanderthal", "@", "newt", ":", "ninja", "@",
"nurse", "@", "ochre jelly", "j", "ogre king", "O", "ogre lord", "O", "ogre", "O",
"orange dragon", "D", "orc mummy", "M", "orc shaman", "o", "orc zombie", "Z",
"orc", "o", "orc-captain", "o", "owlbear", "Y", "page", "@", "panther", "f",
"paper golem", "'", "piranha", ";", "pit fiend", "&", "pit viper", "S",
"plains centaur", "C", "pony", "u", "priest", "@", "priestess", "@", "prisoner",
"@", "purple worm", "w", "pyrolisk", "c", "python", "S", "quantum mechanic", "Q",
"quasit", "i", "queen bee", "a", "quivering blob", "b", "rabid rat", "r",
"ranger", "@", "raven", "B", "red dragon", "D", "red mold", "F",
"red naga hatchling", "N", "red naga", "N", "rock mole", "r", "rock piercer", "p",
"rock troll", "T", "rogue", "@", "rope golem", "'", "roshi", "@", "rothe", "q",
"rust monster", "R", "salamander", ":", "samurai", "@", "sandestin", "&",
"sasquatch", "Y", "scorpion", "s", "sergeant", "@", "sewer rat", "r", "shade", " ",
"shark", ";", "shocking sphere", "e", "shopkeeper", "@", "shrieker", "F",
"silver dragon", "D", "skeleton", "Z", "small mimic", "m", "snake", "S",
"soldier ant", "a", "soldier", "@", "spotted jelly", "j", "stalker", "E",
"steam vortex", "v", "stone giant", "H", "stone golem", "'", "storm giant", "H",
"straw golem", "'", "student", "@", "succubus", "&", "tengu", "i", "thug", "@",
"tiger", "f", "titan", "H", "titanothere", "q", "tourist", "@", "trapper", "t",
"troll", "T", "umber hulk", "U", "valkyrie", "@", "vampire bat", "B",
"vampire lord", "V", "vampire", "V", "violet fungus", "F", "vrock", "&", "warg",
"d", "warhorse", "u", "warrior", "@", "watch captain", "@", "watchman", "@",
"water demon", "&", "water elemental", "E", "water moccasin", "S", "water nymph",
"n", "water troll", "T", "werejackal", "d", "wererat", "r", "werewolf", "d",
"white dragon", "D", "white unicorn", "u", "winged gargoyle", "g",
"winter wolf cub", "d", "winter wolf", "d", "wizard", "@", "wolf", "d",
"wood golem", "'", "wood nymph", "n", "woodchuck", "r", "wraith", "W", "wumpus",
"q", "xan", "x", "xorn", "X", "yellow dragon", "D", "yellow light", "y",
"yellow mold", "F", "yeti", "Y", "zruty", "z");

for my $monster (sort keys %monsters) {
    run ["./jelly", "fu", "monsters.j", $monster], \ "", \my $out;
    print "$monster -> \"$out\" (",
        ($out ne $monsters{$monster} ? "in" : ""), "correct)\n";
}

fuente
10

JavaScript (ES6), 915 ... 902 890 bytes

w=>[..."aZM?o@;LWu&P?D@zF@W: @aT&@nCEfvQ&R&Tb'b@&p@:Srn @ahlrdpdT'TRv:HUYG@&fSfYdG&SGHL@Mh@G@gs';@CS@km@OsirA@q@njOZS@O@';HYqHE&DJavq&&aYaBmZMf;bv@EqHg@Z@;dm@M@?@rs@d@@oDAosDT@d@ZeBVrq@jFooD@VV&&BvMEDKiuiPC@&@DYrD&eD@D@@:AwccKZiF:DKLXAwdL@w&@@u'Hc@@q&;D:::WjdN@N@xD&eFh@gh@&Md?&Ye@@&h@hNN'Z&qtKEd@@HtH&@'@&@xd&dZsv@oo@FDyd@@&&@&@HS'Hw?DF@@@MPfDfi'AH&@@pkZkuMyZhFNN'P?d@u@NN&B@uo'fdi@?ke&"].find((_,i)=>!(s-=`GD4~#_@'R<1*~7C7RbZ6F'"Sa&!*1),#''3'.+B6(K$.l%9&!#0@51""~/+!gaW!/.(5'-@0'';!%C.&""!-.$16.2>(#&g!!O,#8A50O!)*(9b|Z4@7V).;*A*HWO(g1$/*-4&SL1I#K$#"3"#=e/'V~4'B(*,.3),$@D3)*76-"\\&kL7(-4#=7!!#+(B/B!-%!"_+!")+)0$1:E84!L191&)(255)!3O<,90NN6&;Q2'"bO=*h7.%1![<o!%M'G5/R.0$-J*%\\~6T?>)16""L&!X94T4"3$!2'^070Y2a"##)#"&n&(+1*&!-M""73R5%'y0~$-6<".MV?+1*ED>!B6b!)%&)8.+$&X0~Q'E%8&#%S/H.1<#>~!sU`.charCodeAt(i)-32),w=w.replace(/\W/g,1),s=parseInt((w+=w+w)[0]+w[2]+w[3]+w[6]+[...w].pop(),36)%8713)

Formateado

A continuación se muestra una versión formateada del código con datos de carga útil truncados.

w => [..."aZM(…)"].find(
  (_, i) =>
    !(s -= `GD4(…)`.charCodeAt(i) - 32),
    w = w.replace(/\W/g, 1),
    s = parseInt((w += w + w)[0] + w[2] + w[3] + w[6] + [...w].pop(), 36) % 8713
)

Cómo funciona

Paso 1

Primero reducimos el nombre del monstruo por:

  1. Reemplazar caracteres no alfanuméricos (espacios y guiones) con 1's.
  2. Repite esta cadena 3 veces para asegurarte de que tenemos suficientes caracteres para trabajar en el siguiente paso.
  3. Mantener solo los caracteres primero, tercero, cuarto, séptimo y último.

Ejemplos:

1.34..7..L
Demogorgon -> Dmorn
^ ^^  ^  ^

             1.34..7.L
orc mummy -> orc1mummy -> oc1my
             ^ ^^  ^ ^

        1.34..7....L
xorn -> xornxornxorn -> xrnrn
        ^ ^^  ^    ^

Esto lleva a algunas colisiones. Por ejemplo, "Master Assassin"y "Master Kaen"ambos se reducen a "Mst1n". Afortunadamente, todos los nombres de monstruos en colisión comparten el mismo símbolo ( @en este caso).

Paso 2

Luego, interpretamos esta cadena de 5 caracteres como una cantidad base 36 para convertirla a decimal (esta operación no distingue entre mayúsculas y minúsculas) y aplicamos un módulo 8713, que fue elegido empíricamente para producir una lista de teclas libre de colisiones.

Ejemplos:

Dmorn --[from base 36]--> 22893539 --[MOD 8713]--> 4488
oc1my --[from base 36]--> 40872778 --[MOD 8713]--> 95
xrnrn --[from base 36]--> 56717843 --[MOD 8713]--> 4926

Paso 3

Todas las claves están ordenadas en orden ascendente:

[ 39, 75, 95, 192, 255, 287, 294, 344, 372, 389, 399, 516, 551, 574, 624, ..., 8635, 8688 ]

Convertido a valores delta:

[ 39, 36, 20, 97, 63, 32, 7, 50, 28, 17, 10, 117, 35, 23, 50, ..., 83, 53 ]

Y codificado como caracteres ASCII en el rango [ 32, 126 ]. Algunos valores ficticios intermedios se insertan cuando la diferencia entre dos claves consecutivas excede la magnitud máxima codificable.

Finalmente, la lista de teclas se asigna a una lista de símbolos dispuestos en el mismo orden.

Prueba

Arnauld
fuente
Según su propio testuite, esto clasifica erróneamente 5 entradas. No he investigado para ver qué los está causando, pero eso probablemente necesita solución.
@ ais523 Eso es lo que obtengo por haber probado solo en Firefox. Intentaré arreglar eso para (al menos) Chrome.
Arnauld
2
@ ais523 Eso ahora debería funcionar bien en FF, Chrome y Edge. Lo siento por eso.
Arnauld
Tuve la idea de extraer bits de los nombres convertidos en números, pero eso obviamente era demasiado pequeño. Felicidades!
Jonas Schäfer
8

Java, 1130 bytes

import java.util.*;class G{public static void main(String[]u){BitSet s=BitSet.valueOf(Base64.getDecoder().decode("D94FuoCWYEIhCTEgLWwRNU/CMB1cE7XBhxBsBCusihaASRg14IJpQMOIDJdFx3BOdDcmThdhILVkCgGsEmhII8UE+SB4kDYEEJzw7Tw54oUEQZe0AUHCACH6nAdqgiZgJhASCIPAEAzJBmuMIrBCHE8IiFjgKQwrN4/90B4QFaLBQBEwTArRBMLCLHQOUQs7ZXZ8B8uGC1EbeAMJBdihUDgCIwGUEKgEAu4W2SJkIAhzB1IQSHgNiEAwABQECV5BvAB7eizABXxFLEg5iMA3whhAFXOKHXEURB7UA7PQjgUK7sji8CmIC0FJsTB4tAMFgiARB3hOJATDsBkgGKnGmWIiIWBRwkMgToQJ49G8gTR4IqcB4vJwDBHSVBLQhpwHsUFipqBcWWaEsCBoGBF0AlNAE305HAfdU1AEbELBO0EERAfkmMkgZcEXDIa4MAp4HcENmYAMBB7UBbTwBqQPSMS9kVkEBMhCudAqBAKaR1CzZggDRw8WMAh0FQPEyKAsRAxzBwn0grwDMQMyQMdADRtFUBAsBQetRRBwcUgrlsQ1IkosBc9B6iBcjAkSDDKgEAQ1wgLIMEEwMkYB42ERBCdiEJMAt1wYSIAQkdIEI0UPNhALsDnRQ1AT/HQi1AyCEwiICOICpiAPlB8MwxnBPIk6JYaIgDy8NJHDsiAqzK0JAXpQPXgPLwJuEEbMTAGBYlQbDESvAXJAAQ=="));int i,j,k,c,d,h=u[0].hashCode(),a=(h&4092)>>2|(h>>5)&1024|(h>>7)&2048|(h>>9)&4096;char r='@';for(i=k=0;i<4297;i+=14){for(c=0,j=7;j>=0;j--)c+=c+(s.get(i+j)?1:0);if((k+=c)==a){for(d=0,j=13;j>=8;j--)d+=d+(s.get(i+j)?1:0);r=d<5?" &':;".charAt(d):(char)((d<31?60:66)+d);}}System.out.println(r);}}

Sin golf:

import java.util.*;

class G {
    public static void main(String[] u) {
        BitSet s = BitSet.valueOf(Base64.getDecoder().decode(
                "D94FuoCWYEIhCTEgLWwRNU/CMB1cE7XBhxBsBCusihaASRg14IJpQMOIDJdFx3BOdDcmThdhILVkCgGsEmhII8UE+SB4kDYEEJzw7Tw54oUEQZe0AUHCACH6nAdqgiZgJhASCIPAEAzJBmuMIrBCHE8IiFjgKQwrN4/90B4QFaLBQBEwTArRBMLCLHQOUQs7ZXZ8B8uGC1EbeAMJBdihUDgCIwGUEKgEAu4W2SJkIAhzB1IQSHgNiEAwABQECV5BvAB7eizABXxFLEg5iMA3whhAFXOKHXEURB7UA7PQjgUK7sji8CmIC0FJsTB4tAMFgiARB3hOJATDsBkgGKnGmWIiIWBRwkMgToQJ49G8gTR4IqcB4vJwDBHSVBLQhpwHsUFipqBcWWaEsCBoGBF0AlNAE305HAfdU1AEbELBO0EERAfkmMkgZcEXDIa4MAp4HcENmYAMBB7UBbTwBqQPSMS9kVkEBMhCudAqBAKaR1CzZggDRw8WMAh0FQPEyKAsRAxzBwn0grwDMQMyQMdADRtFUBAsBQetRRBwcUgrlsQ1IkosBc9B6iBcjAkSDDKgEAQ1wgLIMEEwMkYB42ERBCdiEJMAt1wYSIAQkdIEI0UPNhALsDnRQ1AT/HQi1AyCEwiICOICpiAPlB8MwxnBPIk6JYaIgDy8NJHDsiAqzK0JAXpQPXgPLwJuEEbMTAGBYlQbDESvAXJAAQ=="));

        int i, j, k, c, d, h = u[0].hashCode(), 
            a = (h & 4092) >> 2 | (h >> 5) & 1024 | (h >> 7) & 2048 | (h >> 9) & 4096;
        char r = '@';
        for (i = 0, k = 0; i < 4297; i += 14) {
            for (c = 0, j = 7; j >= 0; j--)
                c += c + (s.get(i + j) ? 1 : 0);
            if ((k += c) == a) {
                for (d = 0, j = 13; j >= 8; j--)
                    d += d + (s.get(i + j) ? 1 : 0);
                r = d < 5 ? " &':;".charAt(d) : (char) ((d < 31 ? 60 : 66) + d);
            }
        }
        System.out.println(r);
    }
}

Los nombres de los monstruos son:

  • hash utilizando el hashcodemétodo Java => 32 bits
  • ANDed con máscara 1001001000111111111100 => 13 bits
  • ordenados de menor a mayor
  • luego usamos los valores delta de la lista ordenada => 8 bits

El carácter de visualización está codificado en 6 bits.

Entonces cada tupla (nombre del monstruo, personaje) usa 14 bits. Todas las tuplas se guardan en un BitSet y codificado en base 64.

Pierdo muchos bytes con codificación base64 y operaciones BitSet :-)

Arnaud
fuente
Puede reducir el tamaño de lo que es la expresión lambda: ()->{...}. La pregunta lo dice en su sección de "aclaraciones".
Olivier Grégoire
5

Mathematica, 1067 bytes (codificación de caracteres romanos de Mac OS)

FromCharacterCode[Mod[Tr/@{c=ToCharacterCode@#,c^2},216,32],"MacintoshRoman"]/.Inner[Rule,";¤7«´3πœ(ú-UU=6z±'¥ÿ†tƒ|\¢KÛd§≤jSóKWÊ8‰Ñwiøì¡ÛhÓ\‡¨:–*~‚¬æº¢»‘¤Á^∫„·nLÒ¤b|$|ÇòCóÌÈS_Ñä.Ëí 5y«KΔË\Ãò™_E`J’ëΔñTV–N„'„Ÿà¥xpîH#-PP)ÈÊVQ©LrBt}∑WÉ∏dÿå„•Tz∑Âao¿rÃ^bbP¨}ëÖ◇1èÇ&d¢¤ái√,B}±BˆÍdA´íBtæÅ/m√yQ6,uãÊ≤/Î!ïøuΩÒÉ)ë“∕C$RY•ÍÍu£oÉÓå‚Ïl.·1‚40ÃÚ¨ÇÆÅccflÓ8Ï Gáç3EÑ¥fXñ¨Àìz~j÷–ñÓz0~ôWtñ}μÎ◇f||Dd\ ÙH﷿É∑Ì´|¿Ö_»RT8Ûª|Äqü‘&6Ãác›Yˆ¿ô5≈ënÚqΩåVä>∫æ∂p ¨jtöåoÌfløÏÏò§¤flÈ;À∑Ѥ·›9né∕<·ì∕ÿmŸ«Ì»j√üà‰÷“5ïä^Ûe◇kd‡“(Ïö71›iΟÁm„ÈïÒß„kÕπ°ÊÓÒçÓfˆ¨flÁ9k|¶ä∕l~Òød‹jZÏ2[kÎ√3ÛâìÓΔE]ıIÚ>{#ÁÖ‚Üâ;·?l^vàß‹‘jîÙÇÅÉú¥äärÆæ™∏Üi≈mØÂ’-%USÌâ’ı Ê›·Ëÿb‡ıÖ31nh™Δ$~%À0n-À´sflk∑p.o5vz}mè]ÎÅç©lt;Îu„ŸW„›ˆˆÍ﷿Ä*7m8‰πór,„Õш/”Ë∕ªß9±‡¶çÁ•âg˜fló)ÖÔ¡'wúæ0ñ„Kûr"~(a=StringPartition)~2,"AAA&&DH&&&&&D&KKKKH&o&WT&&soV&bEYLDD:DDwDwDDDD&q&WBDyNNPuDj&FPhYss:c'ScAd:LdR&dvhhMZhE;MZv&MZHaEHve'evCdeHgSe:b ZaBa;mMrsZH'pGGMZGGo'NNDPuDFPgxNNdd&Hohoi&ufMZ&Tv:i&'pJdf;AafkMkZk;fdkm'iqlLFd:wtf&i&LhqhHYCnq&:jOODMoZooYf';&SCuwcSQiabrBDFNNrpT'qR:&Ysr eFDZmSajEvH'H'&ifHqtTUBVVF&du&ESnTdrdDugddd'nrWqXDyFYz"~a~1,List]/.x_/;StringLength@x>1->"@"&

Función sin nombre que toma una cadena como entrada y devuelve un carácter. La función tiene la siguiente forma:

1  FromCharacterCode[
2    Mod[Tr/@{c=ToCharacterCode@#,c^2},216,32]
3    ,"MacintoshRoman"] /.
4  Inner[Rule,
5    GIANT_STRING_1 ~(a=StringPartition)~2,
6    GIANT_STRING_2 ~a~1,
7    List]
8  /. x_/;StringLength@x>1 -> "@" &

Aquí GIANT_STRING_1 es una cadena que contiene 608 caracteres de un byte en la codificación de caracteres romanos de Mac OS (ninguno de los cuales está en el rango 00-1F), mientras que GIANT_STRING_2 es ​​una cadena que contiene 304 caracteres ASCII.

La línea 2 inicia la función hash: convierte la cadena de entrada en una lista de códigos de caracteres (codificación irrelevante ya que todos son ASCII imprimibles), luego calcula la suma de esos códigos de caracteres y la suma de sus cuadrados, tanto el módulo 216 como el forzado la respuesta está entre 32 y 255. Luego, las líneas 1 y 3 convierten esos pares ordenados de enteros en cadenas de dos caracteres, que es el valor hash que utilizamos en última instancia.

La línea 5 convierte GIANT_STRING_1 en una lista de 304 cadenas de dos caracteres; la línea 6 convierte GIANT_STRING_2 en una lista de 304 cadenas de un carácter. Luego, las líneas 4 y 5 convierten esas dos listas en un conjunto de 304 reglas de reemplazo: si ve tal y tal cadena de dos caracteres, conviértala en tal y tal cadena de un carácter. Finalmente, la línea 8 convierte cualquier cadena de dos caracteres restante en "@".

Hay 71 monstruos en la lista cuyo símbolo es "@", y esos se manejan sin hash (robé esta idea de un comentario de ais523 en otra respuesta). ¡Sucede que los otros 304 valores hash son todos únicos! por lo que no se necesitan otras modificaciones al algoritmo. (Es un golpe de suerte que "human"debe asignarse "@", ya que las sumas de los códigos de caracteres de las letras "human"y las letras "shark"son idénticas, al igual que las sumas de los cuadrados de esos códigos, ¡como enteros, ni siquiera el módulo 216!)

Greg Martin
fuente
3

Python, 2055 bytes

def f(s):import re;m=re.search(s[-3:-1]+s[:2]+str(len(s))+"(.)","omgn5Gteen13vligr7glero10'akga12Sanso11aragi9rgoDe10&tiet5HleVl16Vanst11Hmpmo14nubge15brsho5uingo21Nbuin7&gobl11Dgobl12Duaja6faule10lkest7Eolic9Ttawa15EanKo14KanKo12Kviba12&gore10Dimim3iutzr5zingn10Ganhi10Herfr15emmel9Mlele13'guNa6Wkaja6dotco6docvr5&petr7tmaor10oarli6:nhpi7;moma11&icli4Linbl20Nolwa11Titwr6Wtlgi12ateru12Rbign12Zozgr9Plepa11'oufo9vingu23Norhi8onena10&tati5Hiosc8sinre18Nligo6obeki10aeaow7Yeyfl12elewo10'adsh5 anfr11Hapap3Ygrog4Obequ9ahopy6Steki6fgogr11Dgogr12Dpepi9Sngdi5dindw10hlegl11'imgr11Pbava11Bcero12phaOl8Tdoli10dcuwi15dargn14GotIx5Dinbl13Parwa4dpuhe14dtisa9&ilba14:liho9onyer6&euAs8&aupl14Cttle9qmmdw11Molbr10Fmism11mncPe10&mpwa11noror3oispy8caumo16Clest11'haUr8okekr6;bigi12ZbuBa9&gowh12Dbiko13Zbiet12Zmmgn11Molwe8dmowa11&icde8Lbiho6hdola9dleJu7&otMi18&ulum10Uenpi9&luho10ighye12ymamu5qorwh13ughbl11yylga8gKoKe12Knndj6&mmet11Magbl10Narsh5;osgh5 orxo4Xoltr5Tdoma8qopCy7Hceir12pgoba18Dorlo9wgoba16Dbidw12ZinFa6&goor13DeaAl5Aiuba14qloac9bkemo6Yniqu16QteDi8&aufo14Ckesh8Fetye4Yolro9ryema18hersh15eaggo11Nrase9ranig6:ghba12Winbr13Polwi11dgeti5fzoNa6&orga9emmko12Manfi8aorgn10Gatco6Alecl10'goye13Deabu7hinog9Oheli6Feoch9:ynly4fngte5ieeel12;rawe7ricch11caior11ocala9fguvi13Fangi9aangi5Hhepa7fdesa10:cuOr5&rswa8ubrco5Sorva12Vxaxa3xovlu12tbaba3Bilcr9:geAn5Aolwo4dviic9&tafi14Ecegl13pbugr8xorpu11wgoCh16Dicar9Laggu13Ndegi12shoAr6Aolla12kedce9sitma8&erti11qicma11Lbior10Zviho12&test12vbusu8&fofo3ddeca11srara9rolko6kmpwo10ntaea15Ellbl10jgosi13Daksn5Svibo10&tosk8Zicco10cvera5Bgoba15DatDe5&goba17Dpuwu6qkawe10dmmhu11Mdodo3dunhe10dtcsa9Yckge5:tefi11vsiqu6iloqu14bewne4:yoGe6&caho8fucwo9rorMo10oisje9;taai13Eardw5holye11Fordw10hlloc11jough5Zerfl14emila11mtedu11vthro5qteic10vtuLo11Hmmor9Mirva7Vbagi9Bolro10Tmako13kleir10'biel10Zmmgi11Mnema5ilego10'olre8Forbl13usiwa14Sroba6&agre8Nrohe6&orgr12ulefl11'ocja10JghYe8&aumi8HiuSc8sbihu12Zriki6Ayemi11horko11kolgr10Furle6ianfi10Hmigi11monpo4ullsp13jaiKo11Ktedi12Rapca15Yorog9Oylwi15geegi9;orba14worba16w");return m.group(1)if m else'@'

Aquí está mi arnés de prueba, en caso de que ayude a alguien más.

MAPPING = {
    # as given in the original question
}
def validate_solution(f):
    for k, v in MAPPING.iteritems():
        vv = f(k)
        if vv != v:
            print 'FAIL: f(%s) = %s instead of %s' % (k, vv, v)
    print 'SUCCESS!'

Escribí un pequeño programa para enumerar todas las diversas formas de extraer 4 caracteres más la longitud de la cadena. Mi plan original había sido entoncesord() estos personajes, hacer algunos cálculos con ellos y reducirlo a una función hash perfecta que produjera índices en una tabla de resultados. Así que escribí otro pequeño programa para enumerar todas las diversas formas de sumar / multiplicar / modular estos 4 caracteres juntos; pero las funciones hash resultante mantenían tener forma demasiadas colisiones. Así que finalmente me di por vencido e hice lo que ves aquí, que es solo un mapa de la representación de cadena pequeña del nombre de cada monstruo al símbolo apropiado.

Es decir: lo que quería obtener era

def f(monster_name):
    small_string = f1(monster_name)
    integer_index = f2(small_string)
    symbol = "relatively_short_table"[integer_index]
    return symbol

pero solo logré llegar tan lejos

def f(monster_name):
    small_string = f1(monster_name)
    symbol = {relatively_large_dict}[small_string]
    return symbol

donde mi búsqueda dict {relatively_large_dict}[small_string]se expresa en cuanto re.match(small_string+"(.)", "relatively_large_string")a golfiness.

Quuxplusone
fuente
2

JavaScript (ES6), 1178

n=>'@0uy1c8@@@@@@2cb7sj0sb5rhcm626435y6js6u651b1nj5jg85g2xj02l4wh31u2py2xl96h5fz6ys46tc7821p2e9c1o1td1cy834@2sq2c055iabn91f82vahc6ytagh5d363i@@@@@@@@@@@@@@@@@@@7hh2wf2nd1bu2d93cm0gu862@144819a6v2h44o41d4@@@@@@0c404806f3fa0z8@04c82o1vfac3@c10a3g08g@82e0lr7bf26p2dibcb11t9y19q6bbh4db7tr3592u2bof4913edawy84p1cr@bap1qzb1o033bt6@8d93v230t4240w9ahh8cy@09u0a60sd1qd@1n23ak1bt614bax0ro7sd57xagg22s1gj@@be0@74l01c28qcdi@1so83t0c068s@2jh7as7ddalq0vxag68pn6b9@0gabu71zp54m6997imb2047h@10s0zo0mv@aww6ixbqgag7@944@bza76b@1a053c2yn6101eh8en@4je6fq97t1py9f0@6co@b3k5my44p@4edb737t9@0tl@00rau75y369z5hk0ot@23d2wicb90uwb54a9l3gw9lv3z51nv@@@@@@@amy81e3kh9yc90e59d@6528z42ic@7uv6bm58t@3av0w004t05aavs3oq3040irawj0ov1n90213h89yn0vs@0mcc284fv6uyaxp@3242ok39h0jd06905v1ia@7zc9659bk@ax30ua0um0652sa65daqd@00z03d2ra1f95751xu@9x10676yz@72w33r24b63d@2d7@ats6f678u@bcg9uf6h6@1b60us2d17ygbxn72106t02g@adublf05q@8xu5wobqb1tc1c73cs7pj@87k3cj2xq6258l379y@0q42qy3vs3y70r9@06v2a9@ast4su12w0ko4y77dn@7oubr07ju1ct5qe81v@0d52kb66t4zj@93508c@af30kj@299'.replace(/@\w*/g,v=>~-v.search((100+h.toString(36)).slice(-3))%3?++i:r=String.fromCharCode(i),i=32,r='@',n.replace(/\w/g,c=>h=parseInt(c,36)^(h*3)&16383,h=0))&&r

Menos golf

n=>(
'@0uy1c8@@@@@@2cb7sj0sb5rhcm626435y6js6u651b1nj5jg85g2xj02l4wh31u2py2xl96h5fz6ys46tc7821p2e9c1o1td1cy834@2sq2c055iabn91f82vahc6ytagh5d363i@@@@@@@@@@@@@@@@@@@7hh2wf2nd1bu2d93cm0gu862@144819a6v2h44o41d4@@@@@@0c404806f3fa0z8@04c82o1vfac3@c10a3g08g@82e0lr7bf26p2dibcb11t9y19q6bbh4db7tr3592u2bof4913edawy84p1cr@bap1qzb1o033bt6@8d93v230t4240w9ahh8cy@09u0a60sd1qd@1n23ak1bt614bax0ro7sd57xagg22s1gj@@be0@74l01c28qcdi@1so83t0c068s@2jh7as7ddalq0vxag68pn6b9@0gabu71zp54m6997imb2047h@10s0zo0mv@aww6ixbqgag7@944@bza76b@1a053c2yn6101eh8en@4je6fq97t1py9f0@6co@b3k5my44p@4edb737t9@0tl@00rau75y369z5hk0ot@23d2wicb90uwb54a9l3gw9lv3z51nv@@@@@@@amy81e3kh9yc90e59d@6528z42ic@7uv6bm58t@3av0w004t05aavs3oq3040irawj0ov1n90213h89yn0vs@0mcc284fv6uyaxp@3242ok39h0jd06905v1ia@7zc9659bk@ax30ua0um0652sa65daqd@00z03d2ra1f95751xu@9x10676yz@72w33r24b63d@2d7@ats6f678u@bcg9uf6h6@1b60us2d17ygbxn72106t02g@adublf05q@8xu5wobqb1tc1c73cs7pj@87k3cj2xq6258l379y@0q42qy3vs3y70r9@06v2a9@ast4su12w0ko4y77dn@7oubr07ju1ct5qe81v@0d52kb66t4zj@93508c@af30kj@299'
.replace(/@\w*/g, v= > 
   (v.search((100 + h.toString(36)).slice(-3))-1) % 3  
     ? ++i : r = String.fromCharCode(i),
   i=32,
   r='@',
   n.replace(/\w/g,c => h=parseInt(c,36) ^ (h*3) & 16383,h=0)
)
&& r

Prueba

F=
n=>'@0uy1c8@@@@@@2cb7sj0sb5rhcm626435y6js6u651b1nj5jg85g2xj02l4wh31u2py2xl96h5fz6ys46tc7821p2e9c1o1td1cy834@2sq2c055iabn91f82vahc6ytagh5d363i@@@@@@@@@@@@@@@@@@@7hh2wf2nd1bu2d93cm0gu862@144819a6v2h44o41d4@@@@@@0c404806f3fa0z8@04c82o1vfac3@c10a3g08g@82e0lr7bf26p2dibcb11t9y19q6bbh4db7tr3592u2bof4913edawy84p1cr@bap1qzb1o033bt6@8d93v230t4240w9ahh8cy@09u0a60sd1qd@1n23ak1bt614bax0ro7sd57xagg22s1gj@@be0@74l01c28qcdi@1so83t0c068s@2jh7as7ddalq0vxag68pn6b9@0gabu71zp54m6997imb2047h@10s0zo0mv@aww6ixbqgag7@944@bza76b@1a053c2yn6101eh8en@4je6fq97t1py9f0@6co@b3k5my44p@4edb737t9@0tl@00rau75y369z5hk0ot@23d2wicb90uwb54a9l3gw9lv3z51nv@@@@@@@amy81e3kh9yc90e59d@6528z42ic@7uv6bm58t@3av0w004t05aavs3oq3040irawj0ov1n90213h89yn0vs@0mcc284fv6uyaxp@3242ok39h0jd06905v1ia@7zc9659bk@ax30ua0um0652sa65daqd@00z03d2ra1f95751xu@9x10676yz@72w33r24b63d@2d7@ats6f678u@bcg9uf6h6@1b60us2d17ygbxn72106t02g@adublf05q@8xu5wobqb1tc1c73cs7pj@87k3cj2xq6258l379y@0q42qy3vs3y70r9@06v2a9@ast4su12w0ko4y77dn@7oubr07ju1ct5qe81v@0d52kb66t4zj@93508c@af30kj@299'.replace(/@\w*/g,v=>~-v.search((100+h.toString(36)).slice(-3))%3?++i:r=String.fromCharCode(i),i=32,r='@',n.replace(/\w/g,c=>h=parseInt(c,36)^(h*3)&16383,h=0))&&r


monsters = {
  "Aleax": "A",
  "Angel": "A",
  "Arch Priest": "@",
  "Archon": "A",
  "Ashikaga Takauji": "@",
  "Asmodeus": "&",
  "Baalzebub": "&",
  "Chromatic Dragon": "D",
  "Croesus": "@",
  "Cyclops": "H",
  "Dark One": "@",
  "Death": "&",
  "Demogorgon": "&",
  "Dispater": "&",
  "Elvenking": "@",
  "Famine": "&",
  "Geryon": "&",
  "Grand Master": "@",
  "Green-elf": "@",
  "Grey-elf": "@",
  "Hippocrates": "@",
  "Ixoth": "D",
  "Juiblex": "&",
  "Keystone Kop": "K",
  "King Arthur": "@",
  "Kop Kaptain": "K",
  "Kop Lieutenant": "K",
  "Kop Sergeant": "K",
  "Lord Carnarvon": "@",
  "Lord Sato": "@",
  "Lord Surtur": "H",
  "Master Assassin": "@",
  "Master Kaen": "@",
  "Master of Thieves": "@",
  "Medusa": "@",
  "Minion of Huhetotl": "&",
  "Mordor orc": "o",
  "Nalzok": "&",
  "Nazgul": "W",
  "Neferet the Green": "@",
  "Norn": "@",
  "Olog-hai": "T",
  "Oracle": "@",
  "Orcus": "&",
  "Orion": "@",
  "Pelias": "@",
  "Pestilence": "&",
  "Scorpius": "s",
  "Shaman Karnov": "@",
  "Thoth Amon": "@",
  "Twoflower": "@",
  "Uruk-hai": "o",
  "Vlad the Impaler": "V",
  "Wizard of Yendor": "@",
  "Woodland-elf": "@",
  "Yeenoghu": "&",
  "abbot": "@",
  "acid blob": "b",
  "acolyte": "@",
  "air elemental": "E",
  "aligned priest": "@",
  "ape": "Y",
  "apprentice": "@",
  "arch-lich": "L",
  "archeologist": "@",
  "attendant": "@",
  "baby black dragon": "D",
  "baby blue dragon": "D",
  "baby crocodile": ":",
  "baby gray dragon": "D",
  "baby green dragon": "D",
  "baby long worm": "w",
  "baby orange dragon": "D",
  "baby purple worm": "w",
  "baby red dragon": "D",
  "baby silver dragon": "D",
  "baby white dragon": "D",
  "baby yellow dragon": "D",
  "balrog": "&",
  "baluchitherium": "q",
  "barbarian": "@",
  "barbed devil": "&",
  "barrow wight": "W",
  "bat": "B",
  "black dragon": "D",
  "black light": "y",
  "black naga hatchling": "N",
  "black naga": "N",
  "black pudding": "P",
  "black unicorn": "u",
  "blue dragon": "D",
  "blue jelly": "j",
  "bone devil": "&",
  "brown mold": "F",
  "brown pudding": "P",
  "bugbear": "h",
  "captain": "@",
  "carnivorous ape": "Y",
  "cave spider": "s",
  "caveman": "@",
  "cavewoman": "@",
  "centipede": "s",
  "chameleon": ":",
  "chickatrice": "c",
  "chieftain": "@",
  "clay golem": "'",
  "cobra": "S",
  "cockatrice": "c",
  "couatl": "A",
  "coyote": "d",
  "crocodile": ":",
  "demilich": "L",
  "dingo": "d",
  "disenchanter": "R",
  "djinni": "&",
  "dog": "d",
  "doppelganger": "@",
  "dust vortex": "v",
  "dwarf king": "h",
  "dwarf lord": "h",
  "dwarf mummy": "M",
  "dwarf zombie": "Z",
  "dwarf": "h",
  "earth elemental": "E",
  "electric eel": ";",
  "elf mummy": "M",
  "elf zombie": "Z",
  "elf": "@",
  "elf-lord": "@",
  "energy vortex": "v",
  "erinys": "&",
  "ettin mummy": "M",
  "ettin zombie": "Z",
  "ettin": "H",
  "fire ant": "a",
  "fire elemental": "E",
  "fire giant": "H",
  "fire vortex": "v",
  "flaming sphere": "e",
  "flesh golem": "'",
  "floating eye": "e",
  "fog cloud": "v",
  "forest centaur": "C",
  "fox": "d",
  "freezing sphere": "e",
  "frost giant": "H",
  "gargoyle": "g",
  "garter snake": "S",
  "gas spore": "e",
  "gecko": ":",
  "gelatinous cube": "b",
  "ghost": " ",
  "ghoul": "Z",
  "giant ant": "a",
  "giant bat": "B",
  "giant beetle": "a",
  "giant eel": ";",
  "giant mimic": "m",
  "giant mummy": "M",
  "giant rat": "r",
  "giant spider": "s",
  "giant zombie": "Z",
  "giant": "H",
  "glass golem": "'",
  "glass piercer": "p",
  "gnome king": "G",
  "gnome lord": "G",
  "gnome mummy": "M",
  "gnome zombie": "Z",
  "gnome": "G",
  "gnomish wizard": "G",
  "goblin": "o",
  "gold golem": "'",
  "golden naga hatchling": "N",
  "golden naga": "N",
  "gray dragon": "D",
  "gray ooze": "P",
  "gray unicorn": "u",
  "green dragon": "D",
  "green mold": "F",
  "green slime": "P",
  "gremlin": "g",
  "grid bug": "x",
  "guard": "@",
  "guardian naga hatchling": "N",
  "guardian naga": "N",
  "guide": "@",
  "healer": "@",
  "hell hound pup": "d",
  "hell hound": "d",
  "hezrou": "&",
  "high priest": "@",
  "hill giant": "H",
  "hill orc": "o",
  "hobbit": "h",
  "hobgoblin": "o",
  "homunculus": "i",
  "horned devil": "&",
  "horse": "u",
  "housecat": "f",
  "human mummy": "M",
  "human zombie": "Z",
  "human": "@",
  "hunter": "@",
  "ice devil": "&",
  "ice troll": "T",
  "ice vortex": "v",
  "iguana": ":",
  "imp": "i",
  "incubus": "&",
  "iron golem": "'",
  "iron piercer": "p",
  "jabberwock": "J",
  "jackal": "d",
  "jaguar": "f",
  "jellyfish": ";",
  "ki-rin": "A",
  "killer bee": "a",
  "kitten": "f",
  "knight": "@",
  "kobold lord": "k",
  "kobold mummy": "M",
  "kobold shaman": "k",
  "kobold zombie": "Z",
  "kobold": "k",
  "kraken": ";",
  "large cat": "f",
  "large dog": "d",
  "large kobold": "k",
  "large mimic": "m",
  "leather golem": "'",
  "lemure": "i",
  "leocrotta": "q",
  "leprechaun": "l",
  "lich": "L",
  "lichen": "F",
  "lieutenant": "@",
  "little dog": "d",
  "lizard": ":",
  "long worm": "w",
  "lurker above": "t",
  "lynx": "f",
  "mail daemon": "&",
  "manes": "i",
  "marilith": "&",
  "master lich": "L",
  "master mind flayer": "h",
  "mastodon": "q",
  "mind flayer": "h",
  "minotaur": "H",
  "monk": "@",
  "monkey": "Y",
  "mountain centaur": "C",
  "mountain nymph": "n",
  "mumak": "q",
  "nalfeshnee": "&",
  "neanderthal": "@",
  "newt": ":",
  "ninja": "@",
  "nurse": "@",
  "ochre jelly": "j",
  "ogre king": "O",
  "ogre lord": "O",
  "ogre": "O",
  "orange dragon": "D",
  "orc mummy": "M",
  "orc shaman": "o",
  "orc zombie": "Z",
  "orc": "o",
  "orc-captain": "o",
  "owlbear": "Y",
  "page": "@",
  "panther": "f",
  "paper golem": "'",
  "piranha": ";",
  "pit fiend": "&",
  "pit viper": "S",
  "plains centaur": "C",
  "pony": "u",
  "priest": "@",
  "priestess": "@",
  "prisoner": "@",
  "purple worm": "w",
  "pyrolisk": "c",
  "python": "S",
  "quantum mechanic": "Q",
  "quasit": "i",
  "queen bee": "a",
  "quivering blob": "b",
  "rabid rat": "r",
  "ranger": "@",
  "raven": "B",
  "red dragon": "D",
  "red mold": "F",
  "red naga hatchling": "N",
  "red naga": "N",
  "rock mole": "r",
  "rock piercer": "p",
  "rock troll": "T",
  "rogue": "@",
  "rope golem": "'",
  "roshi": "@",
  "rothe": "q",
  "rust monster": "R",
  "salamander": ":",
  "samurai": "@",
  "sandestin": "&",
  "sasquatch": "Y",
  "scorpion": "s",
  "sergeant": "@",
  "sewer rat": "r",
  "shade": " ",
  "shark": ";",
  "shocking sphere": "e",
  "shopkeeper": "@",
  "shrieker": "F",
  "silver dragon": "D",
  "skeleton": "Z",
  "small mimic": "m",
  "snake": "S",
  "soldier ant": "a",
  "soldier": "@",
  "spotted jelly": "j",
  "stalker": "E",
  "steam vortex": "v",
  "stone giant": "H",
  "stone golem": "'",
  "storm giant": "H",
  "straw golem": "'",
  "student": "@",
  "succubus": "&",
  "tengu": "i",
  "thug": "@",
  "tiger": "f",
  "titan": "H",
  "titanothere": "q",
  "tourist": "@",
  "trapper": "t",
  "troll": "T",
  "umber hulk": "U",
  "valkyrie": "@",
  "vampire bat": "B",
  "vampire lord": "V",
  "vampire": "V",
  "violet fungus": "F",
  "vrock": "&",
  "warg": "d",
  "warhorse": "u",
  "warrior": "@",
  "watch captain": "@",
  "watchman": "@",
  "water demon": "&",
  "water elemental": "E",
  "water moccasin": "S",
  "water nymph": "n",
  "water troll": "T",
  "werejackal": "d",
  "wererat": "r",
  "werewolf": "d",
  "white dragon": "D",
  "white unicorn": "u",
  "winged gargoyle": "g",
  "winter wolf cub": "d",
  "winter wolf": "d",
  "wizard": "@",
  "wolf": "d",
  "wood golem": "'",
  "wood nymph": "n",
  "woodchuck": "r",
  "wraith": "W",
  "wumpus": "q",
  "xan": "x",
  "xorn": "X",
  "yellow dragon": "D",
  "yellow light": "y",
  "yellow mold": "F",
  "yeti": "Y",
  "zruty": "z"
}
err = ok = 0

for(name in monsters) {
  code = monsters[name]
  result = F(name)
  if (result != code)
    console.log('ERROR',++err, name, result, code)
  else
    ++ok
}
console.log('Errors',err,'OK', ok)

edc65
fuente
2

Javascript, 1185 bytes

s=>{h=0;for(i of s)h=(h<<5)-h+i.charCodeAt()|0;for(v of "Aqgh201etxitsxy0_&ctpzfekt09j36uafamqw46mz1qcxvnnoego4212nxfivutt09qyac4td1ayiotfh3dvub5fggzjqa58h37bnva3dzy_D9wlywkgkifldlp6t46v97basg905f8wadwt0w49q0gk9c8edz9e33uj6esjl_Hkkt54kr0qdlxs6hxdxxyegrdzcmz8ymvg_Ki0enu0ct1shv_o193ve2y3tpa71xu3pud405o7_We09jfsayx_Tw2gk0spoqab5c9k_s7timco3yh674rp1_Vppq2k9t1q_b3mo3tac13_E0r50a7vi5a0kgim_Y2omnjbkq59mw5njf5t_Lu9z2bj6w2128_:n0gngsocqeuh5czhyiedwd3a_w9lf1hv1rra7r_qmckg7rbhlldbvros4f44h_B32t12yzdci83_yjkb3va_Nt2cbaqd46toc29anic1qq3es_P3mkmtv2l4j8r_ukjb44lwm5vkaz5hwkh_j3oo7uj9ip_Fzuk8mh1rpfw7obl6s9fsq_hzmwz3f7kdhiaj4enlxha1_c0q0yu8tnf_'nf7c1sks8rzgxhw83vjq0s76xhrvppbgn_Slr90h5su3zokncwi2m_doi5t2p4vw6dryycyhtl6eujb1ta26752ta7hr19d9vceq_Rqk8tsy_vuxwglitt4u25zfhj5q_M4j7tjk9cryvqn8101u5h646p_Ztzwr09t8ckxx3hbsl6r7dqv7qxmnwt_;u7r3e9trqqkmdj5tlx_apoj0ngpcqy6r7t8gw9_e2wtyw9oyve8uxlf_C8tpo3hlb3_gxji2n2nl4_ kwft9p_maxcdzat5e_rcy28c360mmndp8ksxh_pegqkkuur3_Gh6f8pheo0nn2_xu6yjdx_iz538jwkbwuh4ge7ymj_f3eytt6khltgxj13itedbz_Jlgk_knskybpe8n69a_llnv_tuxgkxc_nod5ob3cft_Oij0a222q3_Q6af_Uc5x_Xzjn_z6iq".split`_`)if(~v.slice(1).match(/.../g).indexOf(h.toString(36).slice(-3)))return v[0];return"@"}

Utiliza una versión de golf del hash de cadena Javascript que se encuentra aquí. El hash real almacenado en la tabla (esa cadena larga) toma el valor absoluto del hash producido por ese método, lo convierte a base-36 y suelta todos menos los tres dígitos menos significativos.

SuperJedi224
fuente
1
Entonces, por lo que puedo decir, ¿estás haciendo hash por {primer carácter, último carácter, longitud} y luego estás usando una tabla de búsqueda grande? Eso tiene sentido, pero creo que hay un par de mejoras que podría hacer: hay algunas entradas duplicadas en la tabla, y podría ahorrar bastante espacio eliminando las entradas @de la tabla y simplemente omitiendo @si la entrada no se encuentra
2
cavewomany chameleontener el mismo primer carácter, último carácter y longitud, ¿puede ser un problema?
Arnaud
1
split("_")puede llegar a ser split tilde _ tilde
user2428118
@SuperChafouin fijo.
SuperJedi224
1
@ SuperJedi224 Hay otros: Cyclopsy Croesus, baluchitheriumy baby long worm, crocodiley centipede, y 24 más
Arnaud
1

Python 3, 1915 1900 bytes

Registro de cambios:

  • Trabajar y generar código ASCII en lugar del propio carácter (guardado 15 bytes)

Pase el nombre del monstruo como primer argumento de línea de comando, reciba el personaje en stdout.

import sys
D=b'`"\x08\x04\x02&@Yx\xf6\x90a\x00Z\x00\x00c\x00X\x00\x00f\x00z\x00\x00hS\x12\x06\t@PSTft?z\x0fnK\nH\x87\xa2ig\t\t\x12 &;@FZkoq\x05\xfc~?\x1b\x80\xc2,z\r\xf3Y\x141\x9cS\x10\x80jU\x06\x08\t&;@BKpqr\x9f\xbe\xbb\xf9O\xcde\x03!kK\x11\x07\x07&:@WYsu\x1boDv\xc9i\x90lS$\x06\r@Sdirw\x1f\x1d\x198\xb3\xb2\x91\x0fm\xa5\x03A@mB#\x07\x07@GPWdiv\x7f;n\xb3Bk\xa5ng\x07\x0c\x16&@EHSVcdfqru\x01\xfen\x83q\xd8\xf3\x1c.\xe5\xac^\x87\t\xaaT\xd4D\x9c\xe1*Io;\x03\x05\x06@desu\x01\xf7\x95R0\x88pc \x08\n:@KMNknq\xfd\xfe\ru\xb2z\xea\\\x9b\x05qC\x08\x07\x06&@AGOfhy\xe2\xbbA\xf2ArS\x1e\x08\x08&@JVYdfi_\x1c\xd8/k\x89\xa8\xe0sw\x08\x0b\x1c&;@Kdfhijou\t\xe0[# \\\x9a\xd3F(L\xfapM\tp\xa8t\xccp\x8d\x11e+\x05\x0c\x8a\x08t+)\x04\x02@PQT\xf2\x94uG\x1c\x06\t&@Uilq\x0f\ryl\xc4`\xa5\x10\x90v\x85\r\x0e$&:@FKLNORSWYry\x9f\x97\xf8\xae\xb8\xdf\xdd\xc1\xcdl\xb2\xc9L|\xbb;\x92\xb8j\xb0\xa99\xdd\x9c\xb8\xd0\x8bh\x95\x88T\xb3;1\xb6\x0bwb\x06\x0c\x11&:;@DGHOVhkm\x02\xfe\x8fO{\xd9u\xac&\xd7\x90\x9fe\xc0\xf44GxW\x07\x07\x0bADHScdv?>\xdd<:\xb7s.\x8cI\x07yR\x07\x07\t&:@bcht;Zx\x16sO\x8d\xab\xc3ze\x0b\x08\x14&@ABCaqs\x01}\xbe=\x15\xc6\xcdL\xa1\xc8\x9e.\xf7\x02\xc1Xq4\x99\t{G\x16\x06\t@Faefg\x1f\x9bU$2P`\xa8\x80|G\x15\x06\x07&\';@Go\x1c1\\\xa7*\x0bS}s\x06\n" &@AHLYZdh\xf6\x1e\t\xb93N2\xc27\xd6\xd8\xd8*\xe5L\xa3\xa4f\x860A\xfa:7.\xdd\x9b)\xb80\x85\xc4\xb4\x83~W\x0e\x07\r&:@ERbd>\x1b\xda\x15\xd4\x92\x0eM\xacJH\x04c\x7fG\x00\x06\x08:@dghx\x1f\xbc\xf4Z\xa1%\xd3C'
R=range
N=sys.argv[1].lower()
B=0
for c in N:B|=ord(c)&0x7f;B<<=7
B%=2**62-1
P=N.split()
F=ord(P[-1][0])^(ord(P[-1][1])>>2)
while D:
 f=D[0];ik,j,h,n=D[1:5];i=ik>>4;k=ik&15;D=D[5:];c=D[:h];m=D[h:h+n];m=int.from_bytes(m,"big");s=1;C=j;b=(h-1).bit_length()
 for x in R(i-1):s<<=k;s|=1
 s<<=j;z=(B&s)>>j;x=0;u=1
 for y in R(i):x<<=1;x|=bool(z&u);u<<=k
 if f!=F:D=D[h+n:];continue
 while m:
  if m&(2**i-1)==x:m>>=i;C=c[m&(2**b-1)];break
  m>>=b+i
 break
print(C)

Cuando leí la pregunta, pensé "Necesito comprimir esto". El primer paso fue poner en minúscula todos los nombres.

Al mirar los datos, sentí que de alguna manera usar la primera letra de la última palabra debería ser el truco como una primera aproximación aproximada de qué letras podría tener el monstruo. Como resultado, esa fue una suposición inicial poderosa. La siguiente tabla es "primer carácter de la última palabra", "número de visitas", "caracteres de monstruos":

 'd' (37) => & @ D L R d h
 'g' (31) =>   & ' : @ G H Z g o
 's' (30) =>   & : ; @ E F H K P S Y Z e k o s
 'm' (28) => & @ F H M Q R S Y i m q r
 'c' (24) => : @ A C H S b c d f s v
 'p' (20) => & ; @ P S c d f p u
 'w' (20) => @ G W d q r u w
 'a' (19) => & @ A L Y a t
 'h' (17) => & @ N U d f h i o u
 'l' (17) => : @ F G K L O V f h i k l q y
 'n' (15) => & : @ N W n
 't' (14) => @ H T f i q t
 'b' (14) => & @ B a b h q x
 'k' (13) => ; @ A G K O f h k
 'e' (12) => & ; @ E H e
 'o' (12) => & @ O P T Y o
 'z' ( 9) => Z z
 'v' ( 9) => & @ S V v
 'r' ( 8) => @ B q r
 'j' ( 8) => & ; J d f j
 'f' ( 6) => & F d h
 'i' ( 5) => & : D V i
 'u' ( 4) => o u
 'y' ( 3) => & @ Y
 'x' ( 2) => X x
 'q' ( 1) => i

Para mejorar aún más la dispersión, modifiqué ligeramente la clave, haciendo XOR con el segundo carácter de la última palabra, desplazada a bits a la derecha, en el primer carácter (llamemos a esta construcción first_key):

 '}' (29) =>   & @ A H L Y Z d h
 'v' (25) => & : @ F K L N O R S W Y r y
 'x' (25) => A D H S c d v
 's' (21) => & ; @ K d f h i j o u
 'p' (21) => : @ K M N k n q
 'z' (19) => & @ A B C a q s
 'n' (19) => & @ E H S V c d f q r u
 '|' (18) => & ' ; @ G o
 'l' (17) => @ S d i r w
 '~' (16) => & : @ E R b d
 '{' (15) => @ F a e f g
 'w' (14) => & : ; @ D G H O V h k m
 'i' (14) =>   & ; @ F Z k o q
 'j' (13) => & ; @ B K p q r
 'u' (12) => & @ U i l q
 'm' (12) => @ G P W d i v
 '\x7f' (11) => : @ d g h x
 'o' (11) => @ d e s u
 'h' (11) => @ P S T f t
 'y' (10) => & : @ b c h t
 'r' ( 9) => & @ J V Y d f i
 'k' ( 9) => & : @ W Y s u
 'a' ( 8) => Z
 'q' ( 7) => & @ A G O f h
 't' ( 6) => @ P Q T
 '`' ( 4) => & @ Y x
 'c' ( 1) => X
 'f' ( 1) => z

Como puede ver, esto nos da nueve nombres que pueden mapearse únicamente con esa información. ¡Agradable!

Ahora necesitaba encontrar el mapeo restante. Para esto comencé convirtiendo el nombre completo (en minúsculas) a un entero:

def name_to_int(name):
    bits = 0
    for c in name:
        bits |= ord(c) & 0x7f
        bits <<= 7
    return bits

Esto simplemente concatena los valores ASCII de 7 bits de los nombres en un número entero enorme. Tomamos este módulo 4611686018427387903(2⁶²-1) para los próximos pasos.

Ahora trato de encontrar una máscara de bits que produzca un número entero que a su vez distinga muy bien a los diferentes personajes de monstruos. Las máscaras de bits consisten en unos distribuidos uniformemente (como 101010101o 1000100010001) y están parametrizados por el número de bits ( i>=1) y el spread ( k>=1). Además, las máscaras se desplazan a la izquierda hasta 32*ibits. Esos son AND-ed con el nombre integerizado y el entero resultante se usa como clave en un mapeo. Se i*number_of_mapping_entriesutiliza el mejor mapeo libre de conflictos (calificado por ).

Los enteros obtenidos de AND-ing de la máscara y el nombre integerizado se desplazan hacia atrás por jbits y se les quita sus ceros (almacenamos i, ky jjunto con el mapeo para poder reconstruir eso), ahorrando mucho espacio.

Así que ahora tenemos un mapeo de dos niveles: desde first_keyel hashmap, y el hashmap asigna el nombre completo al monstruo char únicamente. Necesitamos almacenar eso de alguna manera. Cada entrada de la asignación de nivel superior se ve así:

Row = struct.Struct(
    ">"
    "B"  # first word char
    "B"  # number of bits (i) and bit spacing (k)
    "B"  # shift (j) or character to map to if i = 0
    "B"  # number of monster characters
    "B"  # map entry bytes
)

seguido por los personajes monstruos y el mapeo de segundo nivel.

El mapeo de segundo nivel se serializa empaquetándolo en un entero grande y convirtiéndolo en bytes. Cada valor y clave se desplaza consecutivamente al número entero, lo que hace que el mapeo sea reconstruible (el número de bits por clave / valor es inferible a partir del número de caracteres yi , ambos almacenados en la entrada de la fila).

Si una entrada tiene un solo personaje monstruoso posible para asignar, ies cero, el número de caracteres y la asignación también son cero bytes. El personaje se almacena donde jnormalmente se almacenaría.

Los datos completos tienen un tamaño de 651 bytes, serializados como una cadena de bytes de python de 1426 bytes.

El programa de decodificación esencialmente lo hace al revés: primero extrae el first_key y busca en los datos la entrada correspondiente. Luego calcula el hash del nombre y busca en el hashmap la entrada correspondiente.

Decodificador no ofuscado

#!/usr/bin/python3
import sys
import math

data = b'`"\x08\x04\x02&@Yx\xf6\x90a\x00Z\x00\x00c\x00X\x00\x00f\x00z\x00\x00hS\x12\x06\t@PSTft?z\x0fnK\nH\x87\xa2ig\t\t\x12 &;@FZkoq\x05\xfc~?\x1b\x80\xc2,z\r\xf3Y\x141\x9cS\x10\x80jU\x06\x08\t&;@BKpqr\x9f\xbe\xbb\xf9O\xcde\x03!kK\x11\x07\x07&:@WYsu\x1boDv\xc9i\x90lS$\x06\r@Sdirw\x1f\x1d\x198\xb3\xb2\x91\x0fm\xa5\x03A@mB#\x07\x07@GPWdiv\x7f;n\xb3Bk\xa5ng\x07\x0c\x16&@EHSVcdfqru\x01\xfen\x83q\xd8\xf3\x1c.\xe5\xac^\x87\t\xaaT\xd4D\x9c\xe1*Io;\x03\x05\x06@desu\x01\xf7\x95R0\x88pc \x08\n:@KMNknq\xfd\xfe\ru\xb2z\xea\\\x9b\x05qC\x08\x07\x06&@AGOfhy\xe2\xbbA\xf2ArS\x1e\x08\x08&@JVYdfi_\x1c\xd8/k\x89\xa8\xe0sw\x08\x0b\x1c&;@Kdfhijou\t\xe0[# \\\x9a\xd3F(L\xfapM\tp\xa8t\xccp\x8d\x11e+\x05\x0c\x8a\x08t+)\x04\x02@PQT\xf2\x94uG\x1c\x06\t&@Uilq\x0f\ryl\xc4`\xa5\x10\x90v\x85\r\x0e$&:@FKLNORSWYry\x9f\x97\xf8\xae\xb8\xdf\xdd\xc1\xcdl\xb2\xc9L|\xbb;\x92\xb8j\xb0\xa99\xdd\x9c\xb8\xd0\x8bh\x95\x88T\xb3;1\xb6\x0bwb\x06\x0c\x11&:;@DGHOVhkm\x02\xfe\x8fO{\xd9u\xac&\xd7\x90\x9fe\xc0\xf44GxW\x07\x07\x0bADHScdv?>\xdd<:\xb7s.\x8cI\x07yR\x07\x07\t&:@bcht;Zx\x16sO\x8d\xab\xc3ze\x0b\x08\x14&@ABCaqs\x01}\xbe=\x15\xc6\xcdL\xa1\xc8\x9e.\xf7\x02\xc1Xq4\x99\t{G\x16\x06\t@Faefg\x1f\x9bU$2P`\xa8\x80|G\x15\x06\x07&\';@Go\x1c1\\\xa7*\x0bS}s\x06\n" &@AHLYZdh\xf6\x1e\t\xb93N2\xc27\xd6\xd8\xd8*\xe5L\xa3\xa4f\x860A\xfa:7.\xdd\x9b)\xb80\x85\xc4\xb4\x83~W\x0e\x07\r&:@ERbd>\x1b\xda\x15\xd4\x92\x0eM\xacJH\x04c\x7fG\x00\x06\x08:@dghx\x1f\xbc\xf4Z\xa1%\xd3C'


def name_to_int(name):
    bits = 0
    for c in name:
        bits |= ord(c) & 0x7f
        bits <<= 7
    return bits


def make_mask(nbits, k):
    mask = 1
    for i in range(nbits-1):
        mask <<= k
        mask |= 1
    return mask


def collapse_mask(value, nbits, k):
    bits = 0
    shift = 0
    for i in range(nbits):
        bits <<= 1
        bits |= bool(value & (1<<shift))
        shift += k
    return bits


name = sys.argv[1].casefold()
last_word = name.split()[-1]
last_word_char = chr(ord(last_word[0]) ^ (ord(last_word[1]) >> 2))
while data:
    first_char = chr(data[0])
    ik, j, nchars, nbytes = data[1:5]

    i = ik >> 4
    k = ik & 15

    data = data[5:]
    if first_char != last_word_char:
        # skip this entry
        data = data[nchars+nbytes:]
        continue

    chars, mapping = data[:nchars], data[nchars:nchars+nbytes]
    result = j
    if i == 0:
        break

    mapping = int.from_bytes(mapping, "big")

    name_bits = name_to_int(name) % (2**62-1)
    mask = make_mask(i, k) << j
    key = collapse_mask((name_bits & mask) >> j, i, k)
    bits_per_key = i
    key_mask = 2**(bits_per_key)-1
    bits_per_value = math.ceil(math.log(len(chars), 2))
    value_mask = 2**(bits_per_value)-1
    while mapping:
        if mapping & key_mask == key:
            mapping >>= bits_per_key
            result = chars[mapping & value_mask]
            break
        mapping >>= bits_per_value+bits_per_key

    break
print(chr(result))

Herramienta de análisis

Esta es la herramienta que creé y utilicé para generar los datos; lea bajo su propio riesgo:

#!/usr/bin/python3
import base64
import collections
import math
import json
import struct
import zlib

data = json.load(open("data.json"))

reverse_pseudomap = {}
forward_pseudomap = {}
forward_info = {}
reverse_fullmap = {}
hits = collections.Counter()
monster_char_hitmap = collections.Counter()

for name, char in data.items():
    name = name.casefold()
    parts = name.split()
    monster_char_hitmap[char] += 1

    # if len(parts) > 1:
    #     key = first_char + parts[0][0]
    # else:
    #     key = first_char + last_part[1]

    key = chr(ord(parts[-1][0]) ^ (ord(parts[-1][1]) >> 2))
    # key = parts[-1][0]

    hits[key] += 1
    reverse_pseudomap.setdefault(char, set()).add(key)
    forward_pseudomap.setdefault(key, set()).add(char)
    forward_info.setdefault(key, {})[name] = char
    reverse_fullmap.setdefault(char, set()).add(name)


for char, hit_count in sorted(hits.items(), key=lambda x: x[1], reverse=True):
    monsters = forward_pseudomap[char]
    print(" {!r} ({:2d}) => {}".format(
        char,
        hit_count,
        " ".join(sorted(monsters))
    ))


def make_mask(nbits, k):
    mask = 1
    for i in range(nbits-1):
        mask <<= k
        mask |= 1
    return mask


def collapse_mask(value, nbits, k):
    bits = 0
    shift = 0
    for i in range(nbits):
        bits <<= 1
        bits |= bool(value & (1<<shift))
        shift += k
    return bits


def expand_mask(value, nbits, k):
    bits = 0
    for i in range(nbits):
        bits <<= k
        bits |= value & 1
        value >>= 1
    return bits


assert collapse_mask(expand_mask(0b110110, 6, 3), 6, 3)
assert expand_mask(collapse_mask(0b1010101, 7, 3), 7, 3)


def name_to_int(name):
    # mapped_name = "".join({"-": "3", " ": "4"}.get(c, c) for c in name)
    # if len(mapped_name) % 8 != 0:
    #     if len(mapped_name) % 2 == 0:
    #         mapped_name += "7"
    #     mapped_name = mapped_name + "="*(8 - (len(mapped_name) % 8))
    # print(mapped_name)
    # return base64.b32decode(
    #     mapped_name,
    #     casefold=True,
    # )

    bits = 0
    for c in name:
        bits |= ord(c) & 0x7f
        bits <<= 7
    return bits


compressed_maps = {}
max_bit_size = 0
nmapentries = 0


for first_char, monsters in sorted(forward_info.items()):
    monster_chars = forward_pseudomap[first_char]
    print("trying to find classifier for {!r}".format(first_char))
    print("  {} monsters with {} symbols".format(
        len(monsters),
        len(monster_chars))
    )
    bits = math.log(len(monster_chars), 2)
    print("  {:.2f} bits of clever entropy needed".format(
        bits
    ))

    bits = math.ceil(bits)

    int_monsters = {
        name_to_int(name): char
        for name, char in monsters.items()
    }

    reverse_map = {}
    for name, char in int_monsters.items():
        reverse_map.setdefault(char, set()).add(name)

    solution = None
    solution_score = float("inf")

    if bits == 0:
        char = ord(list(int_monsters.values())[0][0])
        solution = 0, 0, char, {}

    for i in range(bits, 3*bits+1):
        print("  trying to find solution with {} bits".format(i))
        for k in [2, 3, 5, 7, 11]:
            mask = make_mask(i, k)
            for j in range(0, 32*bits):
                bucketed = {}
                for int_name, char in int_monsters.items():
                    bucket = (int_name % (2**62-1)) & mask
                    try:
                        if bucketed[bucket] != char:
                            break
                    except KeyError:
                        bucketed[bucket] = char
                else:
                    new_solution_score = i*len(bucketed)
                    if new_solution_score < solution_score:
                        print("   found mapping: i={}, k={}, j={}, mapping={}".format(
                            i, k, j, bucketed
                        ))
                        solution = i, k, j, bucketed
                        solution_score = new_solution_score
                mask <<= 1

    if solution is not None:
        print("  solution found!")

    chars = "".join(sorted(set(int_monsters.values())))
    i, k, j, mapping = solution

    # sanity check 1
    if i > 0:
        mask = make_mask(i, k) << j
        for int_name, char in int_monsters.items():
            key = (int_name % (2**62-1)) & mask
            assert mapping[key] == char

    compressed_mapping = {}
    for hash_key, char in mapping.items():
        hash_key = collapse_mask(hash_key >> j, i, k)
        max_bit_size = max(hash_key.bit_length(), max_bit_size)
        compressed_mapping[hash_key] = chars.index(char)

    nmapentries += len(compressed_mapping)
    compressed_maps[first_char] = i, k, j, chars, compressed_mapping

    print(" ", compressed_maps[first_char])

    print()

print("max_bit_size =", max_bit_size)
print("nmapentries =", nmapentries)

print("approx size =", (1+math.ceil(max_bit_size/8))*nmapentries)


# first we need to map first word chars to compressed mappings
Row = struct.Struct(
    ">"
    "B"  # first word char
    "B"  # number of bits (i) and bit spacing (k)
    "B"  # shift (j) or character to map to if i = 0
    "B"  # number of characters
    "B"  # map entry bytes
)


def map_to_bytes(i, nchars, mapping):
    bits_per_value = math.ceil(math.log(nchars, 2))
    bits_per_key = i

    bits = 0
    # ensure that the smallest value is encoded last
    for key, value in sorted(mapping.items(), reverse=True):
        assert key.bit_length() <= bits_per_key
        assert value.bit_length() <= bits_per_value

        bits <<= bits_per_value
        bits |= value
        bits <<= bits_per_key
        bits |= key

    return bits.to_bytes(math.ceil(bits.bit_length() / 8), "big")


def bytes_to_map(i, nchars, data):
    data = int.from_bytes(data, "big")

    bits_per_value = math.ceil(math.log(nchars, 2))
    bits_per_key = i
    key_mask = 2**(bits_per_key)-1
    value_mask = 2**(bits_per_value)-1

    mapping = {}
    while data:
        key = data & key_mask
        data >>= bits_per_key
        value = data & value_mask
        data >>= bits_per_value
        assert key not in mapping
        mapping[key] = value

    return mapping


parts = bytearray()
for first_char, (i, k, j, chars, mapping) in sorted(compressed_maps.items()):
    raw_data = map_to_bytes(i, len(chars), mapping)
    recovered_mapping = bytes_to_map(i, len(chars), raw_data)
    assert recovered_mapping == mapping, "{}\n{}\n{}\n{} {}".format(
        mapping,
        recovered_mapping,
        raw_data,
        i, len(chars),
    )
    assert len(raw_data) <= 255

    print(" {!r} => {} {} {} {} {}".format(
        first_char,
        i, k, j,
        len(chars),
        raw_data
    ))

    assert k <= 15
    assert i <= 15

    if i == 0:
        chars = ""

    row = Row.pack(
        ord(first_char),
        (i << 4) | k, j,
        len(chars),
        len(raw_data),
    )
    row += chars.encode("ascii")
    row += raw_data
    parts.extend(row)

parts = bytes(parts)
print(parts)
print(len(parts))
print(len(str(parts)))
print(len(str(zlib.compress(parts, 9))))

Conductor de prueba

#!/usr/bin/python3
import json
import subprocess
import sys

with open("data.json") as f:
    data = json.load(f)

for name, char in data.items():
    stdout = subprocess.check_output(["python3", sys.argv[1], name])
    stdout = stdout.decode().rstrip("\n")
    if char != stdout:
        print("mismatch for {!r}: {!r} != {!r}".format(
            name, char, stdout
        ))
Jonas Schäfer
fuente
0

awk 73 + 2060 bytes

s{while(!(i=index(s,$0)))sub(/.$/,"");print substr(s,i+length(),1)}{s=$0}

Los datos fueron preparados para esto:

  "Aleax": "A",            Al A     # first of alphabet truncate to len=1
  "Angel": "A",            An A
  "Arch Priest": "@",      Arch @   # this needs to come
  "Archon": "A",           Archo A  # before this
  "Ashikaga Takauji": "@", Ash @
  "Asmodeus": "&",         Asm &    

(2060 caracteres) es decir. a la cadena única más corta con el carácter de monstruo agregado al nombre y finalmente a esta forma:

AlAAnAArch@ArchoAAsh@Asm&

(debe haber un carácter alternativo al comienzo de la cadena para marcar una no coincidencia) Al buscar una coincidencia, el nombre se abreviará char por el carácter desde el final hasta que haya una coincidencia y se devuelva el siguiente carácter después de la coincidencia :

$ cat monster
Aleax
$ awk -f program.awk monsters_string monster
A

Todavía puedo eliminar algunos bytes de la cadena de monstruos con algo de organización:

AAnArch@ArchoAsh@Asm&

Teniendo en cuenta que el tamaño de los datos con nombres de monstruos comenzando Ase reduciría de 38 bytes a 22 significa reducir el tamaño de los datos de 2060 a 1193 en promedio.

esto todavía está en progreso y la cadena de monstruos se publicará un poco más tarde.

James Brown
fuente