Помоги мне узнать моего монстра

35

Задний план

Компьютерная игра NetHack датируется 1987 годом, до того, как было широко распространено использование графики в компьютерных играх. В игре много монстров, и потенциально много нужно разместить сразу на экране, поэтому монстры нарисованы очень минимальным образом: монстр просто рисуется как ASCII-персонаж на экране.

В дополнение к тому, что есть много монстров, есть много типов монстров. Может быть важно знать, что есть что; вам придется реагировать иначе, увидев котенка и дракона. Таким образом, большая часть ASCII используется для представления монстров; например, котенок есть f, а красный дракон есть D. Это означает, что может быть очень полезно знать, как будет выглядеть данный монстр, поскольку это поможет вам распознать его, если вы столкнетесь с ним позже в игре. (Обратите внимание, что типов монстров больше, чем персонажей ASCII, поэтому некоторые из них имеют общие свойства: красный дракон и синий дракон оба D.)

задача

Ваша программа должна взять имя монстра NetHack в качестве входных данных и создать символ ASCII, который представляет его в игре в качестве выходных данных. Программа может предполагать, что на самом деле это имя монстра NetHack; это может, если он желает сбой, привести к бессмысленным результатам и т. д., если ввод неверен.

Следующий фрагмент стека представляет собой объект JSON, дающий полное сопоставление возможных входов и их соответствующих выходов:

Показать фрагмент кода

Таким образом, в основном, задача здесь «дать ключ в словаре, представленном объектом JSON выше, вернуть соответствующее значение».

Обратите внимание, что эта проблема, в некотором смысле, обратная колмогоровская сложность ; вместо перехода от маленького / пустого ввода к большому выводу вы переходите от большого ввода к маленькому выводу. (Таким образом, на входе много избыточной информации, которую вы можете игнорировать или использовать по своему усмотрению). Это также довольно похоже на регулярное выражение для гольфа, за исключением того, что а) разрешен любой язык (не только регулярное выражение), и б) существует более двух возможных выходных данных. (У нас было несколько подобных задач, таких как эти две , но эта задача несколько отличается, потому что указанное поведение ввода / вывода имеет более строгие шаблоны).

Разъяснения

Вы можете использовать любой приемлемый формат ввода и вывода (например, вы можете создать вывод в виде символа, или в виде его кода ASCII, или в виде строки длиной один символ). Вы можете отправить функцию вместо полной программы, если хотите.

Это уже упоминалось в стандартных лазейках, но только для повторения: вы не можете хранить соответствие между вводом и выводом нигде, кроме исходного кода вашей программы. Эта задача в основном заключается в представлении поведения ввода / вывода в наименьшем возможном пространстве, поэтому вы не должны делать такие вещи, как загрузка списка из Интернета, сохранение корреспонденции во внешнем файле, запуск NetHack в режиме отладки и порождение соответствующего монстра. чтобы посмотреть, как это выглядит, и т. д. (Кроме того, я не хочу отбиваться от монстров, чтобы проверить ваши представления.)

Состояние победы

Это код-гольф , поэтому выигрышной записью будет самая короткая запись, подсчитанная в байтах. Удачи!

code-golf compression classification hashing Питер Тейлор
источник
6
mail daemon> _ <
briantist
1
Предложение: возможно, вы также можете упорядочить список монстров по порядку в соответствии с символом ASCII, который они представляют
Kritixi Lithos
2
Вздох - это была такая хорошая игра, это были дни ...
GreenAsJade
2
@GreenAsJade все еще такая хорошая игра! Фактически, новая версия была выпущена несколько месяцев назад после нескольких лет бездействия
nmjcman101
1
Дикий коричневый пудинг появился !!
Волшебная Осьминог Урна

Ответы:

11

Jelly , 309 байт в кодировке 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”@;Ṫ

Попробуйте онлайн!

