[Ruby] [Code Golf] Deflate the code and submit it to AtCoder [Compress Golf]

3 minute read

Do you know code golf? I know It is a competition to write codes with as few characters as possible.

This time, 171 Bytes code submitted to AGC047 E is controversial, so I’ll explain compression of the code.

Compress code

First, take a look at the following code.

#!ruby -Knrzlib
eval Zlib.inflate'x�=�Q
.D.OS.c

] r....Delete.By.
               ��O{4..ii aQ(`}cB.I2e...IeT.јL> ����) u, �p �S�W. �H ~.�,�:
z:Ӊ��g�O7ʲ��vQ�1h�^<����=&�\u7 '

I can hardly read it. But the first one is usually Ruby code.

#!ruby -Knrzlib

This is Shebang, but I have specified -Kn and -rzlib in command line options I will. -Kn indicates to treat as binary without character code. This is the same as #coding:binary. -rzlib requires the zlib library. This is the same as require "zlib".

Next line.

eval Zlib.inflate'…

Zlib.inflate is a method to decompress compressed code. It can be seen that this code also decompresses the compressed code and eval from the fact that the compressed string follows after the '.

Try

I found that I could compress the code and embed it in a template like this. To actually do this, there are 3 steps: 1) write code, 2) compress, and 3) submit. Especially, in order to reduce the compression rate, it is necessary to repeat between ① and ②.

1. Write the code

First, let’s write the code. (Here the code content doesn’t matter)

agc047_e.rb


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]}}

The length of this code is 216 Bytes. I could write it, so let’s compress it

2. Compress

Here, we will use the script https://pastebin.com/TtNNhyND to compress it.

$ ruby deflate.rb agc047_e.rb >agc047_e.min.rb
194 B

Shrink to 194 Bytes!

3. Submit

Once compressed, I would like to submit it, but there is one problem. Unfortunately, I can’t just copy-paste this code and submit it as-is. The code generated by compression is binary. However, the submission screen of AtCoder is UTF-8. In most cases, the compressed code contains bytes that are not UTF-8-correct, so it will be garbled if you copy and paste it as it is.

Therefore, I will directly submit the URI-encoded code using DevTools.

Open the submission screen and launch DevTools. Keep the network tab open. ![Screenshot _2020-08-12_14-10-39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/638261/874ba1d8-a322-e483-(0aba-31c3763e90ba.png)

Please push the submit button in this state. The request appears in DevTools. Now select the request named submit, right click and press Copy ▶ Copy as fetch. The code to fetch is copied.

rsz_screenshot_2020-08-12_14-25-02.png

Just open the Console tab and paste the code you just copied. ![Screenshot_2020-08-12_14-31-50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/638261/54532777-b227-1f6b-(c1c5-ede2a2dddbfd.png)

You will paste the URI-encoded source after the sourceCode= (not shown in the image).

Use https://pastebin.com/TA35nsHZ for URI encoding. (Please 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%27

Convert agc047_e.rb with deflate-uriencode.rb. Copy the string beginning with %23 in the second line of output and paste it after the sourceCode= above.

Screenshot _2020-08-12_14-38-54.png

You can submit by executing in this state.

4. Modify the code (to make it shorter)

Let’s shorten the code. There are two ways to shorten the code after compression.

  1. Shorten the original code
  2. Increase compression rate

There are mainly two methods here. 1 is a normal golf method.

increase compression

How can I improve the compression ratio? I am currently using Deflate compression, which is a combination of run length compression and Huffman coding. Pay attention to this Huffman code.

The Huffman code is characterized in that the compression rate increases as the entropy before compression decreases. Entropy becomes smaller as the probability of code appearance is biased. Therefore, if the appearance probabilities of the codes are biased, it seems that the compression rate increases as the bias is biased.

To bias the appearance probability, it is effective to reduce the character type. The easiest way is to rename the variable.

Let’s change the variable names of the variables x and v to t and p in the first code. Then, since it will be covered by puts and map of the function name, the character type can be reduced.

agc047_e.rb


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 B

that? It has increased. Let’s stop p and change it to s.

agc047_e.rb


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 B

This time it is decreasing properly. (I don’t know why it has increased, so please ask for more information)

By repeating trial and error of writing and compressing, you can shorten the code.

Detailed notes