【コードゴルフ】コードをDeflate圧縮してAtCoderに提出する【圧縮ゴルフ】

コードゴルフを知っていますか？僕は知っています。できるだけ少ない文字数でコードを書く競技です。

この度、AGC047 Eに提出された171 Bytesのコードが物議を醸しているので、コードの圧縮について解説しようと思います。

コードを圧縮する

コードを圧縮すると、コードが短くなります、たぶん。ご存知のように、コードゴルファーは1文字1バイト減らすことに心血を注ぎ込んでいますから、圧縮すると短くなるなら圧縮しない手はないでしょう。

では、次のコードを見てください。これは圧縮されたコードの例です。

#!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'

ほとんど読めないですね。
ですが、最初の方は普通にRubyのコードです。

#!ruby -Knrzlib

これはShebangですが、コマンドラインオプションで-Knと-rzlibを指定しています。
-Knは文字コードがないバイナリとして扱うことを示します。#coding:binaryと同じ意味です。
-rzlibはzlibライブラリをrequireしています。require "zlib"と同じ意味です。

次の行です。

eval Zlib.inflate'…

Zlib.inflateは圧縮したコードを解凍するメソッドです。'以降に圧縮された文字列が続いていることからも、このコードは圧縮されたコードを解凍してevalしていることがわかります。

やってみる

コードを圧縮してこのようなテンプレートに埋め込めばよいことがわかりました。
これを実際にするには、①コードを書く、②圧縮する、③提出する、の3つのステップが必要です。
特に、圧縮率を下げるためには①と②の間を反復することが必要になります。

1. コードを書く

まずはコードを書いてみましょう。（ここではコードの内容は問題ではないです）

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

このコードの長さは216 Bytesです。
書けたので、圧縮してみましょう

2. 圧縮する

ここでは、 https://pastebin.com/TtNNhyND のスクリプトを使って圧縮していきます。

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

194 Bytesに縮みました！

3. 提出する

圧縮したら、さあ提出といきたいところですが、ひとつ問題があります。
残念ながら、このコードをコピペしてそのまま提出というわけにはいきません。圧縮して生成されたコードはバイナリです。しかし、AtCoderの提出画面はUTF-8です。多くの場合、圧縮してできたコードはUTF-8として正しくないバイト列を含んでいるので、そのままコピペすると化けてしまいます。

そこで、DevToolsを使って、URIエンコードしたコード直接提出することにします。

提出画面を開いて、DevToolsを出します。ネットワークタブを開いておいてください。

この状態で提出ボタンを押してください。DevToolsにリクエストが表示されます。
ここで、submitという名前のリクエストを選んで右クリックし、Copy▶Copy as fetchを押してください。fetchするコードがコピーされます。

そのままConsoleタブを開いて、今コピーされたコードを貼り付けます。

（画像には表示されていませんが）sourceCode=の後ろにURIエンコードされたソースを貼り付けていくことになります。

URIエンコードするために https://pastebin.com/TA35nsHZ を使います。（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

deflate-uriencode.rbでagc047_e.rbを変換します。
出力の2行目の%23から始まる文字列をコピーして、先程のsourceCode=の後ろに貼り付けてください。

この状態で実行すると提出することができます。

4. コードを修正する（さらに短くなるように）

コードを縮めましょう。圧縮後のコードが短くなるためには、２つの方法があります。

1. 元のコードを短くする
2. 圧縮率を上げる

ここでは主に2の方法をやっていきます。1は普通のゴルフの方法ですね。

圧縮率を上げる

どうすれば圧縮率が上がるでしょうか。今、Deflate圧縮を使っていますが、Deflate圧縮はランレングス圧縮とハフマン符号の組み合わせです。このハフマン符号の方に注目します。

ハフマン符号は、圧縮前のエントロピーが小さい程圧縮率が高くなる特徴があります。エントロピーは、符号の出現確率が偏っている程小さくなります。なので、符号の出現確率を偏らせれば偏らせる程圧縮率が上がるということになりそうです。

出現確率を偏らせるには、文字種を減らしたりするのが有効です。最も簡単な方法としては、変数名を変更するなどです。

最初のコードで、変数xやvの変数名を変更してtやpにしてみましょう。すると、関数名のputsやmapと被るので、文字種を減らすことができます。

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

あれ？増えてしまいました。
ではpはやめて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

今度はちゃんと減っています。（なぜ増えたのかわからないので、詳しい方お願いします）

このように、書いて圧縮する試行錯誤を繰り返すことで、コードを縮めることができます。