Я решил, что пришло время попробовать свои силы. Использование Jelly (и его 8-битной кодовой страницы) дает мне преимущество в 12,5% по сравнению с языками только для ASCII, и Jelly удобен для этой задачи благодаря наличию встроенных базовых операторов преобразования с короткими именами, но большей части экономии из-за лучшего алгоритма сжатия (эта программа в среднем составляет менее одного байта на тип монстра).

Алгоритм и объяснение

Словесная классификация

Я решил, что для того, чтобы получить хороший результат, необходимо использовать преимущества структуры ввода больше, чем другие записи. Одна вещь, которая очень заметна, - то, что у многих монстров есть названия формы " прилагательное разновидности "; a red dragonи a blue dragonоба типа дракона, и поэтому выглядят как D. У некоторых других монстров есть названия вида " работа вида ", такие как ; будучи типом орка, это выглядит как . Сложные вопросы - это нежить; a является и кобольдом, и зомби, и последнее состояние имеет приоритет в именовании монстров NetHack, поэтому мы хотели бы классифицировать это как .orc shamanokobold zombieZ

Таким образом, я классифицировал слова, которые появляются в именах монстров, следующим образом: индикатор - это слово, которое настоятельно рекомендует соответствующий класс монстров (например, sphereнастоятельно предполагает, что монстр находится в классе e); неоднозначное слово это слово , которое делает гораздо меньше предложения ( lordне сказать вам много), а все остальные слова псевдослов , что мы не заботимся о. Основная идея заключается в том, что мы смотрим на слова в названии монстра от конца к началу и выбираем первый индикатор, который мы видим. Таким образом, необходимо было обеспечить, чтобы каждое имя монстра содержало хотя бы один индикатор, за которым следовали двусмысленные слова. Как исключение, слова, которые появляются в именах монстров, которые выглядят как@(самая большая группа) все классифицируются как неоднозначные. Все может появиться перед индикатором; например, имена цветов (такие как red) всегда появляются в имени раньше, чем индикатор, и, таким образом, считаются не словами (так как они никогда не проверяются при определении личности монстра).

В конце концов, эта программа сводится к хеш-таблице, как и другие программы. Однако таблица не содержит записей для всех имен монстров или для всех слов, которые появляются в именах монстров; скорее он содержит только показатели. Хеши неоднозначных слов не отображаются в таблице, но должны быть назначены пустым слотам (попытка найти неоднозначное слово всегда будет пустой). Для не-слов не имеет значения, появляется ли слово в таблице или нет, или хэш сталкивается или нет, потому что мы никогда не используем значение поиска не-слова. (Таблица довольно разреженная, поэтому большинство слов не появляется в таблице, но некоторые из них, например flesh, найдены в таблице в результате коллизий хешей.)

Вот несколько примеров того, как работает эта часть программы:

  • woodchuckэто длинное слово (таким образом, индикатор), и поиск в таблице woodchuckдает нам ожидаемый ответ r.
  • abbotтакже одно слово долго, но выглядит как @. Как таковое, abbotсчитается неоднозначным словом; поиск по таблице пуст, и мы возвращаем ответ @по умолчанию.
  • vampire lordсостоит из индикатора ( vampireсоответствует V) и неоднозначного слова ( lordкоторого нет в таблице). Это означает, что мы проверяем оба слова (в обратном порядке), а затем даем правильный ответ V.
  • gelatinous cubeсостоит из не-слова ( gelatinousсоответствует Hиз-за коллизии хэшей) и индикатора ( cubeсоответствует b). Поскольку мы берем только последнее слово, найденное в таблице, это возвращает b, как и ожидалось.
  • gnome mummyсостоит из двух показателей, gnomeсоответствующих Gи mummyсоответствующих M. Мы берем последний индикатор и получаем то M, что мы хотим.

Код для обработки классификации на основе слов является последней строкой программы Jelly. Вот как это работает:

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

