Avez-vous déjà entendu parler de Code Golf ? C'est un peu comme un jeu où tout le monde essaie d'écrire du code spécifique avec le moins de caractères possible.
L'une des solutions (code de 171 octets) téléchargée dans le concours AtCoder * est largement critiquée, j'ai donc décidé de déterminer quel était le problème.
(Note du traducteur: AtCoder est une plate-forme où se déroulent divers concours entre développeurs. À en juger par le domaine .jp, la plate-forme est japonaise, mais il y a des utilisateurs du monde entier. Par exemple, au moment de la traduction de cet article, il y a 3 utilisateurs de Russie en haut du site.)
Compresser le code
Si je comprends bien, compresser le code (= réduire sa taille-poids) le raccourcit symboliquement. Les membres de Code Golf, pourrait-on dire, mettent leur âme dans la réduction de chaque caractère, de chaque octet. Et comme le but de ce concours est d'écrire le code le plus court possible, il n'y a aucune raison de ne pas le compresser.
Jetez d'abord 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 dès la première ligne, je comprends que le code est écrit en Ruby.
#!ruby -KnrzlibC'est un shebang et a -Kn et -rzlib spécifiés comme options de ligne de commande.
-Kn indique que le code écrit doit être traité comme un code binaire sans caractère. Par exemple, #coding: binary fait la même chose.
-rzlib - Requis par la bibliothèque zlib. Acronyme de require "zlib".
eval Zlib.inflate'…Ligne suivante.
Zlib.inflate est une méthode pour décompresser le code compressé. Comme vous pouvez voir qu'il y a encore une ligne après le caractère ', nous comprenons que cette partie du code décompresse le code compressé et lui applique eval.
Je vais l'essayer moi-même
J'ai pensé que ce serait bien de créer un modèle de compression de code.
Cela nécessite trois étapes: 1) écrire le code, 2) compresser le code et 3) produire le code final. À leur tour, les étapes 1 et 2 doivent être répétées pour diminuer le taux de compression.
Ecrire le code
Écrivons d'abord le code. (Eh bien, cette étape ne présage rien de bon)
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]}}Ce code a une longueur de 216 octets.
Essayons maintenant de compresser.
Compresse
En utilisant ce script, j'ai pu le réduire à 194 octets!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BSoumettre à AtCoder
J'ai compressé le code et je voulais l'envoyer, mais il y avait un problème.
Malheureusement, je ne peux pas simplement copier et coller ce code et l'envoyer tel quel. Le code généré par compression est binaire. Cependant, l'écran de soumission d'AtCoder est UTF-8. La plupart du temps, le code compressé contient des chaînes d'octets qui ne sont pas valides en UTF-8, donc si vous le copiez et collez tel quel, il sera déformé.
Je publierai donc le code encodé par URI directement en utilisant DevTools.
Ouvrons l'écran de soumission et lancons DevTools. Nous gardons la page de soumission de la solution au concours ouverte.
Lorsque tout est préparé, comme indiqué sur la capture d'écran ci-dessus, nous appuyons sur le bouton de soumission de notre solution sur le site. Les DevTools afficheront la demande que nous avons soumise.
Sélectionnez la demande appelée «soumettre» et faites un clic droit dessus, appuyez sur Copier, puis sur Copier en tant que récupération.
Ouvrez votre console et collez le code que vous venez de copier.
Coller après sourceCode = notre code encodé URI (non montré dans la capture d'écran). Nous utilisons ce script pour encoder en 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%27Convertissez agc047_e.rb en deflate-uriencode.rb.
À partir de la deuxième ligne de sortie, copiez tout après% 23 et collez après le sourceCode = ci-dessus.
Nous pouvons maintenant soumettre notre solution.
Changer le code (le rendre encore plus court)
Raccourcissons le code. Il existe deux façons de raccourcir le code après la compression.
- Réduisez le code source
- Augmenter le taux de compression
J'essaierai d'utiliser les deux méthodes. La réduction du code source est l'une des méthodes préférées des contributeurs à Code Golf.
Augmenter le taux de compression
Comment puis-je augmenter le taux de compression? Nous utilisons maintenant la compression Deflate, qui est une combinaison de compression de longueur d'exécution et de codage Huffman. Faites attention à ce code Huffman. Le code de Huffman est différent en ce que le taux de compression augmente à mesure que l'entropie diminue avant la compression. L'entropie diminue avec les probabilités d'apparition du décalage de code. Par conséquent, si la probabilité d'occurrence des codes est décalée, le taux de compression augmentera à mesure que le décalage se produit.
Un moyen efficace de réduire la probabilité d'apparition de code consiste à réduire le type de caractère. Pour ce faire, vous pouvez renommer la variable.
Dans le premier code, renommons les variables x et v en t et p. Ensuite, puisqu'il est placé avec le nom de la fonction met ou map, le type du caractère peut être réduit.
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 BHmm, il a augmenté.
Retirez p et remplacez-le par 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 BCette fois, il rétrécit correctement.
(Je ne sais pas pourquoi il a augmenté, alors s'il vous plaît, s'il y a des gens qui le savent, dites-le nous).
Ainsi, par essais et erreurs, nous avons pu raccourcir le code.
Un lien vers l'original de cet article est ici.
Nous serons très heureux si vous nous dites si vous avez aimé cet article, la traduction était-elle claire, cela vous a-t-il été utile?