Gehen Sie zur druckbaren ASCII-Front

19

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 :

  1. Fügen Sie den Index von c in d an r an .

  2. 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.

Dennis
quelle
1
"Nanananana DDUP!" ist einfach nicht so eingängig wie "Batman!" ...
Türklinke
8
@Doorknob: Aber Batman ist nicht leicht komprimierbar.
Dennis
Können wir das Ergebnis in einer Funktionsrückgabe ausgeben, anstatt es an STDOUT auszugeben?
Fatalize
@Fatalize: Das ist die natürlichste Form der Ausgabe für Funktionen, also ja. Übrigens, wir haben Standardeinstellungen für die E / A. Sofern in der Frage nicht ausdrücklich etwas anderes angegeben ist, ist dies immer zulässig.
Dennis

Antworten:

6

CJam, 20

'¡,q{_C#c' ,C+@|}fC;

Probieren Sie es online aus

Erläuterung:

'¡,      make a string of characters with codes from 0 to 160 (a modified "d")
         could have been to 126 but stackexchange doesn't like the DEL character
q        read the input (s)
{…}fC    for each character C in s
  _      duplicate the d string
  C#     find the index of C in d
  c      convert to character (this is the result)
  ' ,    make a string of characters from 0 to 31
  C+     append C to the string
  @      bring d to the top
  |      set union, preserving order; effectively, C is moved to position 32
         this is the updated d string
;        pop the last d
aditsu
quelle
6

Strauß , 46 45 Zeichen

Keine Versionsnummer im Header, da dies eigentlich nur das letzte Commit ist . Ich habe den OOperator (ASCII-Code zu Zeichenfolge) nach der Veröffentlichung der neuesten Version hinzugefügt (aber noch bevor diese Herausforderung veröffentlicht wurde).

{a95,{32+O}%:d3@{:x\.3@?3@\+\x-x\+}/;{d=}%s*}

Erläuterung:

a             this is the "r" array (a is short for [], empty array)
95,{32+O}%:d  this is the "d" array
3@{...}/      for each character in the input (as an "argument")...
  :x            store in variable x (stack is now [r d c])
  \.3@?         find index in d     (stack is now [r d idx])
  3@\+          append index to r   (stack is now [d modified_r])
  \x-           remove char from d, and then...
  x\+           prepend char to d   (stack is now [modified_r modified_d])
;             throw away modified_d
{d=}%         map r to indices of (original) d
s*            join (s is short for ``, empty string)
Türknauf
quelle
Ich frage mich, ob PPCG von "Code für diese Aufgabe in möglichst präziser Form in Ihrer Lieblingssprache" zu "Entwerfen einer eigenen Programmiersprache zur Lösung der typischen Code-Golfaufgabe, die kürzer als Golfscript ist" übergeht
John Dvorak,
1
@AlexA. ... warte, huh, es ist so geschrieben? Mein ganzes Leben war eine Lüge
Türklinke
@ JanDvorak Strauß ist fast identisch mit GolfScript. Der einzige wirkliche Grund, warum ich es geschaffen habe, ist, dass a.) GolfScript ärgerlicherweise keine REPL hat und b.) Es ein paar fehlende Operatoren / Funktionen (Gleitkomma, E / A usw.) gibt. Und Sprachdesign macht trotzdem Spaß!
Türklinke
3

Python 3, 88

*d,=range(127)
for c in input():y=d.index(ord(c));d[:32]+=d.pop(y),;print(chr(y),end='')

Unter Verwendung einiger Ideen aus meiner CJam-Lösung.
-4 Bytes gehören zu Sp3000 :)

aditsu
quelle
2

SWI-Prolog, 239 197 189 Bytes

a(S):-l([126],X),a(S,X,[],R),b(R,X).
a([A|T],X,S,R):-nth0(I,X,A,Z),(a(T,[A|Z],[I|S],R);R=[I|S]).
b([A|T],X):-(b(T,X);!),nth0(A,X,E),put(E).
l([B|R],Z):-A is B-1,X=[A,B|R],(A=32,Z=X;l(X,Z)).

Beispiel: a(`Two more questions and I have bzip2 in less than 100 bytes!`).Ausgänge:

Twp#o"si$sv#uvq(u$(l#o#W!r%w+$pz,xF%#,"x(. #0--'$GG ".z(**:

(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 .

Tödlich
quelle
2

Python 2, 137 110 104

War nicht schwer umzusetzen, aber vielleicht noch golffähig?

Probieren Sie es hier aus

e=d=map(chr,range(32,127))
r=""
for c in raw_input():n=e.index(c);r+=d[n];e=[e[n]]+e[:n]+e[n+1:]
print r
mbomb007
quelle
1
Ich denke, Sie sind besser dran, eine Listenzuordnung e=d=map(chr,range(32,127))in Python 2 zu erstellen, obwohl Sie die anpassen müssen e, um eine Liste zu bearbeiten.
Xnor
@ xnor Danke. Ich habe es auch versucht e=[e.pop(n)]+e, aber es funktioniert nicht. Warum das?
mbomb007
Du hast e=d=, also wenn du ekommst, kommst du auch d. Versuchen Sie es d=e[:].
Sp3000,
1
Aber an diesem Punkt ist es wahrscheinlich besser, einfach zu tun n=e.index(ord(c));r+=chr(n+32);und fallen zu lassend
Sp3000
1

Pyth, 24 Bytes

JK>95CM127s@LKxL~J+d-Jdz

Demonstration. Testgeschirr.

Das erste bisschen. JK>95CM127erstellt die erforderliche Liste und speichert sie unter Jund K. ~J+d-JdFührt die Listenaktualisierung durch und xL ... zordnet die eingegebenen Zeichen ihren Positionen in der Liste zu. Schließlich s@LKwandelt diese Indizes Zeichen in der ursprünglichen Liste.

isaacg
quelle
1

Haskell, 120 Bytes

e#s=[b|(b,a)<-zip[0..]s,a==e]!!0
a=[' '..'~']
f=snd.foldl(\(d,r)e->(e:take(e#d)d++tail(drop(e#d)d),r++[a!!(e#d)]))(a,[])

Anwendungsbeispiel: f "CODEGOLF"->"COEFH#MI"

So funktioniert es: #ist eine Indexfunktion, die die Position von ein zurückgibt s(kann Haskells native elemIndexwegen eines teuren nicht verwenden import). Die Hauptfunktion ffolgt einem Falzmuster, in dem sie die Positions- dund Ergebniszeichenfolge aktualisiert, rwährend sie durch die Eingabezeichenfolge wandert.

nimi
quelle