Фон
После применения BWT (как показано в Burrows, Wheeler и Back ) и MTF (как видно в Move на лицевой стороне ASCII для печати ) компрессор bzip2 применяет довольно уникальную форму кодирования длин серий.
Определение
Для этой задачи мы определим преобразование BRLE следующим образом:
Учитывая входную строку s, которая состоит исключительно из символов ASCII с кодовыми точками от 0x20 до 0x7A, выполните следующее:
Замените каждую серию одинаковых символов на одно вхождение символа и сохраните количество повторений после первого.
Кодируйте количество повторений после первого вхождения символа , используя биективную нумерацию base-2 и символы
{
и}
.Неотрицательное целое число n кодируется в виде строки b k … b 0 , так что n = 2 k i (b k ) +… + 2 0 i (b 0 ) , где i (
{
) = 1 и i (}
) = 2 ,Обратите внимание, что это представление всегда уникально. Например, число 0 кодируется как пустая строка.
Вставьте строку фигурных скобок, которая кодирует количество повторений после единственного вхождения соответствующего символа.
Пошаговый пример
Input: "abbcccddddeeeeeffffffggggggghhhhhhhh"
Step 1: "abcdefgh" with repetitions 0, 1, 2, 3, 4, 5, 6, 7
Step 2: "" "{" "}" "{{" "{}" "}{" "}}" "{{{"
Step 3: "ab{c}d{{e{}f}{g}}h{{{"
задача
Реализуйте инволютивную программу или функцию, которая считывает одну строку из STDIN или в качестве аргумента командной строки или функции и печатает или возвращает либо BRLE, либо его инверсию входной строки.
Если ввод не содержит фигурных скобок, примените BRLE. Если входные данные содержат фигурные скобки, примените их в обратном порядке.
Примеры
INPUT: CODEGOLF
OUTPUT: CODEGOLF
INPUT: PROGRAMMING
OUTPUT: PROGRAM{ING
INPUT: PUZ{LES
OUTPUT: PUZZLES
INPUT: 444488888888GGGGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
OUTPUT: 4{{8{{{G{{{{W{{{{{
INPUT: y}}}{{
OUTPUT: yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
Дополнительные правила
Вы не можете использовать любые встроенные модули, которые вычисляют BRLE или его инверсию строки.
Вы можете использовать встроенные модули, которые:
Вычислить RLE или RLD строки, если количество повторений не сохранено в bijective base-2.
Выполните базовое преобразование любого вида.
Ваш код может напечатать завершающий символ новой строки, если вы выберете STDOUT для вывода.
Ваш код должен работать для любого ввода 1000 или менее символов ASCII в диапазоне от 0x20 до 0x7A, плюс фигурные скобки (0x7B и 0x7D).
Если входные данные содержат фигурные скобки, вы можете предположить, что это правильный результат применения BRLE к строке.
Применяются стандартные правила игры в гольф. Самая короткая подача в байтах побеждает.
источник
Ответы:
CJam,
5048 байтовСпасибо Денису за сохранение 2 байта.
Попробуйте онлайн.
объяснение
источник
Pyth, 48
50байтов2 байта благодаря @Maltysen.
Демонстрация. Тестовый жгут.
Объяснение:
источник
"{}"
тебя можно использовать`H
, связанный с CJam :)OCaml, 252
t
это функция, которая выполняет преобразование.Сначала я думал, что должен проверить наличие фигурных скобок, но это оказалось ненужным. Декодирование явно не влияет на строки, которые уже декодированы, и часть кодирования оказалась одинаково безвредной для тех, которые уже были закодированы.
источник
the encoding part proved equally harmless
Является ли? Кодировка4{{8{{{G{{{{W{{{{{
не получается4{{8{}G{{{W{{}
?JavaScript ( ES6 ), 162
Некоторое объяснение
Число n до BB2, используя 0 и 1:
(n+1).toString(2).slice(1)
Строка в BB2 в число: to_number ("0b1" + строка) - то есть, добавьте крайнюю левую 1 двоичную цифру и преобразуйте из двоичной (и уменьшите на 1, в данном конкретном случае не требуется).
Регулярное выражение для поиска любого символа с последующим
{
или}
:/[^{}][{}]+/g
Регулярное выражение для поиска повторяющихся символов:
/(.)\1*/g
Используя это регулярное выражение вместо, первый параметр - это «повторный» символ (в конце концов, повторяется только 1 раз), второй параметр - это общая повторяющаяся строка, длина которой - это число, которое мне нужно кодировать в BB2, уже увеличенное на 1.
... тогда собрать все вместе ...
источник