Galaretka , 309 bajtów w kodowaniu Galaretki
“Æ÷“¥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”@;Ṫ
Wypróbuj online!
Uznałem, że nadszedł czas, aby spróbować swoich sił. Zastosowanie Jelly (i jego 8-bitowej strony kodowej) daje mi 12,5% przewagę nad językami tylko ASCII, a Jelly jest wygodny na to wyzwanie, ponieważ ma wbudowane podstawowe operatory konwersji z krótkimi nazwami, ale większość oszczędności są spowodowane lepszym algorytmem kompresji (ten program ma średnio mniej niż jeden bajt na typ potwora).
Algorytm i wyjaśnienie
Klasyfikacja oparta na słowach
Zdecydowałem, że aby uzyskać dobry wynik, trzeba było lepiej wykorzystać strukturę danych wejściowych niż inne wpisy. Jedna rzecz, która jest bardzo zauważalne jest to, że wiele potworów mają nazwy w postaci „ przymiotnik gatunku ”; a red dragoni a blue dragonto oba typy smoków, a zatem wyglądają jak D. Niektóre inne potwory mają nazwy „ praca gatunkowa ”, takie jak ; będąc typem orka, wygląda to jak . Sprawami komplikującymi są nieumarli; a jest zarówno koboldem, jak i zombie, a ten ostatni stan ma pierwszeństwo w nazewnictwie potworów NetHack, dlatego chcielibyśmy to sklasyfikować jako .orc shamanokobold zombieZ
Jako takie, słowa występujące w nazwach potworów sklasyfikowałem następująco: wskaźnik to słowo, które zdecydowanie sugeruje odpowiednią klasę potworów (np. sphereZdecydowanie sugeruje, że potwór jest w klasie e); dwuznaczne słowo jest słowem, które sprawia, że znacznie mniej sugestia ( lordnie powiedzieć dużo), a wszystkie inne słowa są sylaby , które nie dbają o. Podstawowa idea polega na tym, że patrzymy na słowa w nazwie potwora od końca do tyłu i wybieramy pierwszy widoczny wskaźnik. W związku z tym konieczne było upewnienie się, że nazwa każdego potwora zawiera co najmniej jeden wskaźnik, po którym nastąpiły całkowicie niejednoznaczne słowa. Jako wyjątek, słowa pojawiające się w nazwach potworów, które wyglądają jak@(największa grupa) są klasyfikowane jako dwuznaczne. Wszystko może pojawić się przed wskaźnikiem; na przykład, nazwy kolorów (takie jak red) zawsze pojawiają się wcześniej w nazwie niż wskaźnik, a zatem są uważane za słowa (ponieważ nigdy nie są badane podczas określania tożsamości potwora).
Ostatecznie ten program sprowadza się do tabeli skrótów, podobnie jak inne programy. Jednak tabela nie zawiera wpisów dla wszystkich nazw potworów ani dla wszystkich słów pojawiających się w nazwach potworów; raczej zawiera tylko wskaźniki. Hashy niejednoznacznych słów nie pojawiają się w tabeli, ale muszą być przypisane do pustych miejsc (próba wyszukania niejednoznacznego słowa zawsze będzie pusta). W przypadku słów niebędących słowami nie ma znaczenia, czy słowo pojawia się w tabeli, czy też nie, czy hash koliduje, czy nie, ponieważ nigdy nie używamy wartości wyszukiwania słowa niebędącego słowem. (Tabela jest dość rzadka, więc większość słów nie pojawia się w tabeli, ale kilka takich, jak np. flesh, Można znaleźć w tabeli w wyniku kolizji skrótu).
Oto kilka przykładów działania tej części programu:
woodchuckjest jednym słowem długim (a więc wskaźnikiem), a wyszukiwanie w tabeli woodchuckdaje nam zamierzoną odpowiedź r.abbotjest również jednym słowem, ale wygląda jak @. Jako takie abbotjest uważane za słowo dwuznaczne; wyszukiwanie tabeli jest puste i @domyślnie zwracamy odpowiedź .vampire lordskłada się ze wskaźnika ( vampireodpowiadającego V) i niejednoznacznego słowa ( lordktórego nie ma w tabeli). Oznacza to, że sprawdzamy oba słowa (w odwrotnej kolejności), a następnie udzielamy poprawnej odpowiedzi V.gelatinous cubeskłada się z nonword ( gelatinousodpowiadającego z Hpowodu kolizji skrótu) i wskaźnika ( cubeodpowiadającego b). Ponieważ bierzemy tylko ostatnie słowo znalezione w tabeli, zwraca ono bzgodnie z oczekiwaniami.gnome mummyskłada się z dwóch wskaźników, gnomeodpowiadających Gi mummyodpowiadających M. Bierzemy ostatni wskaźnik i otrzymujemy Mto, czego chcemy.
Kod do obsługi klasyfikacji opartej na słowach jest ostatnim wierszem programu Jelly. Oto jak to działa:
ḲÇ€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
Istnieją dwa prawdziwe przypadki; jeśli dane wejściowe składają się wyłącznie z niejednoznacznych słów, t0usuwa całe wyniki wyszukiwania tabel i @domyślnie otrzymujemy wynik; jeśli na wejściu znajdują się wskaźniki, t0usunie wszystko po prawej stronie wskaźnika znajdującego się najbardziej na prawo i Ṫda nam odpowiedni wynik dla tego wskaźnika.
Kompresja tabeli
Oczywiście podzielenie danych wejściowych na słowa samo w sobie nie rozwiązuje problemu; wciąż musimy zakodować zgodność między wskaźnikami i odpowiadającymi im klasami potworów (oraz brak korespondencji z niejednoznacznych słów). Aby to zrobić, stworzyłem rzadką tabelę z użyciem 181 pozycji (odpowiadających 181 wskaźnikom; jest to duża poprawa w stosunku do 378 potworów!) I 966 wszystkich pozycji (odpowiadających 966 wartościom wyjściowym funkcji skrótu). Tabela jest zakodowana w programie za pomocą dwóch ciągów: pierwszy ciąg określa rozmiary „przerw” w tabeli (które nie zawierają wpisów); a drugi ciąg określa klasę potworów, która odpowiada każdej pozycji. Oba są przedstawione w zwięzły sposób za pomocą konwersji bazy.
W programie Jelly kod wyszukiwania tabeli wraz z samym programem jest reprezentowany w drugim wierszu, od pierwszego µ. Oto jak działa ta część programu:
“…’ḃ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 jest jak baza 21, z tym wyjątkiem, że 21 jest cyfrą prawną, a 0 nie. Jest to dla nas wygodniejsze kodowanie, ponieważ liczymy dwa sąsiednie wpisy jako odstęp 1, dzięki czemu możemy znaleźć prawidłowe indeksy za pomocą sumy skumulowanej. Jeśli chodzi o część tabeli, która zawiera wartości, mamy 58 unikalnych wartości, więc najpierw dekodujemy na 58 kolejnych liczb całkowitych, a następnie dekodujemy ponownie za pomocą tabeli odnośników, która odwzorowuje je na rzeczywiste używane znaki. (Większość z nich to litery, więc rozpoczynamy drugą tabelę odnośników od wpisów nieliterowych, &;:' a następnie po prostu dołączamy stałą galaretki, która zaczyna się od wielkich i małych liter; ma również inne śmieci, ale nie obchodzi nas to o tym.)
Wartość wartownika „nie znaleziono indeksu” Jelly, jeśli użyjesz go do zindeksowania listy, zwraca ostatni element listy; w związku z tym dołączyłem zero (liczbę całkowitą zero, mimo że tabela składa się głównie ze znaków) do tabeli odnośników, aby nadać bardziej odpowiedni wskaźnik wskazujący brakujący wpis.
Funkcja skrótu
Pozostała część programu to funkcja skrótu. Zaczyna się to po prostu, zOḌ; to konwertuje ciąg wejściowy na jego kody ASCII, a następnie oblicza ostatni kod, plus 10-krotny przedostatni kod, plus 100-krotny kod wcześniej i tak dalej (ma to bardzo krótką reprezentację w Galaretce, ponieważ jest częściej używany jako string → funkcja konwersji liczb całkowitych). Gdybyśmy jednak po prostu zmniejszyli ten skrót bezpośrednio przez operację modułu, potrzebowalibyśmy raczej dużego stołu. Zamiast tego zaczynam od szeregu operacji mających na celu zmniejszenie tabeli. Każdy z nich działa w ten sposób: bierzemy piątą potęgę bieżącej wartości skrótu; następnie zmniejszamy wartość modulo o stałą (która stała zależy od używanej operacji). Ten łańcuch daje więcej oszczędności (pod względem zmniejszenia wynikowego rozmiaru tabeli) niż kosztuje (pod względem konieczności kodowania samego łańcucha operacji) na dwa sposoby: może stworzyć tabelęznacznie mniejszy (966 zamiast 3529 wpisów), a zastosowanie wielu etapów daje więcej możliwości wprowadzenia korzystnych kolizji (nie zdarzyło się to wiele, ale jest jedna taka kolizja: zarówno Deathi Yeenoghuhash do 806, co pozwala nam usunąć jeden wejście ze stołu, jak oboje idą&). Stosowane tutaj moduły to [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Nawiasem mówiąc, przyczyną podniesienia do piątej potęgi jest to, że jeśli po prostu weźmiesz wartość bezpośrednio, luki mają tendencję do pozostawania na tym samym rozmiarze, podczas gdy potęgowanie przesuwa luki i może umożliwić równomierne rozłożenie stołu po łańcuch zamiast utknąć w lokalnym minimum (bardziej równomiernie rozmieszczone odstępy pozwalają na bardziej precyzyjne kodowanie rozmiarów odstępów). Musi to być nieparzysta moc, aby zapobiec temu, że x ² = (- x ) ² wprowadza kolizje, a 5 działało lepiej niż 3.
Pierwszy wiersz programu koduje sekwencję modułów za pomocą kodowania delta:
“…’;“…‘_\
“…’ Compressed integer list encoding, arbitrary sized integers
; Append
“…‘ Compressed integer list encoding, small integers (≤ 249)
_\ Take cumulative differences
Pozostała część programu, początek drugiego wiersza, implementuje funkcję skrótu:
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).
Weryfikacja
To jest skrypt Perla, którego użyłem do sprawdzenia, czy program działa poprawnie:
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";
}
mail daemon> _ <