Jogando golfe com código: compressão de código e submissão à competição da plataforma AtCoder

Olá, Habr! Apresento a sua atenção a tradução do artigo " 【コ ー ド ゴ ル フ】 コ ー ド を Esvaziar 圧 縮 し て AtCoder に 提出 す る 【圧 縮 縮 ゴ ル フ】 ".



Você já ouviu falar do Code Golf ? É como um jogo em que todos tentam escrever um código específico com o mínimo de caracteres possível.



Uma das soluções (código de 171 bytes) enviada para o concurso AtCoder * foi amplamente criticada, então decidi descobrir qual era o problema.



(Nota do tradutor: AtCoder é uma plataforma onde várias competições entre desenvolvedores são realizadas. A julgar pelo domínio .jp, a plataforma é japonesa, mas há usuários de todo o mundo. Por exemplo, no momento da tradução deste artigo, havia 3 usuários da Rússia no topo do site.)

Código de compressão

Pelo que entendi, compactar o código (= reduzir seu tamanho e peso) o encurta simbolicamente. Os membros do Code Golf, pode-se dizer, colocam suas almas na redução de cada personagem, cada byte. E como o objetivo dessa competição é escrever o código mais curto possível, não há razão para não compactá-lo.



Dê uma olhada no código a seguir primeiro.

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

Eu mal consigo ler. Mas desde a primeira linha, entendi que o código é escrito em Ruby.

#!ruby -Knrzlib

É um shebang e tem -Kn e -rzlib especificados como opções de linha de comando.



-Kn indica que o código escrito deve ser tratado como um código binário sem caracteres. Por exemplo, #coding: binary faz a mesma coisa.



-rzlib - Requerido pela biblioteca zlib. Acrônimo para require "zlib".

eval Zlib.inflate'…

Próxima linha.



Zlib.inflate é um método para descompactar código compactado. Como você pode ver que ainda há uma linha após o caractere ', entendemos que esta parte do código descompacta o código compactado e aplica a avaliação a ele.

Vou tentar sozinho

Achei que seria bom criar um modelo de compressão de código.



Isso requer três etapas: 1) escrever o código, 2) compactar o código e 3) produzir o código final. Por sua vez, os passos 1 e 2 devem ser repetidos para diminuir a taxa de compressão.

Escrevendo o código

Vamos escrever o código primeiro. (Bem, esta etapa não é um bom presságio)

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 tem 216 bytes.



Agora vamos tentar comprimir.

Comprimir

Usando esse script, consegui reduzi-lo para 194 bytes!

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

Enviar para AtCoder

Compactei o código e quis enviá-lo, mas havia um problema.



Infelizmente, não posso simplesmente copiar e colar este código e enviá-lo como está. O código gerado pela compressão é binário. No entanto, a tela de envio do AtCoder é UTF-8. Na maioria das vezes, o código compactado contém cadeias de bytes que não são válidas em UTF-8, portanto, se você copiar e colar como está, ficará distorcido.



Então, vou postar o código codificado URI diretamente usando DevTools.



Vamos abrir a tela de envio e lançar DevTools. Mantemos aberta a página de envio da solução ao concurso.







Quando tudo estiver preparado, conforme indicado na imagem acima, pressionamos o botão para submeter nossa solução no site. O DevTools exibirá a solicitação enviada.



Selecione a solicitação chamada “enviar” e clique com o botão direito sobre ela, pressione Copiar e Copiar como busca.







Abra seu console e cole o código que você acabou de copiar.







Cole após sourceCode = nosso código codificado de URI (não mostrado na captura de tela). Usamos este script para codificar para URI . (Salve 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%27

Converta agc047_e.rb em deflate-uriencode.rb.



Na segunda linha de saída, copie tudo após% 23 e cole após sourceCode = acima.







Agora podemos enviar nossa solução.

Alterar o código (tornando-o ainda mais curto)

Vamos encurtar o código. Existem duas maneiras de encurtar o código após a compressão.

• Reduza o código-fonte
• Aumentar a taxa de compressão

Vou tentar usar os dois métodos. Reduzir o código-fonte é a forma favorita dos colaboradores do Code Golf.

Aumentando a taxa de compressão

Como posso aumentar a taxa de compressão? Agora usamos a compressão Deflate, que é uma combinação de compressão run-length e codificação Huffman. Preste atenção a este código de Huffman. O código de Huffman é diferente porque a taxa de compressão aumenta à medida que a entropia diminui antes da compressão. A entropia diminui à medida que as probabilidades de aparecimento do código mudam. Portanto, se a probabilidade de ocorrência de códigos for alterada, a taxa de compressão aumentará conforme a mudança ocorrer.



Uma maneira eficaz de reduzir a probabilidade de exibição de código é reduzir o tipo de caractere. Para fazer isso, você pode renomear a variável.



No primeiro código, vamos renomear as variáveis ​​x e v para t e p. Então, como ele é colocado com o nome da função puts ou map, o tipo do caractere pode ser reduzido.

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

Hmm, aumentou.



Remova p e substitua por 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

Desta vez, ele encolhe corretamente.



(Não sei porque aumentou, então por favor, se tiver gente que saiba, diga-nos).

Assim, por tentativa e erro, conseguimos encurtar o código.



Um link para o original deste artigo está aqui.



Ficaremos muito felizes se você nos disser se gostou deste artigo, a tradução foi clara, foi útil para você?