コードゴルフのプレイ：コードの圧縮とAtCoderプラットフォームコンペティションへの提出

こんにちは、Habr！記事「【コードゴルフ】コードをデフレート圧べしてAtCoderに立する【圧締めゴルフ】の翻訳をご紹介します。コードゴルフ



について聞いたことがありますか？これは、誰もができるだけ少ない文字で特定のコードを書き込もうとするゲームのようなものです。 AtCoder *コンテストにアップロードされたソリューションの1つ（171バイトのコード）は広く批判されているので、私は問題が何であるかを理解することにしました。（翻訳者注：AtCoderは、開発者間でさまざまな競争が行われるプラットフォームです。.jpドメインから判断すると、プラットフォームは日本語ですが、世界中からユーザーがいます。たとえば、この記事の翻訳時点では、サイトの上部にロシアから3人のユーザーがいます。）

コードの圧縮

私が理解しているように、コードを圧縮する（=サイズと重みを減らす）と、シンボリックに短縮されます。コードゴルフのメンバーは、各キャラクター、各バイトの削減に魂を注いでいると言うかもしれません。そして、この競争の目標は可能な限り短いコードを書くことなので、それを圧縮しない理由はありません。



最初に次のコードを見てください。

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

これはシェバンであり、コマンドラインオプションとして-Knと-rzlibが指定されています。



-Knは、記述されたコードをバイナリの文字のないコードとして扱う必要があることを示します。たとえば、＃coding：binaryも同じことをします。



-rzlib-zlibライブラリに必要です。require "zlib"の略語。

eval Zlib.inflate'…

次の行。



Zlib.inflateは、圧縮されたコードを解凍するためのメソッドです。'文字の後にまだ行があることがわかるので、コードのこの部分が圧縮されたコードを解凍し、それにevalを適用することを理解しています。

自分でやってみます

コード圧縮テンプレートを作成するといいと思いました。



これには3つのステップが必要です：1）コードを書く、2）コードを圧縮する、3）最終的なコードを作成する。次に、圧縮率を下げるために、手順1と2を繰り返す必要があります。

コードを書く

最初にコードを書いてみましょう。（まあ、このステップは良い前兆ではありません）

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バイトです。



それでは、圧縮してみましょう。

圧縮

このスクリプトを使用して、194バイトに減らすことができました。

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

AtCoderに送信

コードを圧縮して送信したかったのですが、問題が1つありました。



残念ながら、このコードをコピーして貼り付けてそのまま送信することはできません。圧縮によって生成されるコードはバイナリです。ただし、AtCoderの送信画面はUTF-8です。ほとんどの場合、圧縮されたコードにはUTF-8では無効なバイト文字列が含まれているため、そのままコピーして貼り付けると文字化けします。



そこで、DevToolsを使用してURIでエンコードされたコードを直接投稿します。



送信画面を開いてDevToolsを起動しましょう。コンテストにソリューションを提出するためのページを開いたままにします。







上のスクリーンショットに示されているように、すべての準備が整ったら、ボタンを押してサイトにソリューションを送信します。 DevToolsは、送信したリクエストを表示します。



「送信」というリクエストを選択して右クリックし、[コピー]、[フェッチとしてコピー]の順に押します。







コンソールを開き、コピーしたコードを貼り付けます。







sourceCode = URIでエンコードされたコードの後に​​貼り付けます（スクリーンショットには表示されていません）。このスクリプトを使用してURIにエンコードします。（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

agc047_e.rbをdeflate-uriencode.rbに変換します。



出力の2行目から、％23以降のすべてをコピーし、上記のsourceCode =の後に貼り付けます。







これで、ソリューションを送信できます。

コードを変更する（さらに短くする）

コードを短くしましょう。圧縮後にコードを短縮する方法は2つあります。

• ソースコードを縮小する
• 圧縮率を上げる

両方の方法を試してみます。ソースコードの縮小は、CodeGolfの貢献者のお気に入りの方法です。

圧縮率を上げる

どうすれば圧縮率を上げることができますか？現在、ランレングス圧縮とハフマンコーディングを組み合わせたデフレート圧縮を使用しています。このハフマンコードに注意してください。ハフマンコードは、圧縮前にエントロピーが減少するにつれて圧縮率が増加するという点で異なります。コードの出現確率がシフトするにつれて、エントロピーは減少します。したがって、コードの発生確率がシフトすると、シフトが発生するにつれて圧縮率が増加します。



コードが表示される可能性を減らす効果的な方法は、文字タイプを減らすことです。これを行うには、変数の名前を変更します。



最初のコードで、変数xとvの名前をtとpに変更しましょう。次に、関数名putsまたはmapで配置されるため、文字の種類を減らすことができます。

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に置き換えます。

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

今回は正しく縮みます。



（なぜ増加したのかわかりませんので、ご存知の方がいらっしゃいましたら教えてください）。

このように、試行錯誤の結果、コードを短縮することができました。



この記事の原本へのリンクはここにあり



ますこの記事が気に入った場合、翻訳は明確でしたか、役に立ちましたか？