Hintergrund
Die Move-to-Front-Transformation (MTF) ist ein Datencodierungsalgorithmus zur Verbesserung der Leistung von Entropiecodierungstechniken.
Der bzip2-Komprimierungsalgorithmus wird nach der Burrows-Wheeler-Transformation (wie in Burrows, Wheeler und Back ) angewendet , mit dem Ziel, Gruppen sich wiederholender Zeichen in kleine, leicht komprimierbare, nicht negative Ganzzahlen umzuwandeln.
Definition
Für diese Herausforderung definieren wir die druckbare ASCII-Version des MTF wie folgt:
Nehmen Sie für eine eingegebene Zeichenfolge s ein leeres Array r , die Zeichenfolge d aller druckbaren ASCII-Zeichen (0x20 bis 0x7E), und wiederholen Sie Folgendes für jedes Zeichen c von s :
Fügen Sie den Index von c in d an r an .
Bewegen Sie c vor d , dh entfernen Sie c von d und stellen Sie es dem Rest voran.
Schließlich nehmen wir die Elemente von r als Indizes im ursprünglichen d und holen die entsprechenden Zeichen.
Beispiel Schritt für Schritt
INPUT: "CODEGOLF"
0. s = "CODEGOLF"
d = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = []
1. s = "ODEGOLF"
d = "C !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35]
2. s = "DEGOLF"
d = "OC !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47]
3. s = "EGOLF"
d = "DOC !\"#$%&'()*+,-./0123456789:;<=>?@ABEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37]
4. s = "GOLF"
d = "EDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38]
5. s = "OLF"
d = "GEDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40]
6. s = "LF"
d = "OGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3]
7. s = "F"
d = "LOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3 45]
8. s = ""
d = "FLOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3 45 41]
OUTPUT: "COEFH#MI"
Aufgabe
Schreiben Sie ein Programm oder eine Funktion, die das druckbare ASCII-MTF (wie oben definiert) implementiert.
Testfälle
Input: Programming Puzzles & Code Golf
Output: Prpi"do lp%((uz rnu&3!P/o&$U$(p
Input: NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN BATMAN!
Output: Na! !! !! !! !! !! !! !! !! !! !! !! !! !! !! !!"DDUP"%'
Input: Two more questions and I have bzip2 in less than 100 bytes!
Output: Twp#o"si$sv#uvq(u$(l#o#W!r%w+$pz,xF%#,"x(. #0--'$GG ".z(**:
Zusätzliche Regeln
Sie können keinen integrierten Operator verwenden, der die MTF einer Zeichenfolge berechnet.
Ihr Code druckt möglicherweise eine abschließende neue Zeile, wenn Sie für die Ausgabe STDOUT auswählen.
Ihr Code muss für jede Eingabe von 1000 oder weniger druckbaren ASCII-Zeichen (0x20 bis 0x7E) funktionieren.
Es gelten die Standard-Code-Golfregeln. Die kürzeste Übermittlung in Bytes gewinnt.
quelle
Antworten:
CJam, 20
Probieren Sie es online aus
Erläuterung:
quelle
Strauß ,
4645 ZeichenKeine Versionsnummer im Header, da dies eigentlich nur das letzte Commit ist . Ich habe den
O
Operator (ASCII-Code zu Zeichenfolge) nach der Veröffentlichung der neuesten Version hinzugefügt (aber noch bevor diese Herausforderung veröffentlicht wurde).Erläuterung:
quelle
Python 3, 88
Unter Verwendung einiger Ideen aus meiner CJam-Lösung.
-4 Bytes gehören zu Sp3000 :)
quelle
SWI-Prolog,
239197189 BytesBeispiel:
a(`Two more questions and I have bzip2 in less than 100 bytes!`).
Ausgänge:(und
true .
danach natürlich)Hinweis: Ihre SWI-Prolog-Version muss eine der neueren sein, in der das Backquote
`
Code-Zeichenfolgen darstellt. Früher wurden Code-Strings"
in älteren Versionen in Anführungszeichen gesetzt .quelle
Python 2,
137110104War nicht schwer umzusetzen, aber vielleicht noch golffähig?
Probieren Sie es hier aus
quelle
e=d=map(chr,range(32,127))
in Python 2 zu erstellen, obwohl Sie die anpassen müssene
, um eine Liste zu bearbeiten.e=[e.pop(n)]+e
, aber es funktioniert nicht. Warum das?e=d=
, also wenn due
kommst, kommst du auchd
. Versuchen Sie esd=e[:]
.n=e.index(ord(c));r+=chr(n+32);
und fallen zu lassend
Pyth, 24 Bytes
Demonstration. Testgeschirr.
Das erste bisschen.
JK>95CM127
erstellt die erforderliche Liste und speichert sie unterJ
undK
.~J+d-Jd
Führt die Listenaktualisierung durch undxL ... z
ordnet die eingegebenen Zeichen ihren Positionen in der Liste zu. Schließlichs@LK
wandelt diese Indizes Zeichen in der ursprünglichen Liste.quelle
Haskell, 120 Bytes
Anwendungsbeispiel:
f "CODEGOLF"
->"COEFH#MI"
So funktioniert es:
#
ist eine Indexfunktion, die die Position vone
in zurückgibts
(kann Haskells nativeelemIndex
wegen eines teuren nicht verwendenimport
). Die Hauptfunktionf
folgt einem Falzmuster, in dem sie die Positions-d
und Ergebniszeichenfolge aktualisiert,r
während sie durch die Eingabezeichenfolge wandert.quelle