Haben Sie jemals von Code Golf gehört ? Es ist wie in einem Spiel, in dem jeder versucht, bestimmten Code mit so wenig Zeichen wie möglich zu schreiben.
Eine der Lösungen (171-Byte-Code), die auf den AtCoder * -Wettbewerb hochgeladen wurden, wird häufig kritisiert, daher habe ich mich entschlossen, das Problem herauszufinden.
(Anmerkung des Übersetzers: AtCoder ist eine Plattform, auf der verschiedene Wettbewerbe unter Entwicklern stattfinden. Gemessen an der .jp-Domain ist die Plattform japanisch, aber es gibt Benutzer aus der ganzen Welt. Zum Zeitpunkt der Übersetzung dieses Artikels befinden sich beispielsweise 3 Benutzer aus Russland oben auf der Website.)
Code komprimieren
So wie ich es verstehe, verkürzt das Komprimieren des Codes (= Reduzieren seines Größengewichts) ihn symbolisch. Man könnte sagen, Mitglieder von Code Golf setzen ihre Seele in die Reduzierung jedes Zeichens, jedes Bytes. Und da das Ziel dieses Wettbewerbs darin besteht, den kürzestmöglichen Code zu schreiben, gibt es keinen Grund, ihn nicht zu komprimieren.
Schauen Sie sich zuerst 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 aus der ersten Zeile verstehe ich, dass der Code in Ruby geschrieben ist.
#!ruby -KnrzlibEs ist ein Shebang und hat -Kn und -rzlib als Befehlszeilenoptionen angegeben.
-Kn gibt an, dass der geschriebene Code als binärer, zeichenloser Code behandelt werden soll. Zum Beispiel macht #coding: binary dasselbe.
-rzlib - Erforderlich für die zlib-Bibliothek. Akronym für erfordern "zlib".
eval Zlib.inflate'…Nächste Zeile.
Zlib.inflate ist eine Methode zum Entpacken von komprimiertem Code. Da Sie sehen können, dass nach dem Zeichen 'noch eine Zeile steht, verstehen wir, dass dieser Teil des Codes den komprimierten Code entpackt und eval auf ihn anwendet.
Ich werde es selbst versuchen
Ich dachte, es wäre schön, eine Codekomprimierungsvorlage zu erstellen.
Dies erfordert drei Schritte: 1) Schreiben des Codes, 2) Komprimieren des Codes und 3) Erstellen des endgültigen Codes. Die Schritte 1 und 2 müssen wiederum wiederholt werden, um das Kompressionsverhältnis zu verringern.
Den Code schreiben
Schreiben wir zuerst den Code. (Nun, dieser Schritt ist kein gutes Zeichen)
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]}}Dieser Code ist 216 Byte lang.
Versuchen wir nun zu komprimieren.
Kompresse
Mit diesem Skript konnte ich es auf 194 Bytes reduzieren!
$ ruby deflate.rb agc047_e.rb > agc047_e.min.rb
194 BBei AtCoder einreichen
Ich habe den Code komprimiert und wollte ihn senden, aber es gab ein Problem.
Leider kann ich diesen Code nicht einfach kopieren, einfügen und unverändert senden. Der durch Komprimierung erzeugte Code ist binär. Der AtCoder-Übermittlungsbildschirm ist jedoch UTF-8. In den meisten Fällen enthält komprimierter Code Byte-Zeichenfolgen, die in UTF-8 nicht gültig sind. Wenn Sie ihn also so kopieren und einfügen, wie er ist, wird er verstümmelt.
Also werde ich den URI-codierten Code direkt mit DevTools veröffentlichen.
Öffnen Sie den Sendebildschirm und starten Sie DevTools. Wir halten die Seite für die Einreichung der Lösung für den Wettbewerb offen.
Wenn alles vorbereitet ist, wie im obigen Screenshot gezeigt, drücken wir die Taste, um unsere Lösung auf der Website einzureichen. DevTools zeigt die von uns gesendete Anfrage an.
Wählen Sie die Anfrage mit dem Namen "Senden" aus und klicken Sie mit der rechten Maustaste darauf, drücken Sie "Kopieren" und dann "Als Abruf kopieren".
Öffnen Sie Ihre Konsole und fügen Sie den gerade kopierten Code ein.
Einfügen nach sourceCode = unser URI-codierter Code (im Screenshot nicht gezeigt). Wir verwenden dieses Skript , um in URI zu codieren . (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%27Konvertieren Sie agc047_e.rb in deflate-uriencode.rb.
Kopieren Sie in der zweiten Ausgabezeile alles nach% 23 und fügen Sie es nach dem obigen sourceCode = ein.
Jetzt können wir unsere Lösung einreichen.
Ändern des Codes (noch kürzer machen)
Kürzen wir den Code. Es gibt zwei Möglichkeiten, den Code nach der Komprimierung zu verkürzen.
- Verkleinern Sie den Quellcode
- Kompressionsverhältnis erhöhen
Ich werde versuchen, beide Methoden anzuwenden. Das Verkleinern des Quellcodes ist eine beliebte Methode für Code Golf-Mitarbeiter.
Kompressionsverhältnis erhöhen
Wie kann ich das Kompressionsverhältnis erhöhen? Wir verwenden jetzt die Deflate-Komprimierung, eine Kombination aus Lauflängenkomprimierung und Huffman-Codierung. Achten Sie auf diesen Huffman-Code. Der Huffman-Code unterscheidet sich darin, dass das Komprimierungsverhältnis zunimmt, wenn die Entropie vor der Komprimierung abnimmt. Die Entropie nimmt ab, wenn sich die Wahrscheinlichkeiten für das Auftreten des Codes verschieben. Wenn daher die Wahrscheinlichkeit des Auftretens von Codes verschoben wird, erhöht sich das Komprimierungsverhältnis, wenn die Verschiebung auftritt.
Eine effektive Möglichkeit, die Wahrscheinlichkeit des Auftretens von Code zu verringern, besteht darin, den Zeichentyp zu verringern. Dazu können Sie die Variable umbenennen.
Benennen wir im ersten Code die Variablen x und v in t und p um. Da es dann mit dem Funktionsnamen Puts oder Map platziert wird, kann der Typ des Zeichens reduziert werden.
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, es hat zugenommen.
Entfernen Sie p und ersetzen Sie es durch 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 BDiesmal schrumpft es richtig.
(Ich weiß nicht, warum es zugenommen hat, also bitte, wenn es Leute gibt, die es wissen, sagen Sie es uns).
So konnten wir durch Versuch und Irrtum den Code verkürzen.
Ein Link zum Original dieses Artikels ist hier.
Wir würden uns sehr freuen, wenn Sie uns mitteilen, ob Ihnen dieser Artikel gefallen hat. War die Übersetzung klar, war sie für Sie nützlich?