Фон
Преобразование « движение вперед» (MTF) - это алгоритм кодирования данных, разработанный для повышения производительности методов энтропийного кодирования.
В алгоритме сжатия bzip2 он применяется после преобразования Барроуза-Уилера (как видно из Барроуза, Уилера и Бэка ) с целью преобразования групп повторяющихся символов в маленькие, легко сжимаемые неотрицательные целые числа.
Определение
Для этой задачи мы определим версию MTF для печати в формате ASCII следующим образом:
Для данной входной строки s возьмите пустой массив r , строку d всех печатаемых символов ASCII (от 0x20 до 0x7E) и повторите следующее для каждого символа c из s :
Добавьте индекс c в d к r .
Переместите 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).
Применяются стандартные правила игры в гольф. Самая короткая подача в байтах побеждает.
источник
Ответы:
CJam, 20
Попробуйте онлайн
Объяснение:
источник
Страус ,
4645 символовНе имеют номер версии в заголовке , потому что это на самом деле только последний коммит . Я добавил
O
(ASCII - код для строки) оператора после выпуска последней версии (но еще до того, эта проблема была опубликована).Объяснение:
источник
Python 3, 88
Используя некоторые идеи из моего решения CJam.
-4 байта принадлежат Sp3000 :)
источник
SWI-Prolog,
239197189 байтПример:
a(`Two more questions and I have bzip2 in less than 100 bytes!`).
выходы:(и
true .
после этого, очевидно)Примечание: ваша версия SWI-Prolog должна быть одной из более новых, в которой обратная кавычка
`
представляет строки кодов. Код строки , используемые должны быть представлены в двойных кавычках"
в старых версиях.источник
Python 2,
137110104Не было трудно реализовать, но , может быть , еще golfable?
Попробуй здесь
источник
e=d=map(chr,range(32,127))
в Python 2, хотя вам нужно настроить ееe
для обработки списка.e=[e.pop(n)]+e
, но это не работает. Это почему?e=d=
, поэтому, когда вы выскочите из,e
вы также выскочил изd
. Попробуйd=e[:]
.n=e.index(ord(c));r+=chr(n+32);
и броситьd
Pyth, 24 байта
Демонстрация. Тест Жгут.
Первый бит.
JK>95CM127
устанавливает необходимый список и сохраняет его вJ
иK
.~J+d-Jd
выполняет обновление списка, аxL ... z
отображаемые символы сопоставляются с их позициями в списке. Наконец,s@LK
преобразует эти индексы в символы в исходном списке.источник
Haskell, 120 байт
Пример использования:
f "CODEGOLF"
->"COEFH#MI"
Как это работает:
#
это индексная функция, которая возвращает позициюe
ins
(не может использовать родной язык HaskellelemIndex
из-за высокой стоимостиimport
). Основная функцияf
следует шаблону сгиба, где она обновляет строку позиции и строкуd
результата,r
когда она проходит по входной строке.источник