[RUBY] [Code Golf] Dégonflez le code et soumettez-le à AtCoder [Compressed Golf]

Connaissez-vous le golf codé? je connais C'est un concours pour écrire du code avec le moins de caractères possible.

Cette fois, le code de 171 octets soumis à AGC047 E est controversé, donc je vais expliquer la compression de code.

Compresser le code

Tout d'abord, jetez un œil au code suivant.

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

Je peux à peine le lire. Mais le premier est généralement du code Ruby.

#!ruby -Knrzlib

C'est Shebang, mais j'ai spécifié -Kn et -rzlib dans les options de ligne de commande (https://docs.ruby-lang.org/ja/latest/doc/spec=2frubycmd.html) Je vais. -Kn indique qu'il est traité comme un binaire sans code de caractère. Il a la même signification que «# coding: binary». -rzlib nécessite la bibliothèque zlib. Il a la même signification que require" zlib ".

La ligne suivante.

eval Zlib.inflate'…

Zlib.inflate est une méthode pour décompresser le code compressé. Le fait que la chaîne compressée suive «» indique également que ce code décompresse le code compressé et «eval».

Essayer

J'ai trouvé que je pouvais compresser le code et l'intégrer dans un modèle comme celui-ci. Pour ce faire, vous avez besoin de trois étapes: (1) écrire le code, (2) compresser et (3) soumettre. En particulier, il est nécessaire de répéter entre ① et ② afin de réduire le taux de compression.

1. Écrivez le code

Écrivons d'abord le code. (Le contenu du code n'a pas d'importance ici)

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

La longueur de ce code est de 216 octets. J'ai pu l'écrire, alors compressons-le

2. Compresser

Ici, nous allons compresser en utilisant le script de https://pastebin.com/TtNNhyND.

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

Réduit à 194 octets!

3. Soumettre

Après la compression, j'aimerais le soumettre, mais il y a un problème. Malheureusement, vous ne pouvez pas simplement copier et coller ce code et le soumettre. Le code compressé est binaire. Cependant, l'écran de soumission d'AtCoder est UTF-8. Dans de nombreux cas, le code compressé contient des octets incorrects comme UTF-8, donc si vous le copiez et collez tel quel, il sera déformé.

J'ai donc décidé d'utiliser DevTools pour soumettre directement le code encodé en URI.

Ouvrez l'écran de soumission et faites apparaître DevTools. Gardez l'onglet Réseau ouvert.

Veuillez appuyer sur le bouton Soumettre dans cet état. La demande apparaît dans DevTools. Sélectionnez maintenant la demande nommée soumettre, cliquez avec le bouton droit et appuyez sur Copier ▶ Copier comme récupération. Le code à récupérer est copié.

Ouvrez simplement l'onglet Console et collez le code que vous venez de copier.

Vous allez coller la source encodée en URI après sourceCode = (bien que non affiché dans l'image).

Utilisez https://pastebin.com/TA35nsHZ pour le codage URI. (Enregistrer sous 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

Convertissez abc047_e.rb avec deflate-uriencode.rb. Copiez la chaîne commençant par % 23 sur la deuxième ligne de la sortie et collez-la après le sourceCode =.

Vous pouvez le soumettre en l'exécutant dans cet état.

4. Modifiez le code (pour le rendre encore plus court)

Réduisons le code. Il existe deux façons de raccourcir le code compressé.

1. Raccourcissez le code d'origine
2. Augmentez le taux de compression

Ici, nous allons principalement faire la deuxième méthode. 1 est une méthode de golf normale.

Augmenter le taux de compression

Comment le taux de compression peut-il augmenter? J'utilise la compression Deflate en ce moment, mais la compression Deflate est une combinaison de compression de longueur d'exécution et de code Huffman. Faites attention à ce code Huffman.

Le code de Huffman a la caractéristique que plus l'entropie avant compression est petite, plus le taux de compression est élevé. L'entropie devient plus petite à mesure que la probabilité d'occurrence du code est biaisée. Par conséquent, il semble que plus la probabilité d'apparition du signe est biaisée, plus le taux de compression sera élevé.

Pour biaiser la probabilité d'apparition, il est efficace de réduire le type de caractère. Le moyen le plus simple est de renommer la variable.

Dans le premier code, renommons les variables «x» et «v» en «t» et «p». Ensuite, il sera recouvert du nom de la fonction met ou map, afin que vous puissiez réduire le type de caractère.

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

cette? Il a augmenté. Arrêtons p et changeons-le en 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

Cette fois, il diminue correctement. (Je ne sais pas pourquoi il a augmenté, alors veuillez vous familiariser avec.)

De cette façon, vous pouvez réduire le code en répétant les essais et erreurs d'écriture et de compression.

Notes détaillées, etc.