fundo
O jogo de computador NetHack data de 1987, antes de o uso de gráficos em jogos de computador ser amplamente estabelecido. Existem muitos monstros no jogo, e potencialmente muito precisa caber na tela de uma só vez, então os monstros são desenhados de uma maneira muito mínima: um monstro é simplesmente desenhado como um personagem ASCII na tela.
Além de haver muitos monstros, existem muitos tipos de monstros. Pode ser importante saber qual é qual; você teria que reagir de maneira diferente ao ver um gatinho e ver um dragão. Como tal, a maior parte do ASCII é usada para representar monstros; por exemplo, um gatinho é fe um dragão vermelho é D. Isso significa que pode ser muito útil saber como será um determinado monstro, pois ajudará você a reconhecê-lo se o encontrar mais tarde no jogo. (Observe que existem mais tipos de monstros do que caracteres ASCII, então alguns deles compartilham; um dragão vermelho e um dragão azul são ambos D.)
Tarefa
Seu programa deve usar o nome de um monstro NetHack como entrada e produzir o caractere ASCII que o representa dentro do jogo como saída. O programa pode assumir que a entrada é de fato o nome de um monstro do NetHack; pode, se desejar travar, produzir resultados sem sentido etc., se a entrada for inválida.
O seguinte snippet de pilha é um objeto JSON que fornece o mapeamento completo de possíveis entradas para suas saídas correspondentes:
Então, basicamente, a tarefa aqui é "dada uma chave no dicionário representado pelo objeto JSON acima, retorne o valor correspondente".
Observe que esse desafio é, de certa forma, uma complexidade kolmogorov inversa ; em vez de passar de uma entrada pequena / vazia para uma saída grande, você está passando de uma entrada grande para uma saída pequena. (Portanto, existem muitas informações redundantes na entrada, que você pode ignorar ou usar como desejar). Também é bastante semelhante ao regex golf, exceto que a) qualquer idioma é permitido (não apenas regex) eb) há mais de duas saídas possíveis. (Tivemos algumas tarefas como essa antes, como essas duas , mas essa tarefa é um pouco diferente porque o comportamento de entrada / saída especificado possui padrões mais fortes).
Esclarecimentos
Você pode usar qualquer formato razoável de entrada e saída (por exemplo, você pode produzir a saída como um caractere, ou como seu código ASCII, ou como uma string com um caractere). Você pode enviar uma função em vez de um programa completo, se preferir.
Isso já é mencionado nas brechas padrão, mas apenas para reiterar: você não pode armazenar a correspondência entre entrada e saída em outro lugar que não seja o código fonte do seu programa. Esse desafio consiste basicamente em representar o comportamento de entrada / saída no menor espaço possível; portanto, você não deve fazer coisas como baixar uma lista da Internet, armazenar a correspondência em um arquivo externo, iniciar o NetHack no modo de depuração e gerar o monstro em questão. para ver como é, etc. (Além disso, não quero ter que lutar contra monstros para testar seus envios.)
Condição de vitória
Como código é golfe , a entrada vencedora será a mais curta, contada em bytes. Boa sorte!
fonte
mail daemon> _ <Respostas:
Jelly , 309 bytes na codificação de Jelly
Experimente online!
Decidi que estava na hora de tentar meu próprio desafio. O uso do Jelly (e sua página de código de 8 bits) me oferece uma vantagem de 12,5% em relação aos idiomas somente ASCII, e o Jelly é conveniente para esse desafio devido a ter operadores de conversão de base incorporados com nomes abreviados, mas a maior parte da economia são devido a um algoritmo de compactação melhor (esse programa calcula a média de menos de um byte por tipo de monstro).
Algoritmo e explicação
Classificação baseada em palavras
Decidi que, para obter uma boa pontuação, era necessário aproveitar mais a estrutura da entrada do que outras entradas. Uma coisa que é muito perceptível é que muitos monstros têm nomes da forma " espécies adjetivas "; a e a são os dois tipos de dragão e, portanto, aparecem como . Alguns outros monstros têm nomes na forma " trabalho de espécies ", como o ; sendo um tipo de orc, isso aparece como . Assuntos complicadores são os mortos-vivos; a é um kobold e um zumbi, e o último estado tem precedência na nomeação de monstros do NetHack, portanto, queremos classificá-lo como .
red dragonblue dragonDorc shamanokobold zombieZComo tal, classifiquei as palavras que aparecem nos nomes dos monstros da seguinte forma: um indicador é uma palavra que sugere fortemente a classe de monstro apropriada (por exemplo
sphere, sugere fortemente que o monstro está na classee); uma palavra ambígua é uma palavra que sugere muito menos (lordnão lhe diz muito) e todas as outras palavras são não-palavras com as quais não nos importamos. A idéia básica é que observemos as palavras no nome do monstro do início ao fim e escolhemos o primeiro indicador que vemos. Como tal, era necessário garantir que cada nome de monstro contivesse pelo menos um indicador, que fosse seguido inteiramente por palavras ambíguas. Como exceção, palavras que aparecem nos nomes de monstros que parecem um@(o maior grupo) são todos classificados como ambíguos. Tudo pode aparecer antes de um indicador; por exemplo, nomes de cores (comored) sempre aparecem mais cedo em um nome do que um indicador e, portanto, são considerados não-palavras (como nunca são examinados ao determinar a identidade de um monstro).No final, esse programa se resume a uma tabela de hash, como os outros programas. No entanto, a tabela não contém entradas para todos os nomes de monstros ou para todas as palavras que aparecem nos nomes de monstros; pelo contrário, contém apenas os indicadores. Os hashes de palavras ambíguas não aparecem na tabela, mas devem ser atribuídos a slots vazios (a tentativa de procurar uma palavra ambígua sempre aparecerá vazia). Para não-palavras, não importa se a palavra aparece na tabela ou não, ou se o hash colide ou não, porque nunca usamos o valor de procurar uma não-palavra. (A tabela é bastante esparsa, portanto, a maioria das não-palavras não aparece na tabela, mas algumas, como
flesh, são encontradas na tabela como consequência de colisões de hash.)Aqui estão alguns exemplos de como essa parte do programa funciona:
woodchucké uma única palavra longa (portanto, um indicador), e a consulta da tabelawoodchuckfornece a resposta pretendidar.abbottambém tem uma única palavra, mas se parece com um@. Como tal,abboté considerada uma palavra ambígua; a pesquisa da tabela fica vazia e retornamos uma resposta@por padrão.vampire lordconsiste em um indicador (vampirecorrespondente aV) e uma palavra ambígua (lord, que não está na tabela). Isso significa que verificamos as duas palavras (na ordem inversa) e fornecemos a resposta correta deV.gelatinous cubeconsiste em uma não palavra (gelatinouscorrespondente aHdevido a uma colisão de hash) e um indicador (cubecorrespondente ab). Como pegamos apenas a última palavra encontrada na tabela, isso retornabcomo esperado.gnome mummyconsiste em dois indicadores,gnomecorrespondentes aGemummycorrespondentes aM. Tomamos o último indicador e obtemosM, que é o que queremos.O código para lidar com a classificação baseada em palavras é a última linha do programa Jelly. Veja como funciona:
Existem dois casos reais; se a entrada consistir inteiramente de palavras ambíguas,
t0excluirá toda a saída das pesquisas da tabela e obteremos um@resultado por padrão; se houver indicadores na entrada,t0excluirá qualquer coisa à direita do indicador mais à direita eṪnos fornecerá o resultado correspondente para esse indicador.Compressão de mesa
Obviamente, dividir a entrada em palavras não resolve o problema por si só; ainda precisamos codificar a correspondência entre indicadores e as classes de monstros correspondentes (e a falta de correspondência de palavras ambíguas). Para fazer isso, construí uma tabela esparsa com 181 entradas usadas (correspondentes aos 181 indicadores; isso é uma grande melhoria em relação aos 378 monstros!) E 966 entradas totais (correspondentes aos 966 valores de saída da função hash). A tabela é codificada no programa através do uso de duas cadeias: a primeira cadeia especifica os tamanhos das "lacunas" na tabela (que não contêm entradas); e a segunda sequência especifica a classe de monstro que corresponde a cada entrada. Ambos são representados de maneira concisa via conversão de base.
No programa Jelly, o código para a pesquisa da tabela, junto com o próprio programa, é representado na segunda linha, a partir da primeira em
µdiante. Veja como esta parte do programa funciona:A base bijetiva 21 é como a base 21, exceto que 21 é um dígito legal e 0 não. Essa é uma codificação mais conveniente para nós, porque contamos duas entradas adjacentes como tendo um intervalo de 1, para que possamos encontrar os índices válidos por soma cumulativa. Quando se trata da parte da tabela que contém os valores, temos 58 valores exclusivos; portanto, primeiro decodificamos em 58 números inteiros consecutivos e depois decodificamos novamente usando uma tabela de pesquisa que os mapeia nos caracteres reais que estão sendo usados. (A maioria dessas letras são letras, portanto, iniciamos esta tabela de pesquisa secundária com entradas que não são da letra
&;:'e, em seguida, apenas anexamos uma constante Jelly que começa com os alfabetos maiúsculos e minúsculos; também possui alguns outros itens indesejados, mas não nos importamos sobre isso.)O valor sentinela "índice não encontrado" do Jelly, se você o usar para indexar em uma lista, retorna o último elemento da lista; portanto, acrescentei um zero (um número inteiro zero, mesmo que a tabela seja composta principalmente de caracteres) na tabela de pesquisa para fornecer um sentinela mais apropriado para indicar uma entrada ausente.
Função hash
A parte restante do programa é a função hash. Isso começa com bastante simplicidade, com
OḌ; isso converte a string de entrada em seus códigos ASCII e calcula o último código, mais 10 vezes o penúltimo código, mais 100 vezes o código anterior e assim por diante (isso tem uma representação muito curta no Jelly, porque é mais comumente usado como um string → função de conversão de número inteiro). No entanto, se simplesmente reduzíssemos esse hash diretamente por meio de uma operação de módulo, acabaríamos precisando de uma tabela bastante grande. Então, em vez disso, começo com uma cadeia de operações para reduzir a tabela. Cada um deles trabalha assim: tomamos a quinta potência do valor atual do hash; então reduzimos o valor do módulo uma constante (essa constante depende de qual operação estamos usando). Essa cadeia oferece mais economia (em termos de redução do tamanho da tabela resultante) do que custa (em termos de necessidade de codificar a própria cadeia de operações), de duas maneiras: pode fazer a tabelamuito menor (966 em vez de 3529 entradas), e o uso de vários estágios oferece mais oportunidades para introduzir colisões benéficas (isso não aconteceu muito, mas existe uma dessas colisões: ambasDeatheYeenoghuhash a 806, permitindo assim remover uma entrada da tabela, pois ambos vão para&) Os módulos usados aqui são [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Aliás, a razão para aumentar para a quinta potência é que, se você pegar o valor diretamente, as lacunas tendem a permanecer do mesmo tamanho, enquanto a exponenciação move as lacunas e pode permitir que a tabela seja distribuída de maneira mais uniforme após o cadeia em vez de ficar preso no mínimo local (intervalos mais uniformemente distribuídos permitem uma codificação por terser dos tamanhos dos intervalos). Isso deve ter um poder ímpar para evitar que x ² = (- x ) ² introduza colisões, e 5 funcione melhor que 3.A primeira linha do programa codifica a sequência de módulos usando a codificação delta:
O restante do programa, o início da segunda linha, implementa a função hash:
Verificação
Este é o script Perl que usei para verificar se o programa funciona corretamente:
fonte
JavaScript (ES6),
915...902890 bytesFormatado
Abaixo está uma versão formatada do código com dados de carga útil truncados.
Como funciona
Passo 1
Primeiro reduzimos o nome do monstro:
1's.Exemplos:
Isso leva a algumas colisões. Por exemplo,
"Master Assassin"e"Master Kaen"são ambos reduzidos a"Mst1n". Felizmente, todos os nomes de monstros em colisão compartilham o mesmo símbolo (@neste caso).Passo 2
Em seguida, interpretamos essa sequência de 5 caracteres como uma quantidade base 36 para convertê-la em decimal (essa operação não diferencia maiúsculas de minúsculas) e aplicamos um módulo
8713, que foi escolhido empiricamente para produzir uma lista de chaves sem colisão.Exemplos:
Etapa 3
Todas as chaves são classificadas em ordem crescente:
Convertido em valores delta:
E codificado como caracteres ASCII no intervalo
[ 32, 126 ]. Alguns valores fictícios intermediários são inseridos quando a diferença entre duas chaves consecutivas excede a magnitude máxima codificável.Finalmente, a lista de teclas é mapeada para uma lista de símbolos organizados na mesma ordem.
Teste
Mostrar snippet de código
fonte
Java, 1130 bytes
Ungolfed:
Os nomes dos monstros são:
hashcodemétodo Java => 32 bitsO caractere de exibição é codificado em 6 bits.
Portanto, cada tupla (nome do monstro, personagem) usa 14 bits. Todas as tuplas são salvas em um BitSet e codificado na base 64.
Perco muitos bytes com a codificação base64 e operações BitSet :-)
fonte
()->{...}. A questão diz isso na seção "esclarecimentos".Mathematica, 1067 bytes (codificação de caracteres romanos do Mac OS)
Função sem nome, tendo uma string como entrada e retornando um caractere. A função tem o seguinte formato:
Aqui, GIANT_STRING_1 é uma sequência que contém 608 caracteres de um byte na codificação de caracteres romanos do Mac OS (nenhum deles está no intervalo 00-1F), enquanto GIANT_STRING_2 é uma sequência que contém 304 caracteres ASCII.
A linha 2 inicia a função hash: converte a sequência de entrada em uma lista de códigos de caracteres (codificando irrelevantes, pois todos são ASCII imprimíveis) e calcula a soma desses códigos de caracteres e a soma de seus quadrados, tanto no módulo 216 quanto forçando a resposta deve estar entre 32 e 255. Em seguida, as linhas 1 e 3 convertem esses pares ordenados de números inteiros em cadeias de dois caracteres, que é o valor de hash que usamos em última análise.
A linha 5 transforma GIANT_STRING_1 em uma lista de 304 seqüências de dois caracteres; a linha 6 transforma GIANT_STRING_2 em uma lista de 304 cadeias de caracteres de um caractere. As linhas 4 e 5 convertem essas duas listas em um conjunto de 304 regras de substituição: se você vir uma cadeia de dois caracteres, transforme-a em uma cadeia de um caractere. Finalmente, a linha 8 transforma qualquer sequência de dois caracteres restante em
"@".Existem 71 monstros na lista cujo símbolo é
"@"e eles são tratados sem hash (roubei essa idéia de um comentário de ais523 em outra resposta). Acontece que os outros 304 valores de hash são todos únicos! e, portanto, nenhuma outra modificação no algoritmo é necessária. (É um golpe de sorte que"human"precisa ser mapeado"@", pois as somas dos códigos de caracteres das letras"human"e das letras"shark"são idênticas, assim como as somas dos quadrados desses códigos - como números inteiros, nem mesmo no módulo 216!)fonte
Python, 2055 bytes
Aqui está o meu equipamento de teste, caso ajude mais alguém.
Eu escrevi um pequeno programa para enumerar todas as várias maneiras de extrair 4 caracteres mais o comprimento da string. Meu plano original era, então,
ord()esses personagens, fazer algumas contas neles e resumir a uma função hash perfeita que produzia índices em uma tabela de saídas. Então, escrevi outro pequeno programa para enumerar todas as várias maneiras de somar / multiplicar / modular esses 4 caracteres juntos; mas as funções hash resultante mantida tendo maneira muitas colisões. Então, finalmente, desisti e fiz o que você vê aqui, que é apenas um mapa da representação em cadeia de caracteres do nome de cada monstro até o símbolo apropriado.Ou seja: o que eu queria era
mas eu só consegui chegar o mais longe
onde minha pesquisa de ditado
{relatively_large_dict}[small_string]é expressa comore.match(small_string+"(.)", "relatively_large_string")para golfe.fonte
JavaScript (ES6), 1178
Menos golfe
Teste
fonte
Javascript, 1185 bytes
Usa uma versão em golf do hash de string Javascript encontrado aqui. O hash real armazenado na tabela (essa cadeia longa) pega o valor absoluto do hash produzido por esse método, o converte em base-36 e elimina todos, exceto os três dígitos menos significativos.
fonte
@da tabela e apenas padronizando@se a entrada não foi encontrado.cavewomanechameleontem o mesmo primeiro caractere, último caractere e comprimento, que pode ser um problema?split("_")pode se tornarsplitbacktick_backtickCyclopseCroesus,baluchitheriumebaby long worm,crocodileecentipede, e 24 maisPython 3,
19151900 bytesChangelog:
Passe o nome do monstro como o primeiro argumento da linha de comando e receba o personagem em stdout.
Quando li a pergunta, pensei "Preciso compactar isso". O primeiro passo foi minúscula em todos os nomes.
Olhando para os dados, senti que, de alguma forma, usar a primeira letra da última palavra deveria funcionar como um primeiro palpite inicial sobre quais letras o monstro poderia ter. Como se viu, esse foi um palpite inicial poderoso. A tabela a seguir é "primeiro caractere da última palavra", "número de ocorrências", "caracteres do monstro":
Para melhorar ainda mais a dispersão, modifiquei a chave levemente, inserindo o XOR no segundo caractere da última palavra, deslocado para bits à direita, no primeiro caractere (vamos chamar essa construção
first_key):Como você pode ver, isso nos dá nove nomes que podem ser mapeados exclusivamente com essas informações. Agradável!
Agora eu precisava encontrar o mapeamento restante. Para isso, comecei convertendo o nome completo (minúsculas) para um número inteiro:
Isso simplesmente concatena os valores ASCII de 7 bits dos nomes em um número inteiro enorme. Tomamos este módulo
4611686018427387903(2⁶²-1) para os próximos passos.Agora, tento encontrar uma máscara de bits que produza um número inteiro que, por sua vez, distingue bem os diferentes personagens de monstros. As máscaras de bits consistem em máscaras distribuídas uniformemente (como
101010101ou1000100010001) e são parametrizadas pelo número de bits (i>=1) e pela propagação (k>=1). Além disso, as máscaras são deslocadas para a esquerda por até32*ibits. Esses são AND-ed com o nome inteiro e o número inteiro resultante é usado como uma chave em um mapeamento. O melhor (marcado pori*number_of_mapping_entries) mapeamento sem conflito é usado.Os inteiros obtidos a partir de E-ing a máscara eo nome integerised são deslocados de volta por
jpedaços e despojado de seus zeros (armazenamosi,kejjuntamente com o mapeamento para ser capaz de reconstruir esse), economizando um monte de espaço.Portanto, agora temos um mapeamento em dois níveis: de
first_keypara o mapa de hash, e o mapa de hash mapeia o nome completo para o monstro char exclusivamente. Precisamos armazenar isso de alguma forma. Cada entrada do mapeamento de nível superior tem a seguinte aparência:seguido pelos personagens monstros e pelo mapeamento de segundo nível.
O mapeamento de segundo nível é serializado, compactando-o em um número inteiro grande e convertendo-o em bytes. Cada valor e chave é alternado consecutivamente para o número inteiro, o que torna o mapeamento reconstrutível (o número de bits por chave / valor é inferível a partir do número de caracteres e
i, ambos armazenados na entrada da linha).Se uma entrada tiver apenas um único caractere de monstro possível para mapear,
ié zero, o número de caracteres e o mapeamento também serão zero bytes. O personagem é armazenado ondejnormalmente seria armazenado.Os dados completos têm 651 bytes de tamanho, serializados como bytes de python e 1426 bytes.
O programa de decodificação basicamente faz o contrário: primeiro extrai
first_keye pesquisa nos dados pela entrada correspondente. Em seguida, calcula o hash do nome e pesquisa no mapa de hash a entrada correspondente.Decodificador não ofuscado
Ferramenta de análise
Esta é a ferramenta que eu criei e usei para gerar os dados - leia por sua conta e risco:
Driver de teste
fonte
awk 73 + 2060 bytes
Os dados foram preparados para isso:
(2060 caracteres) ou seja. à menor string exclusiva com o caractere de monstro anexado ao nome e, finalmente, a este formulário:
(é necessário que haja um caractere de retorno no início da sequência para marcar uma não correspondência). Ao procurar uma correspondência, o nome é reduzido por caractere por caractere do final até que haja uma correspondência e o próximo caractere após a correspondência ser retornada. :
Ainda posso raspar alguns bytes da cadeia de monstros com alguma organização:
Considerando o tamanho dos dados com nomes de monstros começando com
A, reduziria de 38 bytes para 22 significa diminuir o tamanho dos dados de 2060 para 1193, em média.isso ainda está em andamento e a sequência de monstros será publicada um pouco mais tarde.
fonte