Have you ever heard of Code Golf ? It's kind of like a game where everyone tries to write specific code with as few characters as possible.
One of the solutions (171-byte code) uploaded to the AtCoder * contest is widely criticized, so I decided to figure out what the problem was.
(Translator's note: AtCoder is a platform where various competitions are held among developers. Judging by the .jp domain, the platform is Japanese, but there are users from all over the world. For example, at the time of translation of this article, there are 3 users from Russia in the top of the site.)
Compressing the code
As I understand it, compressing the code (= reducing its size-weight) shortens it symbolically. Members of Code Golf, one might say, put their souls into the reduction of each character, each byte. And since the goal of this competition is to write the shortest possible code, there is no reason not to compress it.
Take a look at the following code first.
#!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'I can hardly read it. But from the first line, I understand that the code is written in Ruby.
#!ruby -KnrzlibIt is a shebang and has -Kn and -rzlib specified as command line options.
-Kn indicates that the written code should be treated as a binary, characterless code. For example, #coding: binary does the same thing.
-rzlib - Required by the zlib library. Acronym for require "zlib".
eval Zlib.inflate'…Next line.
Zlib.inflate is a method for unpacking compressed code. Since you can see that there is still a line after the 'character, we understand that this part of the code unpacks the compressed code and applies eval to it.
I'll try it myself
I thought it would be nice to create a code compression template.
This requires three steps: 1) write the code, 2) compress the code, and 3) produce the final code. In turn, steps 1 and 2 must be repeated to decrease the compression ratio.
Writing the code
Let's write the code first. (Well, this step does not bode well)
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]}}This code is 216 bytes long.
Now let's try to compress.
Compress
Using this script, I was able to reduce it to 194 bytes!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BSubmit to AtCoder
I compressed the code and wanted to send it, but there was one problem.
Unfortunately, I can't just copy and paste this code and submit it as it is. The code generated by compression is binary. However, the AtCoder submit screen is UTF-8. Most of the time, compressed code contains byte strings that are not valid in UTF-8, so if you copy and paste it as is, it will be garbled.
So I will post the URI encoded code directly using DevTools.
Let's open the submit screen and launch DevTools. We keep the page for submitting the solution to the contest open.
When everything has been prepared, as indicated in the screenshot above, we press the button for submitting our solution on the site. DevTools will display the request we submitted.
Select the request called “submit” and right-click on it, press Copy, then Copy as fetch.
Open your console and paste in the code you just copied.
Paste after sourceCode = our URI encoded code (not shown in the screenshot). We use this script to encode to URI . (Save as 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%27Convert agc047_e.rb to deflate-uriencode.rb.
From the second line of output, copy everything after% 23 and paste after the above sourceCode =.
Now we can submit our solution.
Changing the code (making it even shorter)
Let's shorten the code. There are two ways to shorten the code after compression.
- Shrink the source code
- Increase compression ratio
I'll try to use both methods. Shrinking source code is a favorite way of Code Golf contributors.
Increasing the compression ratio
How can I increase the compression ratio? We now use Deflate compression, which is a combination of run-length compression and Huffman coding. Pay attention to this Huffman code. The Huffman code is different in that the compression ratio increases as the entropy decreases before compression. Entropy decreases as the probabilities of the appearance of the code shift. Therefore, if the probability of occurrence of codes is shifted, the compression ratio will increase as the shift occurs.
An effective way to reduce the likelihood of code appearing is to reduce the character type. To do this, you can rename the variable.
In the first code, let's rename the variables x and v to t and p. Then, since it is placed with the function name puts or map, the type of the character can be reduced.
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, it has increased.
Remove p and replace it with 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 BThis time it shrinks correctly.
(I do not know why it has increased, so please, if there are people who know, tell us).
Thus, through trial and error, we were able to shorten the code.
A link to the original of this article is here
We will be very glad if you tell us if you liked this article, was the translation clear, was it useful to you?