Есть два реальных случая; если входные данные полностью состоят из неоднозначных слов, t0удаляются все выходные данные поиска в таблице, и мы получаем @результат по умолчанию; если на входе есть индикаторы, t0то удалит что-нибудь справа от крайнего правого индикатора и Ṫвыдаст соответствующий результат для этого индикатора.

Сжатие таблицы

Конечно, разбиение ввода на слова само по себе не решает проблему; нам все еще нужно закодировать соответствие между индикаторами и соответствующими классами монстров (и отсутствие соответствия от неоднозначных слов). Чтобы сделать это, я построил разреженную таблицу с 181 использованными записями (что соответствует 181 индикатору; это большое улучшение по сравнению с 378 монстрами!) И всего 966 записей (что соответствует 966 выходным значениям хэш-функции). Таблица кодируется в программе с использованием двух строк: первая строка указывает размеры «пробелов» в таблице (которые не содержат записей); и вторая строка определяет класс монстров, который соответствует каждой записи. Они оба представлены в сжатой форме через базовое преобразование.

В программе Jelly код поиска по таблице вместе с самой программой представлен во второй строке, начиная с первой µ. Вот как работает эта часть программы:

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

Биективное основание 21 похоже на основание 21, за исключением того, что 21 является допустимой цифрой, а 0 - нет. Для нас это более удобная кодировка, потому что мы считаем, что две соседние записи имеют пробел 1, поэтому мы можем найти действительные индексы с помощью накопленной суммы. Когда дело доходит до той части таблицы, которая содержит значения, у нас есть 58 уникальных значений, поэтому мы сначала декодируем в 58 последовательных целых чисел, а затем снова декодируем, используя таблицу поиска, которая сопоставляет их с реальными используемыми символами. (Большинство из них - буквы, поэтому мы начинаем эту вторичную таблицу поиска с &;:' небуквенных записей, а затем просто добавляем константу Jelly, начинающуюся с прописных и строчных букв; у нее также есть какой-то другой мусор, но нам все равно об этом.)

Стражное значение Jelly «index not found», если вы используете его для индексации списка, возвращает последний элемент списка; таким образом, я добавил ноль (целое ноль, даже если таблица в основном состоит из символов) к таблице поиска, чтобы дать более подходящий сторож, чтобы указать отсутствующую запись.

Хэш-функция

Оставшаяся часть программы - хеш-функция. Это начинается достаточно просто, сOḌ; это преобразует входную строку в ее ASCII-коды, а затем вычисляет последний код, плюс 10-кратный предпоследний код, плюс 100-кратный код до и т. д. (это очень короткое представление в Jelly, потому что оно чаще используется как строка → целочисленная функция преобразования). Однако, если бы мы просто сократили этот хэш напрямую с помощью операции модуля, нам бы понадобилась довольно большая таблица. Поэтому вместо этого я начинаю с цепочки операций по сокращению таблицы. Каждый из них работает следующим образом: мы берем пятую степень текущего хеш-значения; затем мы уменьшаем значение по модулю константы (эта константа зависит от того, какую операцию мы используем). Эта цепочка дает большую экономию (с точки зрения уменьшения размера результирующей таблицы), чем она стоит (с точки зрения необходимости кодирования самой цепочки операций), двумя способами: она может создать таблицугораздо меньше (966, а не 3529 записей), а использование нескольких этапов дает больше возможностей для создания полезных коллизий (такого не было много, но есть одно такое коллизирование: Deathи Yeenoghuхеш, и 806, что позволяет нам удалить один запись из таблицы, так как они оба идут в&). Здесь используются модули [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Между прочим, причина повышения до пятой степени заключается в том, что если вы просто берете значение непосредственно, промежутки, как правило, остаются одинаковыми, тогда как возведение в степень перемещает пробелы вокруг и может позволить распределению таблицы более равномерно распределяться после цепочка, а не застревание в локальном минимуме (более равномерно распределенные промежутки позволяют более сжатое кодирование размеров промежутков). Это должно быть нечетной степенью, чтобы предотвратить тот факт, что x ² = (- x ) ², приводящее к столкновениям, и 5 работал лучше, чем 3.

Первая строка программы кодирует последовательность модулей с использованием дельта-кодирования:

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

Оставшаяся часть программы, начало второй строки, реализует хеш-функцию:

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

верификация

Это скрипт Perl, который я использовал для проверки правильности работы программы:

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

источник
10

JavaScript (ES6), 915 ... 902 890 байт

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)

отформатирован

Ниже приведена отформатированная версия кода с усеченными данными полезной нагрузки.

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
)

