Pernahkah Anda mendengar tentang Code Golf ? Ini seperti permainan di mana setiap orang mencoba menulis kode tertentu dengan karakter sesedikit mungkin.
Salah satu solusi (kode 171-byte) yang diunggah ke kontes AtCoder * banyak dikritik, jadi saya memutuskan untuk mencari tahu apa masalahnya.
(Catatan penerjemah : AtCoder adalah platform tempat diadakannya berbagai kompetisi antar developer. Dilihat dari domain .jp, platformnya adalah bahasa Jepang, tetapi ada pengguna dari seluruh dunia. Misalnya, pada saat artikel ini diterjemahkan, ada 3 pengguna dari Rusia di bagian atas situs.)
Memampatkan kode
Seperti yang saya pahami, mengompresi kode (= mengurangi bobot-ukurannya) mempersingkatnya secara simbolis. Anggota Code Golf, bisa dikatakan, menempatkan jiwa mereka dalam pengurangan setiap karakter, setiap byte. Dan karena tujuan kompetisi ini adalah untuk menulis kode sesingkat mungkin, tidak ada alasan untuk tidak mengompresnya.
Lihat dulu kode berikut.
#!ruby -Knrzlib
eval Zlib.inflate'x = Q
D OS c
]r ݳ By
O{4 . i aQ(`}cB I2e ߣ IeT јL> )u, p S W H~. , :
z:Ӊ g O7ʲ vQ 1h ^< =& \u7'Saya hampir tidak bisa membacanya. Tapi dari baris pertama, saya mengerti bahwa kode tersebut ditulis di Ruby.
#!ruby -KnrzlibIni adalah shebang dan memiliki -Kn dan -rzlib yang ditentukan sebagai opsi baris perintah.
-Kn menunjukkan bahwa kode tertulis harus diperlakukan sebagai biner, kode tanpa karakter. Misalnya, #coding: binary melakukan hal yang sama.
-rzlib - Diperlukan oleh library zlib. Akronim dari require "zlib".
eval Zlib.inflate'…Baris berikutnya.
Zlib.inflate adalah metode untuk membongkar kode terkompresi. Karena Anda dapat melihat bahwa masih ada baris setelah karakter ', kami memahami bahwa bagian kode ini membongkar kode yang dikompresi dan menerapkan eval padanya.
Saya akan mencobanya sendiri
Saya pikir akan menyenangkan membuat template kompresi kode.
Ini membutuhkan tiga langkah: 1) tulis kode, 2) kompres kode, dan 3) buat kode akhir. Pada gilirannya, langkah 1 dan 2 harus diulangi untuk menurunkan rasio kompresi.
Menulis kode
Ayo tulis kodenya dulu. (Nah, langkah ini bukan pertanda baik)
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|x|[a,x,3,x]+(0..29).map{v=x+4;u=x*60+9+_1;[a,v,v,v,a,v,3,6,*[a,6,6,6]*(29-_1),?<,6,x,u,a,v,u,v]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}Kode ini panjangnya 216 byte.
Sekarang mari coba kompres.
Kompres
Dengan menggunakan skrip ini , saya dapat menguranginya menjadi 194 byte!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BKirim ke AtCoder
Saya mengompresi kode dan ingin mengirimkannya, tetapi ada satu masalah.
Sayangnya, saya tidak bisa begitu saja menyalin dan menempelkan kode ini dan mengirimkannya sebagaimana adanya. Kode yang dihasilkan oleh kompresi adalah biner. Namun, layar pengiriman AtCoder adalah UTF-8. Sering kali, kode terkompresi berisi string byte yang tidak valid dalam UTF-8, jadi jika Anda menyalin dan menempelkannya apa adanya, itu akan kacau.
Jadi saya akan memposting kode yang dikodekan URI langsung menggunakan DevTools.
Mari buka layar kirim dan luncurkan DevTools. Kami tetap membuka halaman untuk mengirimkan solusi ke kontes.
Ketika semuanya telah disiapkan, seperti yang ditunjukkan pada tangkapan layar di atas, kami menekan tombol untuk mengirimkan solusi kami di situs. DevTools akan menampilkan permintaan yang kami kirimkan.
Pilih permintaan yang disebut "kirim" dan klik kanan padanya, tekan Salin, lalu Salin sebagai pengambilan.
Buka konsol Anda dan tempelkan kode yang baru saja Anda salin.
Tempel setelah sourceCode = kode yang dikodekan URI kami (tidak ditampilkan di tangkapan layar). Kami menggunakan skrip ini untuk menyandikan ke URI . (Simpan sebagai deflate-uriencode.rb)
$ ruby deflate-uriencode.rb agc047_e.rb
194 B
%23%21ruby+-Knrzlib%0Aeval+Zlib.inflate%27x%DA-%8DQ%0A%830%10D%AF%D2Ou%B7A%13%5D%14%2B%1E%24%04%C9%01%0AB%13%094%B9%7Bwc%99%8F%81%99%E1%CD%19%C3%E7ai%9CG%F4%DB%0E%D8%E3%80%06%F7%17j6%E3%C0r%E0%D4%DB%9F%DF%9C%B2%F5%988N%0E%9A%5E%29%BD%B4%B5%B8%B6%04%E3%1A%B7%D4Q%0F%0B%1C%C3%CA%BB%ABJ%DC+a%C7%09%89%5C%D7%E8%E5y%0C%AD%5C%10%D3b%DDD%BC%5C%29%95%3A%FD%A99%C8%9D%16%DDw*%DC%05%A73%04f+%C9%19N%822l%84%B2%DE%97%F2%03%93%919%B0%DE%97%F2%03%93%919%B0%27Ubah agc047_e.rb menjadi deflate-uriencode.rb.
Dari baris kedua keluaran, salin semuanya setelah% 23 dan tempelkan setelah sourceCode = di atas.
Sekarang kami dapat mengirimkan solusi kami.
Mengubah kode (membuatnya lebih pendek)
Mari persingkat kodenya. Ada dua cara untuk mempersingkat kode setelah kompresi.
- Kecilkan kode sumber
- Tingkatkan rasio kompresi
Saya akan mencoba menggunakan kedua metode tersebut. Menyusut kode sumber adalah cara favorit kontributor Code Golf.
Meningkatkan rasio kompresi
Bagaimana cara meningkatkan rasio kompresi? Kami sekarang menggunakan kompresi Deflate, yang merupakan kombinasi dari kompresi run-length dan pengkodean Huffman. Perhatikan kode Huffman ini. Kode Huffman berbeda karena rasio kompresi meningkat seiring dengan penurunan entropi sebelum kompresi. Entropi berkurang sebagai kemungkinan munculnya pergeseran kode. Oleh karena itu, jika probabilitas kemunculan kode digeser, rasio kompresi akan meningkat saat terjadi pergeseran.
Cara efektif untuk mengurangi kemungkinan munculnya kode adalah dengan mengurangi tipe karakter. Untuk melakukan ini, Anda dapat mengganti nama variabel.
Pada kode pertama, mari ganti nama variabel x dan v menjadi t dan p. Kemudian, karena ditempatkan dengan nama fungsi atau peta, jenis karakter dapat dikurangi.
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|t|[a,t,3,t]+(0..29).map{p=t+4;u=t*60+9+_1;[a,p,p,p,a,p,3,6,*[a,6,6,6]*(29-_1),?<,6,t,u,a,p,u,p]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
275 BHmm, sudah meningkat.
Hapus p dan ganti dengan s.
puts [6484,a=?+,0,1,3,?<,2,3,3]+[0,1].map{|t|[a,t,3,t]+(0..29).map{s=t+4;u=t*60+9+_1;[a,s,s,s,a,s,3,6,*[a,6,6,6]*(29-_1),?<,6,t,u,a,s,u,s]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,?<,3,5,6,a,2,6,2]}}$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
184 BKali ini menyusut dengan benar.
(Saya tidak tahu kenapa meningkat, jadi tolong, jika ada orang yang tahu, beri tahu kami).
Dengan demikian, melalui trial and error, kami dapat mempersingkat kode.
Tautan ke asli artikel ini ada di sini
Kami akan sangat senang jika Anda memberi tahu kami jika Anda menyukai artikel ini, apakah terjemahannya jelas, apakah bermanfaat bagi Anda?