Antecedentes

La transformación de movimiento al frente (MTF) es un algoritmo de codificación de datos diseñado para mejorar el rendimiento de las técnicas de codificación de entropía.

En el algoritmo de compresión bzip2 , se aplica después de la transformación Burrows – Wheeler (como se ve en Burrows, Wheeler y Back ), con el objetivo de convertir grupos de caracteres repetidos en enteros pequeños, no negativos, fácilmente comprimibles.

Definición

Para el propósito de este desafío, definiremos la versión ASCII imprimible del MTF de la siguiente manera:

Dada una cadena de entrada s , tome una matriz vacía r , la cadena d de todos los caracteres ASCII imprimibles (0x20 a 0x7E) y repita lo siguiente para cada carácter c de s :

1. Anexar el índice de c en d a r .

2. Mueva c al frente de d , es decir, quite c de d y prepárela al resto.

Finalmente, tomamos los elementos de r como índices en la d original y buscamos los caracteres correspondientes.

Ejemplo paso a paso

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"

Tarea

Escriba un programa o función que implemente el MTF ASCII imprimible (como se definió anteriormente).

Casos de prueba

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

Reglas adicionales

• No puede utilizar ningún operador integrado que calcule el MTF de una cadena.

• Su código puede imprimir una nueva línea final si elige STDOUT para la salida.

• Su código tiene que funcionar para cualquier entrada de 1000 caracteres ASCII o menos imprimibles (0x20 a 0x7E).

• Se aplican reglas estándar de golf de código. La presentación más corta en bytes gana.

CJam, 20

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

Pruébalo en línea

Explicación:

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

Avestruz , 46 45 caracteres

No tenga un número de versión en el encabezado porque en realidad es solo la última confirmación . He añadido el O(código ASCII en cadena) del operador después de lanzar la versión más reciente (aunque antes de este desafío fue publicada).

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

Explicación:

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)

Pitón 3, 88

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

Usando algunas ideas de mi solución CJam.
-4 bytes pertenecen a Sp3000 :)

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

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

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

(y true .después de eso, obviamente)

Nota: su versión de SWI-Prolog tiene que ser una de las más nuevas en las que la comilla `representa cadenas de códigos. Las cadenas de código solían representarse con comillas dobles "en versiones anteriores.

Pitón 2, 137 110 104

¿No fue difícil de implementar, pero tal vez todavía golfable?

Pruébalo aquí

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 bytes

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

Demostración. Arnés de prueba.

El primer bit JK>95CM127configura la lista necesaria y la guarda en Jy K. ~J+d-Jdrealiza la actualización de la lista, mientras xL ... zasigna los caracteres de entrada a sus posiciones en la lista. Finalmente, s@LKconvierte esos índices en caracteres en la lista original.

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

Ejemplo de uso: f "CODEGOLF"->"COEFH#MI"

Cómo funciona: #es una función de índice que devuelve la posición de ein s(no se puede usar el nativo de Haskell elemIndexdebido a que es costoso import). La función principal fsigue un patrón de plegado donde actualiza la cadena de posición dy la cadena de resultados a rmedida que avanza por la cadena de entrada.