35
\$\begingroup\$

Background

The computer game NetHack dates from 1987, before the use of graphics in computer games was widely established. There are lots of monsters in the game, and potentially a lot need to fit on screen at once, so monsters are drawn in a very minimal way: a monster is simply drawn as an ASCII character on screen.

In addition to there being lots of monsters, there are lots of types of monster. It can be important to know which is which; you'd have to react differently upon seeing a kitten and seeing a dragon. As such, most of ASCII is used to represent monsters; for example, a kitten is f, and a red dragon is D. This means that it can be very helpful to know what a given monster will look like, as it will help you to recognise it if you encounter it later on in the game. (Note that there are more types of monsters than there are ASCII characters, so some of them share; a red dragon and a blue dragon are both D.)

Task

Your program must take the name of a NetHack monster as input, and produce the ASCII character that represents it within the game as output. The program is allowed to assume that the input is in fact the name of a NetHack monster; it may if it wishes crash, produce meaningless results, etc. if the input is invalid.

The following Stack Snippet is a JSON object giving the full mapping of possible inputs to their corresponding outputs:

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

So basically, the task here is "given a key in the dictionary represented by the JSON object above, return the corresponding value".

Note that this challenge is, in a way, a reverse ; instead of going from a small/empty input to a large output, you're going from a large input to a small output. (There's thus lots of redundant information in the input, which you can ignore or make use of as you wish). It's also fairly similar to regex golf, except that a) any language is allowed (not just regex), and b) there are more than two possible outputs. (We've had a few tasks like this before, such as these two, but this task is somewhat different because the specified input/output behaviour has stronger patterns).

Clarifications

You can use any reasonable input and output format (e.g. you can produce the output as a character, or as its ASCII code, or as a string that's one character long). You can submit a function instead of a full program, if you prefer.

This is already mentioned in the standard loopholes, but just to reiterate: you cannot store the correspondence between input and output anywhere other than your program's source code. This challenge is basically about representing the input/output behaviour in the smallest space possible, so you must not do things like downloading a list from the Internet, store the correspondence in an external file, start NetHack in debug mode and spawn the monster in question to see what it looks like, etc.. (Besides, I don't want to have to fight off monsters to test your submissions.)

Victory condition

This is , so the winning entry will be the entry that is shortest, counted in bytes. Good luck!

\$\endgroup\$
  • 6
    \$\begingroup\$ mail daemon >_< \$\endgroup\$ – briantist Jan 2 '17 at 2:40
  • 1
    \$\begingroup\$ Suggestion: maybe you can also arrange the list of monsters in order according to the ASCII symbol they represent \$\endgroup\$ – Kritixi Lithos Jan 2 '17 at 11:59
  • 2
    \$\begingroup\$ Sigh - that was such a good game, those were the days... \$\endgroup\$ – GreenAsJade Jan 2 '17 at 13:16
  • 2
    \$\begingroup\$ @GreenAsJade is still is such a good game! In fact a new version was released a few months ago after a few years of inactivity \$\endgroup\$ – nmjcman101 Jan 3 '17 at 14:11
  • 1
    \$\begingroup\$ A wild BROWN PUDDING has appeared!! \$\endgroup\$ – Magic Octopus Urn Jan 3 '17 at 18:10
11
\$\begingroup\$

Jelly, 309 bytes in Jelly's encoding

“Æ÷“¥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”@;Ṫ

Try it online!

I decided it was about time I had a go at my own challenge. The use of Jelly (and its 8-bit codepage) gives me a 12.5% advantage over the ASCII-only languages, and Jelly is convenient for this challenge due to having built-in base conversion operators with short names, but most of the savings are due to a better compression algorithm (this program averages less than one byte per type of monster).

Algorithm and explanation

Word-based classification