Как это работает

Шаг 1

Сначала мы уменьшаем имя монстра на:

  1. Замена не буквенно-цифровых символов (пробелы и тире) на 1's.
  2. Повторите эту строку 3 раза, чтобы убедиться, что у нас достаточно символов для работы на следующем шаге.
  3. Сохранение только 1-го, 3-го, 4-го, 7-го и последнего символов.

Примеры:

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

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

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

Это приводит к нескольким столкновениям. Например, "Master Assassin"и "Master Kaen"оба уменьшены до "Mst1n". К счастью, все имена сталкивающихся монстров имеют один и тот же символ ( @в данном случае).

Шаг 2

Затем мы интерпретируем эту 5-символьную строку как основную 36-ю величину, чтобы преобразовать ее в десятичную (эта операция не учитывает регистр), и применяем модуль 8713, который был выбран эмпирически для создания списка ключей без столкновений.

Примеры:

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

Шаг 3

Все ключи отсортированы в порядке возрастания:

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

Преобразовано в значения дельты:

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

И закодированы как символы ASCII в диапазоне [ 32, 126 ]. Некоторые промежуточные фиктивные значения вставляются, когда разница между двумя последовательными ключами превышает максимальную кодируемую величину.

Наконец, список ключей отображается на список символов, расположенных в том же порядке.

Тест

Показать фрагмент кода

Arnauld
источник
В соответствии с вашим собственным набором тестов, это неправильно классифицирует 5 записей. Я не исследовал, чтобы увидеть, что их вызывает, но это, вероятно, нуждается в исправлении.
@ ais523 Это то, что я получаю за тестирование только в Firefox. Я постараюсь исправить это для (по крайней мере) Chrome.
Арно
2
@ ais523 Теперь это должно работать на FF, Chrome и Edge. Прости за это.
Арно
У меня была идея извлечь биты из имен, преобразованных в числа, но я, очевидно, думал слишком маленьким. Congrats!
Йонас Шефер
8

Java, 1130 байт

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

Имена монстров:

  • хэширование с использованием hashcodeметода Java => 32 бита
  • AND с маской 1001001000111111111100 => 13 бит
  • отсортировано от самого маленького до самого большого
  • Затем мы используем дельта-значения отсортированного списка => 8 бит

Символ дисплея кодируется в 6 битах.

Таким образом, каждый кортеж (имя монстра, персонаж) использует 14 бит. Все кортежи сохраняются в BitSet и кодируются в base 64.

Я теряю много байтов с кодировкой base64 и операциями BitSet :-)

Arnaud
источник
Вы можете уменьшить размер, что делает его лямбда - выражение: ()->{...}. Так говорится в разделе «Разъяснения».
Оливье Грегуар
5

Mathematica, 1067 байт (кодировка символов Mac OS Roman)

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

Безымянная функция, принимающая строку в качестве ввода и возвращающая символ. Функция имеет следующий вид:

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

Здесь GIANT_STRING_1 - это строка, содержащая 608 однобайтовых символов в римской кодировке Mac OS (ни один из которых не находится в диапазоне 00-1F), а GIANT_STRING_2 - это строка, содержащая 304 символа ASCII.

