Latar Belakang
Game komputer NetHack berasal dari tahun 1987, sebelum penggunaan grafik dalam game komputer sudah banyak diketahui. Ada banyak monster dalam gim, dan berpotensi banyak yang perlu dimuat di layar sekaligus, jadi monster digambar dengan cara yang sangat minim: monster hanya digambar sebagai karakter ASCII di layar.
Selain ada banyak monster, ada banyak jenis monster. Penting untuk mengetahui mana yang mana; Anda harus bereaksi secara berbeda saat melihat anak kucing dan melihat seekor naga. Dengan demikian, sebagian besar ASCII digunakan untuk mewakili monster; misalnya, anak kucing f
, dan naga merah D
. Ini berarti bahwa akan sangat membantu untuk mengetahui seperti apa bentuk monster yang diberikan, karena itu akan membantu Anda untuk mengenalinya jika Anda menemukannya nanti di dalam game. (Perhatikan bahwa ada lebih banyak jenis monster daripada karakter ASCII, sehingga beberapa dari mereka berbagi; naga merah dan naga biru sama-sama D
.)
Tugas
Program Anda harus mengambil nama monster NetHack sebagai input, dan menghasilkan karakter ASCII yang mewakilinya dalam game sebagai output. Program diperbolehkan untuk berasumsi bahwa input sebenarnya adalah nama monster NetHack; mungkin jika ingin macet, menghasilkan hasil yang tidak berarti, dll. jika input tidak valid.
Cuplikan Stack berikut ini adalah objek JSON yang memberikan pemetaan penuh dari input yang mungkin untuk output yang sesuai:
Jadi pada dasarnya, tugas di sini adalah "diberikan kunci dalam kamus yang diwakili oleh objek JSON di atas, kembalikan nilai yang sesuai".
Perhatikan bahwa tantangan ini, dengan cara lain, adalah kompleksitas kolmogorov terbalik ; alih-alih beralih dari input kecil / kosong ke output besar, Anda beralih dari input besar ke output kecil. (Dengan demikian ada banyak informasi yang berlebihan dalam input, yang dapat Anda abaikan atau manfaatkan sesuai keinginan). Ini juga cukup mirip dengan golf regex, kecuali bahwa a) bahasa apa pun diperbolehkan (bukan hanya regex), dan b) ada lebih dari dua kemungkinan output. (Kami telah memiliki beberapa tugas seperti ini sebelumnya, seperti ini dua , tapi tugas ini agak berbeda karena perilaku input / output yang ditentukan memiliki pola yang lebih kuat).
Klarifikasi
Anda dapat menggunakan format input dan output yang masuk akal (mis. Anda dapat menghasilkan output sebagai karakter, atau sebagai kode ASCII, atau sebagai string yang panjangnya satu karakter). Anda dapat mengirimkan fungsi alih-alih program lengkap, jika diinginkan.
Ini sudah disebutkan dalam celah standar, tetapi hanya untuk mengulangi: Anda tidak dapat menyimpan korespondensi antara input dan output di mana pun selain kode sumber program Anda. Tantangan ini pada dasarnya adalah tentang merepresentasikan perilaku input / output dalam ruang sekecil mungkin, jadi Anda tidak boleh melakukan hal-hal seperti mengunduh daftar dari Internet, menyimpan korespondensi dalam file eksternal, memulai NetHack dalam mode debug dan memunculkan monster yang dimaksud untuk melihat seperti apa, dll. (Selain itu, saya tidak ingin harus melawan monster untuk menguji kiriman Anda.)
Kondisi kemenangan
Ini adalah kode-golf , sehingga entri yang menang akan menjadi entri yang terpendek, dihitung dalam byte. Semoga berhasil!
sumber
mail daemon
> _ <Jawaban:
Jelly , 309 byte dalam pengkodean Jelly
Cobalah online!
Saya memutuskan sudah saatnya saya menghadapi tantangan saya sendiri. Penggunaan Jelly (dan codepage 8-bit-nya) memberi saya keuntungan 12,5% dibandingkan bahasa ASCII saja, dan Jelly nyaman untuk tantangan ini karena memiliki operator konversi basis bawaan dengan nama pendek, tetapi sebagian besar penghematan disebabkan oleh algoritma kompresi yang lebih baik (rata-rata program ini kurang dari satu byte per jenis monster).
Algoritma dan penjelasan
Klasifikasi berbasis kata
Saya memutuskan bahwa untuk mendapatkan skor yang baik, perlu memanfaatkan struktur input lebih banyak daripada entri lainnya. Satu hal yang sangat mencolok adalah bahwa banyak monster memiliki nama bentuk " spesies kata sifat "; a dan a keduanya jenis naga, dan dengan demikian muncul sebagai . Beberapa monster lain memiliki nama bentuk " pekerjaan spesies ", seperti ; menjadi jenis orc, ini muncul sebagai . Masalah rumit adalah mayat hidup; a adalah kobold dan zombie, dan negara bagian terakhir diutamakan dalam penamaan monster NetHack, jadi kami ingin mengklasifikasikan ini sebagai .
red dragon
blue dragon
D
orc shaman
o
kobold zombie
Z
Karena itu, saya mengklasifikasikan kata-kata yang muncul dalam nama monster sebagai berikut: indikator adalah kata yang sangat menyarankan kelas monster yang sesuai (misalnya
sphere
sangat menyarankan bahwa monster itu ada di kelase
); sebuah kata ambigu adalah kata yang membuat jauh lebih sedikit dari saran (lord
tidak cerita banyak), dan semua kata lain adalah nonwords bahwa kita tidak peduli tentang. Ide dasarnya adalah bahwa kita melihat kata-kata dalam nama monster dari ujung mundur ke awal, dan memilih indikator pertama yang kita lihat. Dengan demikian, perlu untuk memastikan bahwa setiap nama monster mengandung setidaknya satu indikator, yang diikuti sepenuhnya oleh kata-kata yang ambigu. Sebagai pengecualian, kata-kata yang muncul dalam nama-nama monster yang terlihat seperti@
(kelompok terbesar) semuanya diklasifikasikan sebagai ambigu. Apa pun dapat muncul di depan indikator; misalnya, nama warna (sepertired
) selalu muncul lebih awal dalam nama daripada indikator, dan dengan demikian dianggap bukan kata (karena mereka tidak pernah diperiksa saat menentukan identitas monster).Pada akhirnya, program ini datang ke tabel hash, seperti program lainnya. Namun, tabel tidak mengandung entri untuk semua nama monster, atau untuk semua kata yang muncul dalam nama monster; melainkan hanya berisi indikator. Hash dari kata-kata yang ambigu tidak muncul dalam tabel, tetapi harus ditugaskan ke slot kosong (berusaha mencari kata yang ambigu akan selalu muncul kosong). Untuk yang bukan kata, tidak masalah apakah kata tersebut muncul di tabel atau tidak, atau apakah hash bertabrakan atau tidak, karena kita tidak pernah menggunakan nilai mencari kata yang bukan. (Tabel ini cukup jarang, sehingga sebagian besar non-kata tidak muncul dalam tabel, tetapi beberapa, seperti
flesh
, ditemukan dalam tabel sebagai konsekuensi dari tabrakan hash.)Berikut ini beberapa contoh cara kerja bagian dari program ini:
woodchuck
adalah satu kata panjang (dengan demikian indikator), dan pencarian tabelwoodchuck
memberi kita jawaban yang diinginkanr
.abbot
juga panjang satu kata, tetapi terlihat seperti@
. Dengan demikian,abbot
dianggap sebagai kata yang ambigu; pencarian tabel muncul kosong, dan kami mengembalikan jawaban@
secara default.vampire lord
terdiri dari indikator (vampire
sesuai denganV
) dan kata yang mendua (lord
, yang tidak ada dalam tabel). Ini berarti bahwa kami memeriksa kedua kata (dalam urutan terbalik), lalu memberikan jawaban yang benarV
.gelatinous cube
terdiri dari kata non ((gelatinous
sesuai denganH
akibat tabrakan hash) dan indikator (cube
, sesuai denganb
). Karena kami hanya mengambil kata terakhir yang ditemukan dalam tabel, ini akan kembalib
, seperti yang diharapkan.gnome mummy
terdiri dari dua indikator,gnome
sesuai denganG
danmummy
sesuai denganM
. Kami mengambil indikator terakhir, dan dapatkanM
, itulah yang kami inginkan.Kode untuk menangani klasifikasi berbasis kata adalah baris terakhir dari program Jelly. Begini cara kerjanya:
Ada dua kasus nyata; jika input seluruhnya terdiri dari kata-kata yang ambigu,
t0
menghapus seluruh output dari tabel lookup dan kami mendapatkan@
hasil secara default; jika ada indikator dalam input,t0
akan menghapus apa pun di sebelah kanan indikator paling kanan, danṪ
akan memberi kami hasil yang sesuai untuk indikator itu.Kompresi tabel
Tentu saja, memecah input menjadi kata-kata tidak menyelesaikan masalah dengan sendirinya; kita masih harus menyandikan korespondensi antara indikator dan kelas monster yang sesuai (dan kurangnya korespondensi dari kata-kata yang ambigu). Untuk melakukan ini, saya membuat tabel sederhana dengan 181 entri yang digunakan (sesuai dengan 181 indikator; ini merupakan peningkatan besar dari 378 monster!), Dan 966 entri total (sesuai dengan nilai output 966 fungsi hash). Tabel dikodekan dalam programnya melalui penggunaan dua string: string pertama menentukan ukuran "celah" dalam tabel (yang tidak mengandung entri); dan string kedua menentukan kelas monster yang sesuai dengan setiap entri. Keduanya disajikan secara ringkas melalui konversi basis.
Dalam program Jelly, kode untuk pencarian tabel, bersama dengan program itu sendiri, diwakili di baris kedua, dari yang pertama
µ
dan seterusnya. Begini cara kerja bagian dari program ini:Base bijective 21 seperti base 21, kecuali bahwa 21 adalah digit hukum dan 0 tidak. Ini adalah pengkodean yang lebih nyaman bagi kami karena kami menghitung dua entri yang berdekatan memiliki celah 1, sehingga kami dapat menemukan indeks yang valid melalui jumlah kumulatif. Ketika sampai pada bagian tabel yang menyimpan nilai-nilai, kita memiliki 58 nilai unik, jadi pertama-tama kita mendekode menjadi 58 bilangan bulat berturut-turut, dan kemudian mendekode lagi menggunakan tabel pencarian yang memetakan ini ke dalam karakter aktual yang digunakan. (Sebagian besar adalah huruf, jadi kami memulai tabel pencarian sekunder ini dengan entri non-huruf
&;:'
,, dan kemudian hanya menambahkan konstanta Jelly yang dimulai dengan huruf besar dan kecil; ia juga memiliki beberapa sampah lain tetapi kami tidak peduli tentang itu.)Nilai sentinel "index not found" Jelly, jika Anda menggunakannya untuk mengindeks ke dalam daftar, mengembalikan elemen terakhir dari daftar; jadi, saya menambahkan nol (bilangan bulat nol, meskipun tabel sebagian besar terdiri dari karakter) ke tabel pencarian untuk memberikan sentinel yang lebih tepat untuk menunjukkan entri yang hilang.
Fungsi hash
Bagian yang tersisa dari program adalah fungsi hash. Ini dimulai cukup sederhana, dengan
OḌ
; ini mengubah string input menjadi kode ASCII, dan kemudian menghitung kode terakhir, ditambah 10 kali kode kedua dari belakang, ditambah 100 kali kode sebelumnya, dan seterusnya (ini memiliki representasi yang sangat singkat di Jelly karena lebih umum digunakan sebagai string → fungsi konversi integer). Namun, jika kita hanya mengurangi hash ini secara langsung melalui operasi modulus, kita akan membutuhkan tabel yang agak besar. Jadi sebagai gantinya, saya memulai dengan rantai operasi untuk mengurangi tabel. Mereka masing-masing bekerja seperti ini: kita mengambil kekuatan kelima dari nilai hash saat ini; lalu kita mengurangi nilai modulo menjadi konstanta (konstanta mana yang bergantung pada operasi mana yang kita gunakan). Rantai ini memberikan lebih banyak penghematan (dalam hal mengurangi ukuran tabel yang dihasilkan) daripada biayanya (dalam hal perlu menyandikan rantai operasi itu sendiri), dengan dua cara: ia dapat membuat tabeljauh lebih kecil (966 daripada 3529 entri), dan penggunaan beberapa tahap memberikan lebih banyak kesempatan untuk memperkenalkan tabrakan yang bermanfaat (ini tidak banyak terjadi, tetapi ada satu tabrakan seperti itu: keduanyaDeath
danYeenoghu
hash hingga 806, sehingga memungkinkan kami untuk menghapus satu entri dari tabel, karena keduanya pergi ke&
). Moduli yang digunakan di sini adalah [3529, 2163, 1999, 1739, 1523, 1378, 1246, 1223, 1145, 966]. Kebetulan, alasan untuk menaikkan ke kekuatan kelima adalah bahwa jika Anda hanya mengambil nilai secara langsung, kesenjangan cenderung tetap dengan ukuran yang sama, sedangkan eksponensial memindahkan celah di sekitar dan dapat memungkinkan meja untuk didistribusikan lebih merata setelah rantai daripada terjebak dalam minimum lokal (kesenjangan yang lebih merata memungkinkan pengodean ukuran celah yang lebih singkat). Ini harus menjadi kekuatan aneh untuk mencegah fakta bahwa x ² = (- x ) ² memperkenalkan tabrakan, dan 5 bekerja lebih baik daripada 3.Baris pertama program mengkodekan urutan moduli menggunakan delta encoding:
Sisa program, awal baris kedua, mengimplementasikan fungsi hash:
Verifikasi
Ini adalah skrip Perl yang saya gunakan untuk memverifikasi bahwa program ini bekerja dengan benar:
sumber
JavaScript (ES6),
915...902890 byteDiformat
Di bawah ini adalah versi kode yang diformat dengan data payload terpotong.
Bagaimana itu bekerja
Langkah 1
Kami pertama-tama mengurangi nama monster dengan:
1
's.Contoh:
Ini mengarah pada beberapa tabrakan. Misalnya,
"Master Assassin"
dan"Master Kaen"
keduanya dikurangi menjadi"Mst1n"
. Untungnya, semua nama monster yang bertabrakan memiliki simbol yang sama (@
dalam hal ini).Langkah 2
Kemudian, kami menafsirkan string 5-karakter ini sebagai basis 36 untuk mengubahnya menjadi desimal (operasi ini tidak sensitif huruf) dan kami menerapkan modulo
8713
, yang secara empiris dipilih untuk menghasilkan daftar kunci yang bebas tabrakan.Contoh:
Langkah # 3
Semua kunci diurutkan dalam urutan menaik:
Dikonversi ke nilai delta:
Dan dikodekan sebagai karakter ASCII dalam jangkauan
[ 32, 126 ]
. Beberapa nilai dummy menengah disisipkan ketika perbedaan antara dua kunci berturut-turut melebihi besarnya maksimum yang dapat disandikan.Akhirnya, daftar kunci dipetakan ke daftar simbol yang diatur dalam urutan yang sama.
Uji
Tampilkan cuplikan kode
sumber
Java, 1130 byte
Tidak Disatukan:
Nama monster adalah:
hashcode
metode Java => 32 bitKarakter tampilan dikodekan pada 6 bit.
Jadi setiap tuple (nama monster, karakter) menggunakan 14 bit. Semua tupel disimpan dalam BitSet dan basis 64 disandikan.
Saya kehilangan banyak byte dengan encoding base64 dan operasi BitSet :-)
sumber
()->{...}
. Pertanyaannya mengatakan demikian di bagian "klarifikasi".Mathematica, 1067 bytes (penyandian karakter Mac OS Roman)
Fungsi yang tidak disebutkan namanya mengambil string sebagai input dan mengembalikan karakter. Fungsi ini memiliki bentuk berikut:
Di sini GIANT_STRING_1 adalah string yang berisi 608 karakter satu-byte dalam penyandian karakter Mac OS Roman (tidak ada yang berada dalam kisaran 00-1F), sedangkan GIANT_STRING_2 adalah string yang berisi 304 karakter ASCII.
Baris 2 memulai fungsi hash: ia mengubah string input menjadi daftar kode karakter (pengkodean tidak relevan karena semuanya dapat dicetak ASCII), kemudian menghitung jumlah kode karakter dan jumlah kotak mereka, baik modulo 216 dan memaksa jawaban untuk berada di antara 32 dan 255. Kemudian baris 1 dan 3 mengubah pasangan integer yang diurutkan menjadi string dua karakter, yang merupakan nilai hash yang akhirnya kita gunakan.
Baris 5 mengubah GIANT_STRING_1 menjadi daftar yang terdiri dari 304 string dua karakter; baris 6 mengubah GIANT_STRING_2 menjadi daftar 304 string satu karakter. Kemudian baris 4 dan 5 mengonversi kedua daftar menjadi satu set aturan penggantian 304: jika Anda melihat string dua-karakter ini-dan-itu, ubahlah menjadi string satu-karakter yang-dan-itu. Akhirnya, baris 8 mengubah string dua karakter yang tersisa menjadi
"@"
.Ada 71 monster dalam daftar yang simbolnya ada
"@"
, dan mereka ditangani tanpa hashing (saya mencuri ide ini dari komentar ais523 pada jawaban lain). Kebetulan bahwa 304 nilai hash lainnya semuanya unik! sehingga tidak diperlukan modifikasi lain pada algoritma. (Ini keberuntungan yang"human"
perlu dipetakan"@"
, karena jumlah kode karakter dari surat-surat di"human"
dan huruf dalam"shark"
identik, seperti jumlah kuadrat dari kode-kode itu — sebagai bilangan bulat, bahkan bukan modulo 216!)sumber
Python, 2055 byte
Inilah test harness saya, kalau-kalau itu membantu orang lain.
Saya menulis sebuah program kecil untuk menghitung semua berbagai cara mengekstraksi 4 karakter ditambah panjang string. Rencana awal saya adalah untuk kemudian
ord()
karakter-karakter ini, melakukan beberapa matematika pada mereka, dan mendidihkannya ke fungsi hash sempurna yang menghasilkan indeks ke dalam tabel output. Jadi saya menulis program kecil lain untuk menghitung semua berbagai cara penjumlahan / penggandaan / modulo'ing 4 karakter ini bersama-sama; tetapi fungsi hash yang dihasilkan terus memiliki cara terlalu banyak tabrakan. Jadi akhirnya saya menyerah dan hanya melakukan apa yang Anda lihat di sini, yang hanya merupakan peta dari representasi string kecil dari setiap nama monster ke simbol yang sesuai.Yaitu: Apa yang ingin saya dapatkan adalah
tetapi saya hanya berhasil sampai sejauh itu
di mana pencarian dict saya
{relatively_large_dict}[small_string]
dinyatakanre.match(small_string+"(.)", "relatively_large_string")
untuk golfiness.sumber
JavaScript (ES6), 1178
Kurang golf
Uji
sumber
Javascript, 1185 byte
Menggunakan versi golf dari hash string Javascript yang ditemukan di sini. Hash aktual yang disimpan dalam tabel (string panjang itu) mengambil nilai absolut dari hash yang dihasilkan oleh metode itu, mengubahnya menjadi basis-36, dan menjatuhkan semua kecuali tiga digit paling tidak signifikan.
sumber
@
dari tabel dan hanya default@
jika input tidak ditemukan.cavewoman
danchameleon
memiliki karakter pertama yang sama, karakter terakhir dan panjang, yang mungkin menjadi masalah?split("_")
dapat menjadisplit
backtick_
backtickCyclops
danCroesus
,baluchitherium
danbaby long worm
,crocodile
dancentipede
, dan 24 lainnyaPython 3,
19151900 byteChangelog:
Lulus nama monster sebagai argumen baris perintah pertama, terima karakter di stdout.
Ketika saya membaca pertanyaan, saya berpikir "Saya perlu mengompres ini". Langkah pertama adalah huruf kecil semua nama.
Melihat data, saya merasa bahwa entah bagaimana menggunakan huruf pertama dari kata terakhir harus melakukan trik sebagai tebakan pertama kasar pada huruf mana yang mungkin dimiliki monster itu. Ternyata, itu dugaan awal yang kuat. Tabel berikut adalah "karakter pertama dari kata terakhir", "jumlah hit", "karakter monster":
Untuk lebih meningkatkan penyebaran, saya memodifikasi kunci sedikit, dengan XOR-ing karakter kedua dari kata terakhir, bergeser ke bit ke kanan, ke karakter pertama (mari kita sebut konstruk ini
first_key
):Seperti yang Anda lihat, ini memberi kami sembilan nama yang dapat dipetakan secara unik hanya dengan informasi itu. Bagus!
Sekarang saya perlu menemukan pemetaan yang tersisa. Untuk ini saya mulai dengan mengonversi nama lengkap (huruf kecil) ke integer:
Ini hanya menggabungkan nilai ASCII 7bit dari nama-nama tersebut menjadi bilangan bulat besar. Kami mengambil modulo ini
4611686018427387903
(2⁶²-1) untuk langkah selanjutnya.Sekarang saya mencoba untuk menemukan bitmask yang menghasilkan integer yang pada gilirannya membedakan karakter monster yang berbeda. Topeng bit terdiri dari yang tersebar merata (seperti
101010101
atau1000100010001
) dan parametris dengan jumlah bit (i>=1
) dan spread (k>=1
). Selain itu, masker dibiarkan bergeser hingga32*i
bit. Itu adalah AND-ed dengan nama integer dan integer yang dihasilkan digunakan sebagai kunci dalam pemetaan.i*number_of_mapping_entries
Pemetaan bebas konflik terbaik ( diberi skor oleh ) digunakan.Bilangan bulat yang diperoleh dari DAN-topeng dan nama bilangan bulat digeser kembali oleh
j
bit dan dilucuti dari nol mereka (kami menyimpani
,k
danj
bersama dengan pemetaan untuk dapat merekonstruksi itu), menghemat banyak ruang.Jadi sekarang kita memiliki pemetaan dua tingkat: dari
first_key
ke hashmap, dan hashmap memetakan nama lengkap ke monster char secara unik. Kita perlu menyimpannya entah bagaimana. Setiap entri pemetaan tingkat atas terlihat seperti ini:diikuti oleh karakter monster dan pemetaan tingkat kedua.
Pemetaan tingkat kedua diserialisasi dengan mengemasnya menjadi bilangan bulat besar dan mengubahnya menjadi byte. Setiap nilai dan kunci digeser secara berurutan ke dalam bilangan bulat, yang membuat pemetaan dapat direkonstruksi (jumlah bit per kunci / nilai dapat disimpulkan dari jumlah karakter dan
i
, keduanya disimpan dalam entri baris).Jika sebuah entri hanya memiliki satu karakter monster yang memungkinkan untuk dipetakan,
i
adalah nol, jumlah karakter dan pemetaan juga nol byte. Karakter disimpan di tempatj
biasanya disimpan.Data lengkap berukuran 651 byte, diserialisasi sebagai string byte python, 1426 byte.
Program decoding pada dasarnya melakukannya sebaliknya: pertama mengekstraknya
first_key
dan mencari data untuk entri yang sesuai. Kemudian menghitung hash nama dan mencari melalui hashmap untuk entri yang sesuai.Dekoder tidak terarah
Alat analisis
Ini adalah alat yang saya buat dan gunakan untuk menghasilkan data - baca dengan risiko Anda sendiri:
Driver uji
sumber
awk 73 + 2060 byte
Data disiapkan untuk ini:
(2060 karakter) yaitu. untuk menyingkat string unik dengan karakter monster ditambahkan ke nama dan akhirnya ke bentuk ini:
(harus ada char back fall di awal string untuk menandai tidak cocok) Saat mencari pertandingan nama disingkat char oleh char dari akhir sampai ada pertandingan dan char berikutnya setelah pertandingan dikembalikan :
Saya masih bisa mencukur beberapa byte dari string monster dengan pengorganisasian:
Mempertimbangkan ukuran data dengan nama monster dimulai dengan
A
akan berkurang dari 38 byte menjadi 22 berarti menjatuhkan ukuran data dari 2060 menjadi 1193 rata-rata.ini masih dalam proses dan string monster akan dipublikasikan sedikit kemudian.
sumber