I decided that in order to get a good score, it was necessary to take more advantage of the structure of the input than other entries were. One thing that's very noticeable is that many monsters have names of the form "adjective species"; a red dragon and a blue dragon are both types of dragon, and thus appear as D. Some other monsters have names of the form "species job", such as the orc shaman; being a type of orc, this appears as o. Complicating matters are the undead; a kobold zombie is both a kobold and a zombie, and the latter state takes precedence in NetHack monster naming, thus we'd want to classify this as Z.

As such, I classified the words that appear in monster names as follows: an indicator is a word that strongly suggests the appropriate monster class (e.g. sphere strongly suggests that the monster is in class e); an ambiguous word is a word that makes much less of a suggestion (lord doesn't tell you much), and all other words are nonwords that we don't care about. The basic idea is that we look at the words in the monster name from the end backwards to the start, and pick the first indicator that we see. As such, it was necessary to ensure that each monster name contained at least one indicator, which was followed entirely by ambiguous words. As an exception, words that appear in the names of monsters that look like an @ (the largest group) are all classified as ambiguous. Anything can appear before an indicator; for example, color names (such as red) always appear earlier in a name than an indicator does, and thus are considered nonwords (as they're never examined while determining a monster's identity).

In the end, this program comes down to a hash table, like the other programs do. However, the table doesn't contain entries for all monster names, or for all words that appear in monster names; rather, it contains only the indicators. The hashes of ambiguous words do not appear in the table, but must be assigned to empty slots (attempting to look up an ambiguous word will always come up empty). For nonwords, it doesn't matter whether the word appears in the table or not, or whether the hash collides or not, because we never use the value of looking up a nonword. (The table is fairly sparse, so most nonwords don't appear in the table, but a few, such as flesh, are found in the table as a consequence of hash collisions.)

Here's some examples of how this part of the program works:

  • woodchuck is a single word long (thus an indicator), and the table lookup on woodchuck gives us the intended answer r.
  • abbot is also a single word long, but looks like an @. As such, abbot is considered an ambiguous word; the table lookup comes up empty, and we return an answer of @ by default.
  • vampire lord consists of an indicator (vampire corresponding to V) and an ambiguous word (lord, which is not in the table). This means that we check both words (in reverse order), then give the correct answer of V.
  • gelatinous cube consists of a nonword (gelatinous, corresponding to H due to a hash collision) and an indicator (cube, corresponding to b). As we only take the last word that's found in the table, this returns b, as expected.
  • gnome mummy consists of two indicators, gnome corresponding to G and mummy corresponding to M. We take the last indicator, and get M, which is what we want.

The code for handling the word-based classification is the last line of the Jelly program. Here's how it works:

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

There are two real cases; if the input consists entirely of ambiguous words, t0 deletes the entire output of the table lookups and we get an @ outcome by default; if there are indicators in the input, t0 will delete anything to the right of the rightmost indicator, and will give us the corresponding result for that indicator.

Table compression

Of course, breaking the input into words doesn't solve the problem by itself; we still have to encode the correspondence between indicators and the corresponding monster classes (and the lack of correspondence from ambiguous words). To do this, I constructed a sparse table with 181 entries used (corresponding to the 181 indicators; this is a big improvement over the 378 monsters!), and 966 total entries (corresponding to the 966 output values of the hash function). The table is encoded in he program via the use of two strings: the first string specifies the sizes of the "gaps" in the table (which contain no entries); and the second string specifies the monster class which corresponds to each entry. These are both represented in a concise way via base conversion.

In the Jelly program, the code for the table lookup, together with the program itself, is represented in the second line, from the first µ onwards. Here's how this part of the program works:

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

Bijective base 21 is like base 21, except that 21 is a legal digit and 0 isn't. This is a more convenient encoding for us because we count two adjacent entries as having a gap of 1, so that we can find the valid indexes via cumulative sum. When it comes to the part of the table that holds the values, we have 58 unique values, so we first decode into 58 consecutive integers, and then decode again using a lookup table that maps these into the actual characters being used. (Most of these are letters, so we start this secondary lookup table with the non-letter entries, &;:' , and then just append a Jelly constant that starts with the uppercase and lowercase alphabets; it also has some other junk but we don't care about that.)

Jelly's "index not found" sentinel value, if you use it to index into a list, returns the last element of the list; thus, I appended a zero (an integer zero, even though the table's mostly made of characters) to the lookup table to give a more appropriate sentinel to indicate a missing entry.

Hash function

The remaining part of the program is the hash function. This starts out simply enough, with OḌ; this converts the input string into its ASCII codes, and then calculates the last code, plus 10 times the penultimate code, plus 100 times the code before, and so on (this has a very short representation in Jelly because it's more commonly used as a string→integer conversion function). However, if we simply reduced this hash directly via a modulus operation, we'd end up needing a rather large table. So instead, I start off with a chain of operations to reduce the table. They each work like this: we take the fifth power of the current hash value; then we reduce the value modulo a constant (which constant depends on which operation we're using). This chain gives more savings (in terms of reducing the resulting table size) than it costs (in terms of needing to encode the chain of operations itself), in two ways: it can make the table much smaller (966 rather than 3529 entries), and the use of multiple stages gives more opportunity to introduce beneficial collisions (this didn't happen much, but there is one such collision: both Death and Yeenoghu hash to 806, thus allowing us to remove one entry from the table, as they both go to &). The moduli that are used here are [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Incidentally, the reason for raising to the fifth power is that if you just take the value directly, the gaps tend to stay the same size, whereas exponentiation moves the gaps around and can make it possible for the table to become distributed more evenly after the chain rather than getting stuck in a local minimum (more evenly distributed gaps allow for a terser encoding of the gap sizes). This has to be an odd power in order to prevent the fact that x²=(-x)² introducing collisions, and 5 worked better than 3.

The first line of the program encodes the sequence of moduli using delta encoding:

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

The remainder of the program, the start of the second line, implements the hash function:

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

Verification

This is the Perl script I used to verify that the program works correctly:

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";
}
\$\endgroup\$
10
\$\begingroup\$

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)

Formatted

Below is a formatted version of the code with truncated payload data.

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
)

