tło
Gra komputerowa NetHack pochodzi z 1987 roku, zanim szeroko rozpowszechniono stosowanie grafiki w grach komputerowych. W grze jest wiele potworów i potencjalnie wiele musi zmieścić się na ekranie, więc potwory są rysowane w bardzo minimalny sposób: potwór jest po prostu rysowany jako postać ASCII na ekranie.
Oprócz wielu potworów istnieje wiele rodzajów potworów. Może być ważne, aby wiedzieć, który jest który; musiałbyś inaczej zareagować na widok kota i smoka. Jako taka większość ASCII jest używana do reprezentowania potworów; na przykład kotek jest f
, a czerwony smok jest D
. Oznacza to, że bardzo pomocna może być wiedza o tym, jak będzie wyglądać dany potwór, ponieważ pomoże ci go rozpoznać, jeśli napotkasz go później w grze. (Pamiętaj, że istnieje więcej rodzajów potworów niż znaków ASCII, więc niektóre z nich są wspólne; zarówno czerwony, jak i niebieski smok D
).
Zadanie
Twój program musi przyjąć nazwę potwora NetHack jako dane wejściowe i wygenerować postać ASCII, która reprezentuje go w grze jako dane wyjściowe. Program może założyć, że dane wejściowe są w rzeczywistości nazwą potwora NetHack; może, jeśli chce awarii, generować bezsensowne wyniki itp., jeśli dane wejściowe są nieprawidłowe.
Poniższy fragment stosu jest obiektem JSON, który zapewnia pełne odwzorowanie możliwych danych wejściowych na odpowiadające im dane wyjściowe:
Zasadniczo więc zadanie polega na tym, że „klucz w słowniku reprezentowany przez powyższy obiekt JSON, zwraca odpowiednią wartość”.
Zauważ, że wyzwanie to jest poniekąd odwrotną złożonością kolmogorowa ; zamiast przechodzić z małego / pustego wejścia do dużego wyjścia, przechodzisz z dużego wejścia do małego wyjścia. (W ten sposób na wejściu znajduje się wiele zbędnych informacji, które można zignorować lub wykorzystać w dowolny sposób). Jest również dość podobny do regex golfa, z tym że a) dozwolony jest dowolny język (nie tylko regex), i b) istnieją więcej niż dwa możliwe wyniki. (Mieliśmy już kilka takich zadań, takich jak te dwa , ale to zadanie jest nieco inne, ponieważ określone zachowanie wejścia / wyjścia ma silniejsze wzorce).
Wyjaśnienia
Możesz użyć dowolnego rozsądnego formatu danych wejściowych i wyjściowych (np. Możesz wygenerować dane wyjściowe jako znak, kod ASCII lub ciąg znaków o długości jednego znaku). Jeśli chcesz, możesz przesłać funkcję zamiast pełnego programu.
Jest to już wspomniane w standardowych lukach, ale dla przypomnienia: nie można przechowywać zależności między danymi wejściowymi i wyjściowymi w innym miejscu niż kod źródłowy programu. Wyzwanie to polega przede wszystkim na reprezentowaniu zachowania wejścia / wyjścia w możliwie najmniejszej przestrzeni, więc nie wolno robić rzeczy takich jak pobieranie listy z Internetu, przechowywanie korespondencji w zewnętrznym pliku, uruchamianie NetHacka w trybie debugowania i spawnowanie danego potwora aby zobaczyć, jak to wygląda itp. (Poza tym nie chcę walczyć z potworami, aby przetestować twoje zgłoszenia).
Warunek zwycięstwa
To jest golf golfowy , więc zwycięskim hasłem będzie rekord najkrótszy, liczony w bajtach. Powodzenia!
źródło
mail daemon
> _ <Odpowiedzi:
Galaretka , 309 bajtów w kodowaniu Galaretki
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 dragon
i ablue dragon
to oba typy smoków, a zatem wyglądają jakD
. 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 shaman
o
kobold zombie
Z
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.
sphere
Zdecydowanie sugeruje, że potwór jest w klasiee
); dwuznaczne słowo jest słowem, które sprawia, że znacznie mniej sugestia (lord
nie 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 jakred
) 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:
woodchuck
jest jednym słowem długim (a więc wskaźnikiem), a wyszukiwanie w tabeliwoodchuck
daje nam zamierzoną odpowiedźr
.abbot
jest również jednym słowem, ale wygląda jak@
. Jako takieabbot
jest uważane za słowo dwuznaczne; wyszukiwanie tabeli jest puste i@
domyślnie zwracamy odpowiedź .vampire lord
składa się ze wskaźnika (vampire
odpowiadającegoV
) i niejednoznacznego słowa (lord
którego nie ma w tabeli). Oznacza to, że sprawdzamy oba słowa (w odwrotnej kolejności), a następnie udzielamy poprawnej odpowiedziV
.gelatinous cube
składa się z nonword (gelatinous
odpowiadającego zH
powodu kolizji skrótu) i wskaźnika (cube
odpowiadającegob
). Ponieważ bierzemy tylko ostatnie słowo znalezione w tabeli, zwraca onob
zgodnie z oczekiwaniami.gnome mummy
składa się z dwóch wskaźników,gnome
odpowiadającychG
imummy
odpowiadającychM
. Bierzemy ostatni wskaźnik i otrzymujemyM
to, czego chcemy.Kod do obsługi klasyfikacji opartej na słowach jest ostatnim wierszem programu Jelly. Oto jak to działa:
Istnieją dwa prawdziwe przypadki; jeśli dane wejściowe składają się wyłącznie z niejednoznacznych słów,
t0
usuwa całe wyniki wyszukiwania tabel i@
domyślnie otrzymujemy wynik; jeśli na wejściu znajdują się wskaźniki,t0
usunie 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: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, z
OḌ
; 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ównoDeath
iYeenoghu
hash 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:
Pozostała część programu, początek drugiego wiersza, implementuje funkcję skrótu:
Weryfikacja
To jest skrypt Perla, którego użyłem do sprawdzenia, czy program działa poprawnie:
źródło
JavaScript (ES6),
915...902890 bajtówSformatowany
Poniżej znajduje się sformatowana wersja kodu ze obciętymi danymi ładunku.
Jak to działa
Krok 1
Najpierw redukujemy nazwę potwora poprzez:
1
„s”.Przykłady:
Prowadzi to do kilku kolizji. Na przykład
"Master Assassin"
i"Master Kaen"
oba są zredukowane do"Mst1n"
. Na szczęście wszystkie kolidujące nazwy potworów mają ten sam symbol (@
w tym przypadku).Krok 2
Następnie interpretujemy ten 5-znakowy ciąg jako liczbę podstawową 36, aby przekonwertować go na liczbę dziesiętną (ta operacja nie rozróżnia wielkości liter) i stosujemy moduł
8713
, który został empirycznie wybrany do utworzenia listy kluczy bez kolizji.Przykłady:
Krok 3
Wszystkie klucze są sortowane w kolejności rosnącej:
Przekształcone na wartości delta:
I zakodowane jako znaki ASCII w zakresie
[ 32, 126 ]
. Niektóre pośrednie wartości manekina są wstawiane, gdy różnica między dwoma kolejnymi kluczami przekracza maksymalną możliwą do zakodowania wielkość.Na koniec lista kluczy jest mapowana na listę symboli ułożonych w tej samej kolejności.
Test
Pokaż fragment kodu
źródło
Java, 1130 bajtów
Nie golfowany:
Imiona potworów to:
hashcode
metody Java => 32 bityZnak wyświetlany jest zakodowany na 6 bitach.
Tak więc każda krotka (nazwa potwora, postać) używa 14 bitów. Wszystkie krotki są zapisywane w BitSet i zakodowane w standardzie 64.
Tracę dużo bajtów z kodowaniem base64 i operacjami BitSet :-)
źródło
()->{...}
. Pytanie brzmi tak w sekcji „wyjaśnienia”.Mathematica, 1067 bajtów (kodowanie znaków rzymskich w systemie Mac OS)
Nienazwana funkcja pobiera ciąg znaków jako dane wejściowe i zwraca znak. Funkcja ma następującą postać:
Tutaj GIANT_STRING_1 jest ciągiem zawierającym 608 jednobajtowych znaków w rzymskim kodowaniu znaków Mac OS (żaden z nich nie jest w zakresie 00-1F), podczas gdy GIANT_STRING_2 jest ciągiem zawierającym 304 znaki ASCII.
Wiersz 2 uruchamia funkcję skrótu: konwertuje ciąg wejściowy na listę kodów znaków (kodowanie nie ma znaczenia, ponieważ wszystkie są drukowalne ASCII), a następnie oblicza sumę tych kodów znaków i sumę ich kwadratów, zarówno modulo 216, jak i wymuszając odpowiedź leży między 32 a 255. Następnie wiersze 1 i 3 przekształcają uporządkowane pary liczb całkowitych w dwuznakowe łańcuchy, czyli wartości skrótu, której ostatecznie używamy.
Wiersz 5 zamienia GIANT_STRING_1 w listę 304 ciągów dwóch znaków; wiersz 6 zamienia GIANT_STRING_2 w listę 304 ciągów jednoznakowych. Następnie wiersze 4 i 5 przekształcają te dwie listy w zestaw 304 reguł zastępowania: jeśli zobaczysz taki i taki dwuznakowy ciąg, zamień go w taki i taki jednoznakowy ciąg. Wreszcie wiersz 8 zamienia pozostały ciąg dwóch znaków w
"@"
.Na liście znajduje się 71 potworów, których symbolem jest
"@"
, i są one obsługiwane bez mieszania (ukradłem ten pomysł z komentarza ais523 na inną odpowiedź). Tak się składa, że pozostałe 304 wartości skrótu są unikalne! i dlatego żadne inne modyfikacje algorytmu nie są potrzebne. (Jest to szczęśliwa przerwa, którą"human"
należy odwzorować"@"
, ponieważ sumy kodów znaków w literach"human"
i literach"shark"
są identyczne, podobnie jak sumy kwadratów tych kodów - jako liczby całkowite, nawet modulo 216!)źródło
Python, 2055 bajtów
Oto moja uprząż testowa, na wypadek, gdyby pomogła komukolwiek innemu.
Napisałem mały program do wyliczenia wszystkich różnych sposobów wyodrębnienia 4 znaków plus długość łańcucha. Mój pierwotny plan polegał na tym, aby
ord()
te postacie zrobić z nimi matematykę i sprowadzić ją do idealnej funkcji skrótu, która wygenerowała wskaźniki w tabeli wyników. Napisałem więc kolejny mały program do wyliczenia wszystkich różnych sposobów sumowania / mnożenia / modulowania tych 4 znaków razem; ale wynikowe funkcje hash przechowywane mający drogę zbyt wielu kolizji. Więc w końcu poddałem się i zrobiłem to, co tu widzicie, czyli mapę od małej reprezentacji nazwy każdego potwora do odpowiedniego symbolu.To znaczy: chciałem dostać
ale udało mi się dotrzeć tylko tak daleko
gdzie moje wyszukiwanie
{relatively_large_dict}[small_string]
wyrażone jest jakre.match(small_string+"(.)", "relatively_large_string")
w golfa.źródło
JavaScript (ES6), 1178
Mniej golfa
Test
źródło
JavaScript, 1185 bajtów
Używa golfowej wersji skrótu łańcucha JavaScript znalezionego tutaj. Rzeczywisty skrót przechowywany w tabeli (ten długi ciąg) przyjmuje wartość bezwzględną skrótu wytworzonego tą metodą, konwertuje go na base-36 i upuszcza wszystkie oprócz trzech najmniej znaczących cyfr.
źródło
@
z tabeli i ustawiając domyślnie,@
jeśli dane wejściowe nie znalezionocavewoman
ichameleon
mieć ten sam pierwszy znak, ostatni znak i długość, co może być problemem?split("_")
może staćsplit
grawis_
grawisCyclops
iCroesus
,baluchitherium
ibaby long worm
,crocodile
icentipede
, i 24 więcejPython 3,
19151900 bajtówDziennik zmian:
Przekaż nazwę potwora jako argument pierwszego wiersza poleceń, otrzymaj znak na stdout.
Kiedy przeczytałem pytanie, pomyślałem „muszę to skompresować”. Pierwszym krokiem było małe litery wszystkich nazwisk.
Patrząc na dane, poczułem, że jakoś użycie pierwszej litery ostatniego słowa powinno załatwić sprawę jako wstępne przybliżenie, jakie litery może mieć potwór. Jak się okazuje, było to potężne wstępne przypuszczenie. Poniższa tabela to „pierwszy znak ostatniego słowa”, „liczba trafień”, „znaki potwora”:
Aby jeszcze bardziej ulepszyć rozkład, zmodyfikowałem nieznacznie klucz, XOR - wprowadzając drugi znak ostatniego słowa, przesunięty do bitów w prawo, do pierwszego znaku (nazwijmy ten konstrukt
first_key
):Jak widać, daje nam to dziewięć nazw, które można jednoznacznie zmapować tylko z tymi informacjami. Miły!
Teraz musiałem znaleźć pozostałe mapowanie. W tym celu zacząłem od przekształcenia pełnej (małej litery) nazwy na liczbę całkowitą:
Jest to po prostu połączenie 7-bitowych wartości ASCII nazw w wielką liczbę całkowitą. Bierzemy to modulo
4611686018427387903
moduł (2⁶²-1) do następnych kroków.Teraz próbuję znaleźć maskę bitową, która daje liczbę całkowitą, która z kolei ładnie odróżnia różne postacie potworów. Maski bitowe składają się z równomiernie rozłożonych (takich jak
101010101
lub1000100010001
) i są parametryzowane przez liczbę bitów (i>=1
) i spread (k>=1
). Ponadto maski są przesuwane w lewo o maksymalnie32*i
bit. Są one AND-owane z nazwą całkowitą, a wynikowa liczba całkowita jest używana jako klucz w odwzorowaniu. Wykorzystywane jest najlepsze (ocenione przezi*number_of_mapping_entries
) mapowanie wolne od konfliktów.Liczby całkowite uzyskane z AND-ing maski i zintegrowana nazwa są przesunięte w tył o
j
bity i pozbawione zer (przechowujemyi
,k
aj
wraz z mapowaniem aby móc zrekonstruować tego), co pozwala zaoszczędzić sporo miejsca.Mamy teraz dwupoziomowe odwzorowanie: od
first_key
do haszapy, a haszapa jednoznacznie odwzorowuje pełną nazwę na znak potwora. Musimy to jakoś przechowywać. Każdy wpis mapowania najwyższego poziomu wygląda następująco:następnie postacie potworów i mapowanie drugiego poziomu.
Mapowanie drugiego poziomu jest serializowane przez upakowanie go w dużą liczbę całkowitą i przekształcenie go w bajty. Każda wartość i klucz są kolejno przenoszone na liczbę całkowitą, co sprawia, że mapowanie jest rekonstruowalne (liczba bitów na klucz / wartość jest mniejsza od liczby znaków i
i
obie są przechowywane we wpisie wiersza).Jeśli wpis ma tylko jedną możliwą postać potwora do
i
zmapowania , wynosi zero, liczba znaków i odwzorowanie również wynoszą zero bajtów. Postać jest przechowywana gdziej
, normalnie byłby przechowywany.Pełne dane mają rozmiar 651 bajtów i są serializowane jako ciąg bajtów python o długości 1426 bajtów.
Program dekodujący zasadniczo robi to na odwrót: najpierw wyodrębnia plik
first_key
i wyszukuje w danych odpowiedni wpis. Następnie oblicza skrót nazwy i przeszukuje skrót dla odpowiedniego wpisu.Dekoder nieobjawiony
Narzędzie analityczne
To narzędzie, które stworzyłem i wykorzystałem do wygenerowania danych - czytaj na własne ryzyko:
Kierowca testowy
źródło
awk 73 + 2060 bajtów
Dane zostały przygotowane do tego:
(2060 znaków) tj. do najkrótszego unikalnego ciągu z postacią potwora dołączoną do nazwy i wreszcie do tej formy:
(na początku łańcucha musi znajdować się znak cofania, aby zaznaczyć niezgodność) Podczas wyszukiwania dopasowania nazwa jest zwężana przez znak char od końca do momentu dopasowania i zwracany jest następny znak po dopasowaniu :
Nadal mogę zgolić kilka bajtów z łańcucha potworów, organizując:
Biorąc pod uwagę rozmiar danych z nazwami potworów zaczynającymi się od
A
, zmniejszyłoby się z 38 bajtów do 22, co oznacza zmniejszenie rozmiaru danych średnio z 2060 do 1193.to wciąż trwa, a łańcuch potworów zostanie opublikowany nieco później.
źródło