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 complejidad kolmogorov 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 código de golf , por lo que la entrada ganadora será la entrada más corta, contada en bytes. ¡Buena suerte!
fuente
mail daemon> _ <Respuestas:
Jelly , 309 bytes en la codificación de Jelly
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 dragonDorc shamanokobold zombieZComo 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 clasee); 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 (comored) 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 tablawoodchucknos da la respuesta deseadar.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 aV) y una palabra ambigua (lordque no está en la tabla). Esto significa que verificamos ambas palabras (en orden inverso), luego damos la respuesta correcta deV.gelatinous cubeconsiste en una no palabra (gelatinouscorrespondiente aHdebido a una colisión hash) y un indicador (cubecorrespondiente ab). Como solo tomamos la última palabra que se encuentra en la tabla, esto regresab, como se esperaba.gnome mummyconsta de dos indicadores,gnomecorrespondientesGymummycorrespondientes aM. Tomamos el último indicador y obtenemosM, 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:
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: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, con
OḌ; 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: ambasDeathyYeenoghuhash 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:
El resto del programa, el inicio de la segunda línea, implementa la función hash:
Verificación
Este es el script de Perl que utilicé para verificar que el programa funciona correctamente:
fuente
JavaScript (ES6),
915...902890 bytesFormateado
A continuación se muestra una versión formateada del código con datos de carga útil truncados.
Cómo funciona
Paso 1
Primero reducimos el nombre del monstruo por:
1's.Ejemplos:
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:
Paso 3
Todas las claves están ordenadas en orden ascendente:
Convertido a valores delta:
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
Mostrar fragmento de código
fuente
Java, 1130 bytes
Sin golf:
Los nombres de los monstruos son:
hashcodemétodo Java => 32 bitsEl 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 :-)
fuente
()->{...}. La pregunta lo dice en su sección de "aclaraciones".Mathematica, 1067 bytes (codificación de caracteres romanos de Mac OS)
Función sin nombre que toma una cadena como entrada y devuelve un carácter. La función tiene la siguiente forma:
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!)fuente
Python, 2055 bytes
Aquí está mi arnés de prueba, en caso de que ayude a alguien más.
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 entonces
ord()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
pero solo logré llegar tan lejos
donde mi búsqueda dict
{relatively_large_dict}[small_string]se expresa en cuantore.match(small_string+"(.)", "relatively_large_string")a golfiness.fuente
JavaScript (ES6), 1178
Menos golf
Prueba
fuente
Javascript, 1185 bytes
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.
fuente
@de la tabla y simplemente omitiendo@si la entrada no se encuentracavewomanychameleontener el mismo primer carácter, último carácter y longitud, ¿puede ser un problema?split("_")puede llegar a sersplittilde_tildeCyclopsyCroesus,baluchitheriumybaby long worm,crocodileycentipede, y 24 másPython 3,
19151900 bytesRegistro de cambios:
Pase el nombre del monstruo como primer argumento de línea de comando, reciba el personaje en stdout.
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":
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):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:
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
101010101o1000100010001) 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 hasta32*ibits. Esos son AND-ed con el nombre integerizado y el entero resultante se usa como clave en un mapeo. Sei*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 (almacenamosi,kyjjunto 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í: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 y
i, 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 dondejnormalmente 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_keyy busca en los datos la entrada correspondiente. Luego calcula el hash del nombre y busca en el hashmap la entrada correspondiente.Decodificador no ofuscado
Herramienta de análisis
Esta es la herramienta que creé y utilicé para generar los datos; lea bajo su propio riesgo:
Conductor de prueba
fuente
awk 73 + 2060 bytes
Los datos fueron preparados para esto:
(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:
(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 :
Todavía puedo eliminar algunos bytes de la cadena de monstruos con algo de organización:
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.
fuente