[RUBY] [Code Golf] Entleeren Sie den Code und senden Sie ihn an AtCoder [Compressed Golf]

Kennen Sie Code Golf? Ich kenne Es ist ein Wettbewerb, Code mit so wenig Zeichen wie möglich zu schreiben.

Dieses Mal ist der 171-Byte-Code, der an AGC047 E gesendet wurde umstritten, daher möchte ich die Codekomprimierung erläutern.

Code komprimieren

Schauen Sie sich zunächst den folgenden Code an.

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

Ich kann es kaum lesen. Aber der erste ist normalerweise Ruby-Code.

#!ruby -Knrzlib

Dies ist Shebang, aber ich habe "-Kn" und "-rzlib" in den Befehlszeilenoptionen angegeben (https://docs.ruby-lang.org/ja/latest/doc/spec=2frubycmd.html). Ich werde. -Kn gibt an, dass es als Binärdatei ohne Zeichencode behandelt wird. Es hat die gleiche Bedeutung wie "# Kodierung: binär". -rzlib benötigt die zlib-Bibliothek. Es hat die gleiche Bedeutung wie require" zlib ".

Die nächste Zeile.

eval Zlib.inflate'…

Zlib.inflate ist eine Methode zum Dekomprimieren des komprimierten Codes. Sie können sehen, dass dieser Code den komprimierten Code und "eval" dekomprimiert, weil die komprimierte Zeichenfolge "" folgt.

Versuchen

Ich fand heraus, dass ich den Code komprimieren und in eine Vorlage wie diese einbetten konnte. Dazu benötigen Sie drei Schritte: (1) Code schreiben, (2) komprimieren und (3) senden. Insbesondere ist es notwendig, zwischen ① und ② zu wiederholen, um das Kompressionsverhältnis zu verringern.

1. Schreiben Sie Code

Schreiben wir zuerst den Code. (Der Inhalt des Codes spielt hier keine Rolle)

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

Die Länge dieses Codes beträgt 216 Bytes. Ich konnte es schreiben, also lasst es uns komprimieren

2. Komprimieren

Hier werden wir mit dem Skript von https://pastebin.com/TtNNhyND komprimieren.

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

Auf 194 Bytes geschrumpft!

3. Senden

Nach dem Komprimieren möchte ich es einreichen, aber es gibt ein Problem. Leider können Sie diesen Code nicht einfach kopieren, einfügen und senden. Der komprimierte Code ist binär. Der AtCoder-Übermittlungsbildschirm ist jedoch UTF-8. In vielen Fällen enthält der komprimierte Code falsche Bytes wie UTF-8. Wenn Sie ihn also so kopieren und einfügen, wie er ist, wird er verstümmelt.

Deshalb habe ich mich für DevTools entschieden, um den URI-codierten Code direkt zu senden.

Öffnen Sie den Übermittlungsbildschirm und rufen Sie DevTools auf. Lassen Sie die Registerkarte Netzwerk geöffnet.

Bitte klicken Sie in diesem Zustand auf die Schaltfläche "Senden". Die Anforderung wird in DevTools angezeigt. Wählen Sie nun die Anfrage mit dem Namen Senden aus, klicken Sie mit der rechten Maustaste und drücken Sie Kopieren ▶ Als Abruf kopieren. Der abzurufende Code wird kopiert.

Öffnen Sie einfach die Registerkarte Konsole und fügen Sie den gerade kopierten Code ein.

Sie fügen die URI-codierte Quelle nach sourceCode = ein (obwohl im Bild nicht gezeigt).

Verwenden Sie https://pastebin.com/TA35nsHZ für die URI-Codierung. (Speichern als 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

Konvertieren Sie abc047_e.rb mit deflate-uriencode.rb. Kopieren Sie die Zeichenfolge beginnend mit "% 23" in die zweite Zeile der Ausgabe und fügen Sie sie nach "sourceCode =" ein.

Sie können es senden, indem Sie es in diesem Zustand ausführen.

4. Ändern Sie den Code (um ihn noch kürzer zu machen)

Lassen Sie uns den Code verkleinern. Es gibt zwei Möglichkeiten, den komprimierten Code zu verkürzen.

1. Kürzen Sie den Originalcode
2. Erhöhen Sie das Kompressionsverhältnis

Hier werden wir hauptsächlich die zweite Methode durchführen. 1 ist eine normale Golfmethode.

Erhöhen Sie die Komprimierungsrate

Wie kann das Kompressionsverhältnis erhöht werden? Ich verwende derzeit die Deflate-Komprimierung, aber die Deflate-Komprimierung ist eine Kombination aus Lauflängenkomprimierung und Huffman-Code. Achten Sie auf diesen Huffman-Code.

Der Huffman-Code hat die Eigenschaft, dass das Kompressionsverhältnis umso höher ist, je kleiner die Entropie vor der Komprimierung ist. Die Entropie wird kleiner, wenn die Wahrscheinlichkeit des Auftretens des Codes verzerrt ist. Daher scheint die Komprimierungsrate umso höher zu sein, je stärker die Wahrscheinlichkeit des Auftretens des Zeichens verzerrt ist.

Um die Erscheinungswahrscheinlichkeit zu beeinflussen, ist es effektiv, den Zeichentyp zu reduzieren. Am einfachsten ist es, die Variable umzubenennen.

Benennen wir im ersten Code die Variablen "x" und "v" in "t" und "p" um. Dann wird es mit dem Funktionsnamen "Puts" oder "Map" abgedeckt, sodass Sie den Zeichentyp reduzieren können.

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

Das? Es hat zugenommen. Lassen Sie uns p stoppen und es in s ändern.

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

Diesmal nimmt es richtig ab. (Ich weiß nicht, warum es zugenommen hat, also machen Sie sich bitte damit vertraut.)

Auf diese Weise können Sie den Code verkleinern, indem Sie das Ausprobieren des Schreibens und Komprimierens wiederholen.

Detaillierte Hinweise usw.