How it works

Step #1

We first reduce the monster name by:

  1. Replacing non-alphanumerical characters (spaces and dashes) with 1's.
  2. Repeating this string 3 times to make sure that we have enough characters to work with for the next step.
  3. Keeping only the 1st, 3rd, 4th, 7th and last characters.

Examples:

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

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

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

This leads to a few collisions. For instance, "Master Assassin" and "Master Kaen" are both reduced to "Mst1n". Fortunately, all colliding monster names share the same symbol (@ in this case).

Step #2

Then, we interpret this 5-character string as a base 36 quantity to convert it to decimal (this operation is case insensitive) and we apply a modulo 8713, which was empirically chosen to produce a collision-free list of keys.

Examples:

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

Step #3

All keys are sorted in ascending order:

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

Converted to delta values:

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

And encoded as ASCII characters in the range [ 32, 126 ]. Some intermediate dummy values are inserted when the difference between two consecutive keys exceeds the maximum encodable magnitude.

Finally, the list of keys is mapped to a list of symbols arranged in the same order.

Test

f=
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)

list = {
  "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"
};

success = error = 0;

for(w in list) {
  list[w] == f(w) ? success++ : error++;
}
console.log("Success:", success);
console.log("Error:", error);

\$\endgroup\$
  • \$\begingroup\$ According to your own testsuite, this misclassifies 5 entries. I haven't investigated to see what's causing them, but that probably needs fixing. \$\endgroup\$ – user62131 Jan 3 '17 at 0:48
  • \$\begingroup\$ @ais523 That's what I get for having tested in Firefox only. I will try to fix that for (at least) Chrome. \$\endgroup\$ – Arnauld Jan 3 '17 at 0:58
  • 2
    \$\begingroup\$ @ais523 That should now work fine on FF, Chrome & Edge. Sorry about that. \$\endgroup\$ – Arnauld Jan 3 '17 at 1:12
  • \$\begingroup\$ I had the idea of extracting bits from the names converted to numbers, but I that was obviously thinking too small. Congrats! \$\endgroup\$ – Jonas Schäfer Jan 3 '17 at 15:17
