Ajude-me a reconhecer meu monstro

35

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 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 é , a entrada vencedora será a mais curta, contada em bytes. Boa sorte!

Peter Taylor
fonte
6
mail daemon> _ <
briantist
11
Sugestão: talvez você também possa organizar a lista de monstros em ordem, de acordo com o símbolo ASCII que eles representam
Kritixi Lithos 2/17/17
2
Suspiro - que era um jogo tão bom, aqueles eram os dias ...
GreenAsJade
2
@GreenAsJade ainda é um jogo tão bom! De fato, uma nova versão foi lançada há alguns meses depois de alguns anos de inatividade
nmjcman101
11
Um PUDIM MARROM selvagem apareceu !!
Magic Octopus Urn

Respostas:

11

Jelly , 309 bytes na codificação 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”@;Ṫ

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 dragonD orc shamanokobold zombieZ

Como 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 classe e); 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 (como red) 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 tabela woodchuckfornece a resposta pretendida r.
  • 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 a V) 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 de V.
  • gelatinous cubeconsiste em uma não palavra ( gelatinouscorrespondente a Hdevido a uma colisão de hash) e um indicador ( cubecorrespondente a b). Como pegamos apenas a última palavra encontrada na tabela, isso retorna bcomo esperado.
  • gnome mummyconsiste em dois indicadores, gnomecorrespondentes a Ge mummycorrespondentes a M. Tomamos o último indicador e obtemos M, 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:

ḲÇ€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

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:

“…’ḃ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

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, comOḌ; 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: ambas Deathe Yeenoghuhash 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:

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

O restante do programa, o início da segunda linha, implementa a função 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).

Verificação

Este é o script Perl que usei para verificar se o programa funciona corretamente:

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";
}

fonte
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)

Formatado

Abaixo está uma versão formatada do código com dados 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
)

Como funciona

Passo 1

Primeiro reduzimos o nome do monstro:

  1. Substituindo caracteres não alfanuméricos (espaços e hífens) por 1's.
  2. Repita essa sequência três vezes para garantir que tenhamos caracteres suficientes para trabalhar na próxima etapa.
  3. Mantendo apenas o 1º, 3º, 4º, 7º e último caracteres.

Exemplos:

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

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

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

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:

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

Etapa 3

Todas as chaves são classificadas em ordem crescente:

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

Convertido em valores delta:

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

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

Arnauld
fonte
De acordo com o seu próprio testinguite, isso classifica incorretamente 5 entradas. Eu não investiguei para ver o que os está causando, mas isso provavelmente precisa ser consertado.
@ ais523 É o que recebo por ter testado apenas no Firefox. Vou tentar corrigir isso para (pelo menos) o Chrome.
Arnauld
2
@ ais523 Agora, isso deve funcionar bem no FF, Chrome & Edge. Me desculpe por isso.
Arnauld
Eu tive a idéia de extrair bits dos nomes convertidos em números, mas eu que obviamente estava pensando muito pequeno. Parabéns!
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);}}

Ungolfed:

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);
    }
}

Os nomes dos monstros são:

  • hash usando o hashcodemétodo Java => 32 bits
  • ANDed com máscara 1001001000111111111100 => 13 bits
  • classificados do menor para o maior
  • então usamos os valores delta da lista classificada => 8 bits

O 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 :-)

Arnaud
fonte
Você pode reduzir o tamanho, tornando-lambda expressão: ()->{...}. A questão diz isso na seção "esclarecimentos".
Olivier Grégoire
5

Mathematica, 1067 bytes (codificação de caracteres romanos do 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->"@"&

Função sem nome, tendo uma string como entrada e retornando um caractere. A função tem o seguinte formato:

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 -> "@" &

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!)

Greg Martin
fonte
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'@'

Aqui está o meu equipamento de teste, caso ajude mais alguém.

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!'

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

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

mas eu só consegui chegar o mais longe

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

onde minha pesquisa de ditado {relatively_large_dict}[small_string]é expressa como re.match(small_string+"(.)", "relatively_large_string")para golfe.

Quuxplusone
fonte
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 golfe

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

Teste

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
fonte
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"@"}

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.

SuperJedi224
fonte
11
Até onde eu sei, você usa hash {primeiro caractere, último caractere, comprimento} e usa uma grande tabela de pesquisa? Isso faz sentido, mas acho que há algumas melhorias que você pode fazer: existem algumas entradas duplicadas na tabela e você pode economizar bastante espaço removendo as entradas @da tabela e apenas padronizando @se a entrada não foi encontrado.
2
cavewomane chameleontem o mesmo primeiro caractere, último caractere e comprimento, que pode ser um problema?
Arnaud
11
split("_")pode se tornar split backtick _ backtick
user2428118 2/17/17
@SuperChafouin Fixed.
precisa saber é o seguinte
11
@ SuperJedi224 Há outros: Cyclopse Croesus, baluchitheriume baby long worm, crocodilee centipede, e 24 mais
Arnaud
1

Python 3, 1915 1900 bytes

Changelog:

  • Trabalhar com e gerar código ASCII em vez do próprio caractere (salvo 15 bytes)

Passe o nome do monstro como o primeiro argumento da linha de comando e receba o personagem em 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)

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":

 '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 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):

 '}' (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 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:

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

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 101010101ou 1000100010001) 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 por i*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 (armazenamos i, ke jjuntamente 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:

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 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 onde jnormalmente 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

#!/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))

Ferramenta de análise

Esta é a ferramenta que eu criei e usei para gerar os dados - leia por sua conta e risco:

#!/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))))

Driver de teste

#!/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
fonte
0

awk 73 + 2060 bytes

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

Os dados foram preparados para isso:

  "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) ou seja. à menor string exclusiva com o caractere de monstro anexado ao nome e, finalmente, a este formulário:

AlAAnAArch@ArchoAAsh@Asm&

(é 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. :

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

Ainda posso raspar alguns bytes da cadeia de monstros com alguma organização:

AAnArch@ArchoAsh@Asm&

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.

James Brown
fonte