Строка 2 запускает хеш-функцию: она преобразует входную строку в список кодов символов (кодировка не имеет значения, поскольку все они печатаются в формате ASCII), затем вычисляет сумму этих кодов символов и сумму их квадратов, как по модулю 216, так и по форсированию. ответ лежит между 32 и 255. Затем строки 1 и 3 преобразуют эти упорядоченные пары целых чисел в двухсимвольные строки, что является значением хеша, которое мы в конечном итоге используем.

Строка 5 превращает GIANT_STRING_1 в список из 304 двухсимвольных строк; строка 6 превращает GIANT_STRING_2 в список из 304 односимвольных строк. Затем строки 4 и 5 преобразуют эти два списка в набор из 304 правил замещения: если вы видите такую-то двухсимвольную строку, превращайте ее в такую-то такую-односимвольную строку. Наконец, строка 8 превращает любую оставшуюся двухсимвольную строку в "@".

В списке 71 монстр с символом "@", и они обрабатываются без хеширования (я украл эту идею из комментария ais523 к другому ответу). Просто так получилось, что все остальные 304 значения хешей являются уникальными! и поэтому никакие другие модификации алгоритма не требуются. (Это удачный разрыв, который "human"нужно сопоставить "@", поскольку суммы кодов символов букв в "human"и букв в "shark"них идентичны, равно как и суммы квадратов этих кодов - как целые числа, даже не по модулю 216!)

Грег Мартин
источник
3

Питон, 2055 байт

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

Вот мой тестовый комплект, на случай, если он кому-нибудь поможет.

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

Я написал небольшую программу для перечисления всех различных способов извлечения 4 символов плюс длина строки. Мой первоначальный план состоял в том, чтобы затем использовать ord()эти символы, сделать с ними некоторые математические расчеты и свести их к идеальной хэш-функции, которая вывела бы индексы в таблицу результатов. Поэтому я написал еще одну небольшую программу для перечисления всех различных способов суммирования / умножения / модуляции этих четырех символов вместе; но в результате хэш - функция продолжала иметь сторонние слишком много столкновений. Так что в конце концов я сдался и просто сделал то, что вы видите здесь, это просто карта из строкового представления имени каждого монстра к соответствующему символу.

То есть: то, что я хотел получить, было

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

но мне удалось добраться до

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

где мой продиктованный поиск {relatively_large_dict}[small_string]выражен как re.match(small_string+"(.)", "relatively_large_string")для игры в гольф.

Quuxplusone
источник
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

Меньше гольфа

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

Тест 

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
источник
2

Javascript, 1185 байт

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

Использует гольф-версию строкового хэша Javascript, найденную здесь. Фактический хеш, хранящийся в таблице (эта длинная строка), принимает абсолютное значение хеша, созданного этим методом, преобразует его в base-36 и удаляет все, кроме трех наименее значащих цифр.

SuperJedi224
источник
1
Итак, насколько я могу судить, вы хэшируете {первым символом, последним символом, длиной}, а затем используете большую справочную таблицу? Это имеет смысл, но я думаю, что есть несколько улучшений, которые вы могли бы сделать: в таблице есть несколько повторяющихся записей, и вы могли бы сэкономить довольно много места, удалив записи @из таблицы и просто установив значение по умолчанию, @если ввод не найден
2
cavewomanи chameleonиметь тот же первый символ, последний символ и длину, что может быть проблемой?
Арно
1
split("_")может стать split backtick _ backtick
user2428118
@SuperChafouin Исправлено.
SuperJedi224
1
@ SuperJedi224 Есть и другие: Cyclopsи Croesus, baluchitheriumи baby long worm, crocodileи centipede, и еще 24
Арно
1

Питон 3, 1915 г. 1900 байт

Changelog:

  • Работать и выводить код ASCII вместо самого символа (сохранено 15 байт)

Передайте имя монстра в качестве первого аргумента командной строки, получите символ на стандартный вывод.

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)

Когда я прочитал вопрос, я подумал: «Мне нужно это сжать». Первым шагом было сделать строчными все имена.

