Contexte

La transformation de déplacement vers l'avant (MTF) est un algorithme de codage de données conçu pour améliorer les performances des techniques de codage entropique.

Dans l' algorithme de compression bzip2 , il est appliqué après la transformation Burrows – Wheeler (comme on le voit dans Burrows, Wheeler et Back ), dans le but de transformer des groupes de caractères répétés en petits entiers non négatifs facilement compressibles.

Définition

Aux fins de ce défi, nous définirons la version ASCII imprimable du MTF comme suit:

Étant donné une chaîne d'entrée s , prenez un tableau vide r , la chaîne d de tous les caractères ASCII imprimables (0x20 à 0x7E) et répétez ce qui suit pour chaque caractère c de s :

1. Ajoutez l'index de c en d à r .

2. Déplacez c vers l'avant de d , c'est-à-dire, supprimez c de d et ajoutez-le au reste.

Enfin, nous prenons les éléments de r comme index dans le d original et récupérons les caractères correspondants.

Exemple pas à pas

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"

Tâche

Écrivez un programme ou une fonction qui implémente le MTF ASCII imprimable (tel que défini ci-dessus).

Cas de test

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(**:

Règles supplémentaires

• Vous ne pouvez pas utiliser d'opérateur intégré qui calcule le MTF d'une chaîne.

• Votre code peut imprimer une nouvelle ligne de fin si vous choisissez STDOUT pour la sortie.

• Votre code doit fonctionner pour toute entrée de 1000 caractères ASCII imprimables ou moins (0x20 à 0x7E).

• Les règles de golf du code standard s'appliquent. La soumission la plus courte en octets l'emporte.

CJam, 20

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

Essayez-le en ligne

Explication:

'¡,      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

Autruche , 46 45 caractères

N'ayez pas de numéro de version dans l'en-tête car il ne s'agit en fait que du dernier commit . J'ai ajouté l' Oopérateur (code ascii à la chaîne) après avoir publié la dernière version (mais toujours avant la publication de ce défi).

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

Explication:

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)

Python 3, 88

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

Utilisation de quelques idées de ma solution CJam.
-4 octets appartiennent à Sp3000 :)

SWI-Prolog, 239 197 189 octets

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

Exemple: a(`Two more questions and I have bzip2 in less than 100 bytes!`).sorties:

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

(et true .après, évidemment)

Remarque: votre version SWI-Prolog doit être l'une des plus récentes dans laquelle la citation arrière `représente des chaînes de codes. Les chaînes de code étaient représentées par des guillemets doubles "dans les anciennes versions.

Python 2, 137 110 104

Ce n'était pas difficile à mettre en œuvre, mais peut-être quand même jouable au golf?

Essayez-le ici

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

Pyth, 24 octets

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

Manifestation. Harnais de test.

Le premier morceau. JK>95CM127configure la liste nécessaire et l'enregistre dans Jet K. ~J+d-Jdeffectue la mise à jour de la liste, tout en xL ... zmappant les caractères saisis à leurs positions dans la liste. Enfin, s@LKconvertit ces index en caractères dans la liste d'origine.

Haskell, 120 octets

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,[])

Exemple d'utilisation: f "CODEGOLF"->"COEFH#MI"

Comment ça marche: #est une fonction d'index qui retourne la position de ein s(ne peut pas utiliser le natif de Haskell à elemIndexcause d'un prix élevé import). La fonction principale fsuit un modèle de pliage où elle met à jour la chaîne de position det la chaîne de résultat rlorsqu'elle parcourt la chaîne d'entrée.