[Code golf] Deflate the code and submit it to AtCoder [Compressed golf]

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

This time, the 171 Bytes code submitted to AGC047 E is controversial, so I will explain about code compression.

Compress the code

First, take a look at the following code.

#!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 the first one is usually Ruby code.

#!ruby -Knrzlib

This is Shebang, but I specified -Kn and -rzlib in the Command Line Options (https://docs.ruby-lang.org/ja/latest/doc/spec=2frubycmd.html) I will. -Kn indicates that it is treated as a binary without a character code. It has the same meaning as # coding: binary. -rzlib requires the zlib library. It has the same meaning as require" zlib ".

The next line.

eval Zlib.inflate'…

Zlib.inflate is a method to decompress the compressed code. From the fact that the compressed string follows ', we can see that this code decompresses the compressed code and ʻeval`.

Try

I found that I could compress the code and embed it in a template like this. To do this, you need three steps: (1) write code, (2) compress, and (3) submit. In particular, it is necessary to repeat between ① and ② in order to reduce the compression rate.

1. Write code

Let's write the code first. (The content of the code doesn't matter here)

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. Now that I've written it, let's compress it

2. Compress

Here, we will compress using the script of https://pastebin.com/TtNNhyND.

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

Shrinked to 194 Bytes!

3. Submit

After compressing, I would like to submit it, but there is one problem. Unfortunately, you can't just copy and paste this code and submit it as is. The compressed code is binary. However, the AtCoder submission screen is UTF-8. In many cases, the compressed code contains incorrect bytes as UTF-8, so if you copy and paste it as it is, it will be garbled.

So I decided to use DevTools to submit the URI-encoded code directly.

Open the submission screen and bring up DevTools. Keep the Network tab open.

Please press 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.

Just open the Console tab and paste the code you just copied.

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

Use https://pastebin.com/TA35nsHZ for URI encoding. (Save it 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 abc047_e.rb with deflate-uriencode.rb. Copy the string starting with % 23 on the second line of the output and paste it after the previoussourceCode =.

You can submit it by executing it in this state.

4. Modify the code (to make it even shorter)

Let's shrink the code. There are two ways to shorten the compressed code.

1. Shorten the original code
2. Increase the compression ratio

Here, we will mainly do the second method. 1 is a normal golf method, isn't it?

Increase compression ratio

How can the compression ratio increase? I'm using Deflate compression right now, but Deflate compression is a combination of run-length compression and Huffman coding. Pay attention to this Huffman code.

The Huffman code has the characteristic that the smaller the entropy before compression, the higher the compression rate. The entropy becomes smaller as the probability of occurrence of the sign is biased. Therefore, it seems that the more the sign appearance probability is biased, the higher the compression rate will be.

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

In the first code, let's rename the variables x and v to t and p. Then, it will be covered with the function name puts or map, so you can reduce the character type.

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 increased, so please be familiar with it.)

In this way, you can shrink the code by repeating the trial and error of writing and compressing.

Detailed notes, etc.