Глядя на данные, я почувствовал, что каким-то образом использование первой буквы последнего слова должно помочь в качестве приблизительного первого предположения о том, какие буквы могут быть у монстра. Как оказалось, это было мощное первоначальное предположение. В следующей таблице приведены «первый символ последнего слова», «количество попаданий», «символы монстра»:

 '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

Чтобы еще больше улучшить распространение, я немного изменил ключ, добавив XOR второго символа последнего слова, смещенного в биты вправо, в первый символ (назовем эту конструкцию 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

Как видите, это дает нам девять имен, которые могут быть однозначно сопоставлены только с этой информацией. Ницца!

Теперь мне нужно было найти оставшееся отображение. Для этого я начал с преобразования полного (в нижнем регистре) имени в целое число:

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

Это просто объединяет 7-битные значения ASCII-имен в огромное целое число. Мы возьмем это по модулю 4611686018427387903(2⁶²-1) для следующих шагов.

Теперь я пытаюсь найти битовую маску, которая выдает целое число, которое, в свою очередь, хорошо различает различных персонажей монстров. Битовые маски состоят из равномерно распределенных (например, 101010101или 1000100010001) и параметризуются числом битов ( i>=1) и расширением ( k>=1). Кроме того, маски сдвинуты влево на величину до 32*iбитов. Это AND-ed с целочисленным именем, и полученное целое число используется в качестве ключа в отображении. Лучшее (оцененное i*number_of_mapping_entries) бесконфликтное отображение используется.

Целые полученные из И-инги маски и integerised имени сдвинуты назад jбитами и раздели их нули (мы храним i, kи jвместе с отображением , чтобы иметь возможность восстановить это), экономя много места.

Итак, теперь у нас есть двухуровневое отображение: from first_keyна hashmap, и hashmap однозначно отображает полное имя на monster char. Нам нужно как-то хранить это. Каждая запись отображения верхнего уровня выглядит следующим образом:

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
)

затем следуют персонажи монстров и отображение второго уровня.

Отображение второго уровня сериализуется путем упаковки его в большое целое число и преобразования его в байты. Каждое значение и ключ последовательно сдвигаются в целое число, что делает преобразование восстанавливаемым (количество битов на ключ / значение выводится из числа символов и iоба хранятся в записи строки).

Если запись имеет только один возможный символ монстра для сопоставления, iравен нулю, количество символов и отображение также равны нулю байтов. Символ хранится там, где jобычно хранится.

Полные данные имеют размер 651 байт, сериализованный как строка байтов питона, его 1426 байт.

Программа декодирования, по сути, делает это наоборот: сначала она извлекает first_keyи ищет в данных соответствующую запись. Затем он вычисляет хеш имени и выполняет поиск в хеш-карте соответствующей записи.

Необъяснимый декодер

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

Инструмент анализа

Это инструмент, который я сделал и использовал для генерации данных - читайте на свой страх и риск:

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

Тестовый водитель

#!/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
        ))
Йонас Шефер
источник
0

awk 73 + 2060 байт

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

Данные были подготовлены к этому:

  "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 символов) т.е. кратчайшую уникальную строку с символом монстра, добавленным к имени и, наконец, к этой форме:

AlAAnAArch@ArchoAAsh@Asm&

(в начале строки должен быть отступающий символ, чтобы пометить несоответствие). При поиске совпадения имя сокращается на символ символом с конца, пока не будет найдено совпадение, а следующий символ после совпадения возвращается :

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

Я все еще могу сбрить несколько байтов из строки монстров с некоторой организацией:

AAnArch@ArchoAsh@Asm&

Учитывая, что размер данных с именами монстров, начиная с A, уменьшится с 38 байтов до 22, это означает уменьшение размера данных в среднем с 2060 до 1193.

это все еще в стадии разработки, и строка монстров будет опубликована чуть позже.

Джеймс Браун
источник