¿Alguna vez has oído hablar de Code Golf ? Es como un juego en el que todos intentan escribir un código específico con la menor cantidad de caracteres posible.
Una de las soluciones (código de 171 bytes) cargada en el concurso AtCoder * es ampliamente criticada, así que decidí averiguar cuál era el problema.
(Nota del traductor: AtCoder es una plataforma donde se llevan a cabo varios concursos entre desarrolladores. A juzgar por el dominio .jp, la plataforma es japonesa, pero hay usuarios de todo el mundo. Por ejemplo, en el momento de la traducción de este artículo, hay 3 usuarios de Rusia en la parte superior del sitio).
Comprimir código
Según tengo entendido, comprimir el código (= reducir su tamaño-peso) lo acorta simbólicamente. Los miembros de Code Golf, se podría decir, ponen su alma en la reducción de cada carácter, cada byte. Y dado que el objetivo de esta competencia es escribir el código más corto posible, no hay razón para no comprimirlo.
Primero eche un vistazo al siguiente código.
#!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'Apenas puedo leerlo. Pero desde la primera línea, entiendo que el código está escrito en Ruby.
#!ruby -KnrzlibEs un shebang y tiene -Kn y -rzlib especificados como opciones de línea de comando.
-Kn indica que el código escrito debe tratarse como un código binario sin caracteres. Por ejemplo, #coding: binary hace lo mismo.
-rzlib: lo requiere la biblioteca zlib. Acrónimo de require "zlib".
eval Zlib.inflate'…Línea siguiente.
Zlib.inflate es un método para descomprimir código comprimido. Como puede ver que todavía hay una línea después del carácter ', entendemos que esta parte del código descomprime el código comprimido y le aplica eval.
Lo intentaré yo mismo
Pensé que sería bueno crear una plantilla de compresión de código.
Esto requiere tres pasos: 1) escribir el código, 2) comprimir el código y 3) producir el código final. A su vez, los pasos 1 y 2 deben repetirse para disminuir la relación de compresión.
Escribiendo el código
Primero escribamos el código. (Bueno, este paso no augura nada bueno)
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]}}Este código tiene 216 bytes de longitud.
Ahora intentemos comprimir.
Comprimir
¡Usando este script, pude reducirlo a 194 bytes!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BEnviar a AtCoder
Comprimí el código y quería enviarlo, pero había un problema.
Desafortunadamente, no puedo simplemente copiar y pegar este código y enviarlo como está. El código generado por compresión es binario. Sin embargo, la pantalla de envío de AtCoder es UTF-8. La mayoría de las veces, el código comprimido contiene cadenas de bytes que no son válidas en UTF-8, por lo que si lo copia y pega como está, se distorsionará.
Así que publicaré el código codificado con URI directamente usando DevTools.
Abramos la pantalla de envío y lancemos DevTools. Mantenemos abierta la página de envío de la solución al concurso.
Cuando todo ha sido preparado, como se indica en la captura de pantalla anterior, presionamos el botón para enviar nuestra solución en el sitio. DevTools mostrará la solicitud que enviamos.
Seleccione la solicitud llamada "enviar" y haga clic derecho sobre ella, presione Copiar, luego Copiar como buscar.
Abra su consola y pegue el código que acaba de copiar.
Pegar después de sourceCode = nuestro código codificado URI (no se muestra en la captura de pantalla). Usamos este script para codificar en URI . (Guardar como 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%27Convierta agc047_e.rb en deflate-uriencode.rb.
Desde la segunda línea de salida, copie todo después de% 23 y péguelo después del sourceCode = anterior.
Ahora podemos enviar nuestra solución.
Cambiar el código (hacerlo aún más corto)
Acortemos el código. Hay dos formas de acortar el código después de la compresión.
- Reducir el código fuente
- Incrementar la relación de compresión
Intentaré usar ambos métodos. Reducir el código fuente es una de las formas favoritas de los colaboradores de Code Golf.
Aumento de la relación de compresión
¿Cómo puedo aumentar la relación de compresión? Ahora usamos la compresión Deflate, que es una combinación de compresión de longitud de ejecución y codificación Huffman. Preste atención a este código de Huffman. El código de Huffman es diferente en que la relación de compresión aumenta a medida que la entropía disminuye antes de la compresión. La entropía disminuye a medida que cambian las probabilidades de aparición del código. Por lo tanto, si se cambia la probabilidad de aparición de códigos, la relación de compresión aumentará a medida que se produzca el cambio.
Una forma eficaz de reducir la probabilidad de que aparezca código es reducir el tipo de carácter. Para hacer esto, puede cambiar el nombre de la variable.
En el primer código, cambiemos el nombre de las variables xyv por t y p. Entonces, dado que se coloca con el nombre de la función put o map, se puede reducir el tipo de carácter.
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, ha aumentado.
Quite py reemplácelo con 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 BEsta vez se encoge correctamente.
(No sé por qué ha aumentado, así que por favor, si hay gente que lo sepa, díganos).
Por lo tanto, a través de prueba y error, pudimos acortar el código.
Un enlace al original de este artículo está aquí.
Estaremos muy contentos si nos dice si le gustó este artículo, ¿fue clara la traducción, le resultó útil?