Переместиться на печатную переднюю часть ASCII

19

Фон

Преобразование « движение вперед» (MTF) - это алгоритм кодирования данных, разработанный для повышения производительности методов энтропийного кодирования.

В алгоритме сжатия bzip2 он применяется после преобразования Барроуза-Уилера (как видно из Барроуза, Уилера и Бэка ) с целью преобразования групп повторяющихся символов в маленькие, легко сжимаемые неотрицательные целые числа.

Определение

Для этой задачи мы определим версию MTF для печати в формате ASCII следующим образом:

Для данной входной строки s возьмите пустой массив r , строку d всех печатаемых символов ASCII (от 0x20 до 0x7E) и повторите следующее для каждого символа c из s :

  1. Добавьте индекс c в d к r .

  2. Переместите c в начало d , то есть удалите c из d и добавьте его к остатку.

Наконец, мы берем элементы r в качестве индексов в исходном d и выбираем соответствующие символы.

Пошаговый пример

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"

задача

Напишите программу или функцию, которая реализует печатный ASCII MTF (как определено выше).

Контрольные примеры

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

Дополнительные правила

  • Вы не можете использовать любой встроенный оператор, который вычисляет MTF строки.

  • Ваш код может напечатать завершающий символ новой строки, если вы выберете STDOUT для вывода.

  • Ваш код должен работать для любого ввода 1000 или менее печатных символов ASCII (от 0x20 до 0x7E).

  • Применяются стандартные правила игры в гольф. Самая короткая подача в байтах побеждает.

Деннис
источник
1
"Nanananana DDUP!" просто не так броско, как "Бэтмен!" ...
Дверная ручка
8
@Doorknob: Но Бэтмен не легко сжимаемый.
Деннис
Может мы выводим результат в возвращении функции вместо печати его STDOUT?
Fatalize
@Fatalize: Это самая естественная форма вывода для функций, так что да. Кстати, у нас есть по умолчанию для ввода / вывода , поэтому если вопрос явно не говорит , в противном случае, это всегда разрешено.
Деннис

Ответы:

6

CJam, 20

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

Попробуйте онлайн

Объяснение:

'¡,      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
источник
6

Страус , 46 45 символов

Не имеют номер версии в заголовке , потому что это на самом деле только последний коммит . Я добавил O(ASCII - код для строки) оператора после выпуска последней версии (но еще до того, эта проблема была опубликована).

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

Объяснение:

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)
Дверная ручка
источник
Я интересно , если PPCG превращается из «коды этой задачи в большинстве conscise образом возможно в вашем любимом языке» , чтобы «создать свой собственный язык программирования для решения типовых задач кода гольфа короче golfscript»
Джон Дворак
1
@AlexA. ... ждать, да, это пишется именно так? Вся моя жизнь была ложью
дверная ручка
@JanDvorak Страус почти идентичен GolfScript. Только реальная причина , я создал это потому.) GolfScript раздражающе не имеет REPL и б.) Есть несколько недостающих операторов / функций ( с плавающей точкой, I / O, и т.д.). И языковой дизайн это весело в любом случае!
Дверная ручка
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='')

Используя некоторые идеи из моего решения CJam.
-4 байта принадлежат Sp3000 :)

aditsu
источник
2

SWI-Prolog, 239 197 189 байт

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

Пример: a(`Two more questions and I have bzip2 in less than 100 bytes!`).выходы:

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

true .после этого, очевидно)

Примечание: ваша версия SWI-Prolog должна быть одной из более новых, в которой обратная кавычка `представляет строки кодов. Код строки , используемые должны быть представлены в двойных кавычках "в старых версиях.

Fatalize
источник
2

Python 2, 137 110 104

Не было трудно реализовать, но , может быть , еще golfable?

Попробуй здесь

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
источник
1
Я думаю, что лучше сделать карту списка e=d=map(chr,range(32,127))в Python 2, хотя вам нужно настроить ее eдля обработки списка.
xnor
@xnor Спасибо. Я также пытался использовать e=[e.pop(n)]+e, но это не работает. Это почему?
mbomb007
У вас есть e=d=, поэтому, когда вы выскочите из, eвы также выскочил из d. Попробуй d=e[:].
Sp3000
1
Но на данный момент, вероятно, лучше просто сделать n=e.index(ord(c));r+=chr(n+32);и броситьd
Sp3000
1

Pyth, 24 байта

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

Демонстрация. Тест Жгут.

Первый бит. JK>95CM127устанавливает необходимый список и сохраняет его в Jи K. ~J+d-Jdвыполняет обновление списка, а xL ... zотображаемые символы сопоставляются с их позициями в списке. Наконец, s@LKпреобразует эти индексы в символы в исходном списке.

isaacg
источник
1

Haskell, 120 байт

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

Пример использования: f "CODEGOLF"->"COEFH#MI"

Как это работает: #это индексная функция, которая возвращает позицию ein s(не может использовать родной язык Haskell elemIndexиз-за высокой стоимости import). Основная функция fследует шаблону сгиба, где она обновляет строку позиции и строку dрезультата, rкогда она проходит по входной строке.

Ними
источник