8
\$\begingroup\$

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

Monster names are:

  • hashed using Java hashcode method => 32 bits
  • ANDed with mask 1001001000111111111100 => 13 bits
  • sorted from smallest to biggest
  • we then use the delta values of the sorted list => 8 bits

The display character is encoded on 6 bits.

So each tuple (monster name, character) uses 14 bits. All the tuples are saved in a BitSet and base 64 encoded.

I lose a lot of bytes with base64 encoding and BitSet operations :-)

\$\endgroup\$
  • \$\begingroup\$ You can reduce the size by making it lambda expression: ()->{...}. The question says so in its "clarifications" section. \$\endgroup\$ – Olivier Grégoire Jan 2 '17 at 21:44
5
\$\begingroup\$

Mathematica, 1067 bytes (Mac OS Roman character encoding)

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

Unnamed function taking a string as input and returning a character. The function has the following form:

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

Here GIANT_STRING_1 is a string containing 608 one-byte characters in the Mac OS Roman character encoding (none of which are in the range 00-1F), while GIANT_STRING_2 is a string containing 304 ASCII characters.

Line 2 starts the hash function: it converts the input string into a list of character codes (encoding irrelevant since they're all printable ASCII), then computes the sum of those character codes and the sum of their squares, both modulo 216 and forcing the answer to lie between 32 and 255. Then lines 1 and 3 convert those ordered pairs of integers into two-character strings, which is the hash value we ultimately use.

Line 5 turns GIANT_STRING_1 into a list of 304 two-character strings; line 6 turns GIANT_STRING_2 into a list of 304 one-character strings. Then lines 4 and 5 convert those two lists into a set of 304 replacement rules: if you see such-and-such two-character string, turn it into such-and-such one-character string. Finally, line 8 turns any remaining two-character string into "@".

There are 71 monsters in the list whose symbol is "@", and those are handled without hashing (I stole this idea from a comment by ais523 on another answer). It just so happens that the other 304 hash values are all unique! and so no other modifications to the algorithm are needed. (It's a lucky break that "human" needs to be mapped to "@", since the sums of the character codes of the letters in "human" and the letters in "shark" are identical, as are the sums of the squares of those codes—as integers, not even modulo 216!)

\$\endgroup\$
3
\$\begingroup\$

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

Here's my test harness, in case it helps anyone else.

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

I wrote a little program to enumerate all the various ways of extracting 4 characters plus the length of the string. My original plan had been to then ord() these characters, do some math on them, and boil it down to a perfect hash function that produced indices into a table of outputs. So I wrote another little program to enumerate all the various ways of summing/multiplying/modulo'ing these 4 characters together; but the resulting hash functions kept having way too many collisions. So eventually I gave up and just did what you see here, which is just a map from the small-string representation of each monster's name to the appropriate symbol.

That is: What I wanted to get was

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

but I only managed to get as far as

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

where my dict lookup {relatively_large_dict}[small_string] is expressed as re.match(small_string+"(.)", "relatively_large_string") for golfiness.

\$\endgroup\$
2
\$\begingroup\$

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

Less golfed

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

Test

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)

\$\endgroup\$
2
\$\begingroup\$

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

Uses a golfed version of the Javascript string hash found here. The actual hash stored in the table (that long string) takes the absolute value of the hash produced by that method, converts it to base-36, and drops all but the three least significant digits.

\$\endgroup\$
  • 1
    \$\begingroup\$ So as far as I can tell, you're hashing by {first character, last character, length}, then using a large lookup table? That makes sense, but I think there are a couple of improvements you could make: there are some duplicate entries in the table, and you could save quite a lot of space by removing the entries for @ from the table and just defaulting to @ if the input isn't found. \$\endgroup\$ – user62131 Jan 2 '17 at 1:46
  • 2
    \$\begingroup\$ cavewoman and chameleon have the same first char, last char and length, that may be a problem ? \$\endgroup\$ – Arnaud Jan 2 '17 at 4:31
  • 1
    \$\begingroup\$ split("_") can become split backtick _ backtick \$\endgroup\$ – user2428118 Jan 2 '17 at 8:42
  • \$\begingroup\$ @SuperChafouin Fixed. \$\endgroup\$ – SuperJedi224 Jan 2 '17 at 11:39
  • 1
    \$\begingroup\$ @SuperJedi224 There are others : Cyclops and Croesus, baluchitherium and baby long worm, crocodile and centipede, and 24 more \$\endgroup\$ – Arnaud Jan 2 '17 at 11:48
1
\$\begingroup\$

Python 3, 1915 1900 bytes

Changelog:

  • Work with and output ASCII code instead of the character itself (saved 15 bytes)

Pass the monster name as first command line argument, receive the character on 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)

When I read the question, I thought "I need to compress this". The first step was to lowercase all names.

Looking at the data, I felt that somehow using the first letter of the last word should do the trick as a rough first guess on which letters the monster might have. As it turns out, that was a powerful initial guess. The following table is "first character of last word", "number of hits", "monster characters":

 '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

To further improve the spreadout, I modified the key slightly, by XOR-ing the second character of the last word, shifted to bits to the right, into the first character (let us call this construct 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

As you can see, this gives us nine names which can uniquely mapped just with that information. Nice!

Now I needed to find the remaining mapping. For this I started by converting the full (lower-cased) name to an integer:

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

This is simply concatenating together the 7bit ASCII values of the names into a huge integer. We take this modulo 4611686018427387903 (2⁶²-1) for the next steps.

Now I try to find a bitmask which yields an integer which in turn nicely distinguishes the different monster characters. The bit masks consist of evenly spread ones (such as 101010101 or 1000100010001) and are parametrised by the number of bits (i>=1) and the spread (k>=1). In addition, the masks are left-shifted for up to 32*i bits. Those are AND-ed with the integerised name and the resulting integer is used as a key in a mapping. The best (scored by i*number_of_mapping_entries) conflict-free mapping is used.

The integers obtained from AND-ing the mask and the integerised name are shifted back by j bits and stripped of their zeroes (we store i, k and j along with the mapping to be able to reconstruct that), saving a lot of space.

So now we have a two-level mapping: from first_key to the hashmap, and the hashmap maps the full name to the monster char uniquely. We need to store that somehow. Each entry of the top-level mapping looks like this:

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
)

followed by the monster characters and the second level mapping.

The second level mapping is serialised by packing it into a large integer and converting it to bytes. Each value and key is shifted consecutively into the integer, which makes the mapping reconstructible (the number of bits per key/value is inferrable from the number of characters and i, both stored in the row entry).

If an entry has only a single possible monster character to map to, i is zero, number of characters and the mapping are also zero bytes. The character is stored where j would normally be stored.

The full data is 651 bytes in size, serialised as python byte string its 1426 bytes.

The decoding program essentially does it the other way round: first it extracts the first_key and searches in the data for the corresponding entry. Then it calculates the hash of the name and searches through the hashmap for the corresponding entry.

Unobfuscated decoder

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

Analysis tool

This is the tool I made and used to generate the data -- read at your own risk:

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

Test driver

#!/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
        ))
\$\endgroup\$
0
\$\begingroup\$

awk 73 + 2060 bytes

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

The data was prepared to this:

  "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 chars) ie. to shortest unique string with the monster character appended to the name and finally to this form:

AlAAnAArch@ArchoAAsh@Asm&

(there needs to be a fall back char in the beginning of the string to mark a non-match) When searching for a match the name is shortened char by char from the end until there is a match and the next char after match is returned:

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

I can still shave off a few bytes from the monsters string with some organizing:

AAnArch@ArchoAsh@Asm&

Considering the size of the data with monsters names starting with A would reduce from 38 bytes to 22 means dropping data size from 2060 to 1193 on the average.

this is still work in progress and the monster string will be published a bit later.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy