Решить диагональное преобразование Барроуза-Уилера

11

Вступление

В этом задании вы будете решать диагональные преобразования Барроуза-Уилера. Вот общий обзор диагонального преобразования Барроуза-Уилера. Для кодирования сообщения сначала необходимо убедиться, что оно нечетной длины (т. Е. 5, 7, 9 и т. Д.). Затем вы делаете сетку, с nпомощью n, где nдлина сообщения. Первая строка - это оригинальное сообщение. Каждая строка после этого является строкой над ней, но смещается на 1 символ влево, а первый символ перемещается назад. Например:

Hello World
ello WorldH
llo WorldHe
lo WorldHel
o WorldHell
 WorldHello
WorldHello 
orldHello W
rldHello Wo
ldHello Wor
dHello Worl

Затем вы берете каждую букву от диагонали NW до SE и помещаете ее в новую строку:

Hello World  H
ello WorldH  l
llo WorldHe  o
lo WorldHel  W
o WorldHell  r
 WorldHello  d
WorldHello   e
orldHello W  l
rldHello Wo  (space)
ldHello Wor  o
dHello Worl  l

Ваше кодированное сообщение HloWrdel ol. Для декодирования сначала возьмите длину закодированного сообщения, добавьте 1 и разделите на 2. Позволяет позвонить по этому номеру x. Теперь, когда мы знаем x, начиная с первой буквы, каждая буква идет xпосле последней и повторяется. Например:

H   l   o   W   r   d   e   l     o   l
1   

Then...

H   l   o   W   r   d   e   l     o   l
1                       2

And again...

H   l   o   W   r   d   e   l     o   l
1   3                   2

Until you get...

H   l   o   W   r   d   e   l       o   l
1   3   5   7   9  11   2   4   6   8  10

Теперь просто переставьте буквы в правильном порядке, чтобы получить Hello World!

Вызов

Ваша задача - написать две программы, функции или одну из них. Однако оба должны использовать один и тот же язык. Первая программа примет строку в качестве ввода через STDIN, аргументы программы или параметры функции и закодирует ее, используя этот метод. Вторая программа примет строку в качестве ввода через STDIN, аргументы программы или параметры функции и расшифрует ее, используя этот метод.

Требования

Первая программа / функция

  • Ввод одной строки с использованием любого метода, перечисленного выше.
  • Необходимо кодировать строку с использованием диагонального стиля преобразования Берроуза-Уилера.

Вторая программа / функция

  • Ввод одной строки с использованием любого метода, перечисленного выше.
  • Необходимо декодировать строку с использованием диагонального стиля преобразования Берроуза-Уилера.

Ограничения

  • Вы не можете использовать любые встроенные или внешние функции, которые выполняют эту задачу.
  • Стандартные лазейки не допускаются.
  • Обе программы / функции должны быть на одном языке.

счет

Это код гольф, поэтому самая короткая программа в байтах выигрывает .

Если мне нужно добавить больше информации, оставьте комментарий!

GamrCorps
источник
2
Нужно ли преобразовывать входную строку четной длины в нечетную длину?
Оптимизатор
5
Это не преобразование Барроуза-Уилера.
FUZxxl
3
Преобразование Берроуза-Уилера отличается тем, что массив всех вращений сортируется лексикографически перед тем, как вы берете последние элементы.
FUZxxl
@ Оптимизатор не нужен.
GamrCorps

Ответы:

12

CJam, (4 + 8 =) 12 байт

Программа кодирования:

q2/z

Попробуйте онлайн здесь

Программа декодирования:

q_,2/)/z

Попробуйте онлайн здесь

Как (точнее, почему) они работают :

Диагональное преобразование Барроуза-Уилера - это, в основном, любой другой символ строки с переносом с конца. Если мы будем рассматривать строку как двумерную матрицу из 2 столбцов, она просто сводится к преобразованию матрицы. Пример:

Hello World

Представляется в виде 2D матрицы в виде

He
ll
o 
Wo
rl
d

Теперь, просто прочитав это в столбце, дайте:

HloWrdel ol

Что является преобразованием Барроуза-Уилера.

Декодирование просто противоположно процессу, запишите строку в виде двухстрочной двухмерной матрицы и прочитайте столбец.

Расширение кода :

Кодер:

q          "Read the input";
 2/        "divide it into sub arrays of 2 characters";
   z       "Take transform";

декодер:

q_,        "Read the input, take copy and get length of copy";
   2/      "Divide the length by 2";
     )/    "Increment and split the input into two rows";
       z   "Take transform";
оптимизатор
источник
7

Python 2, 61 байт

E=lambda x:x[::2]+x[1::2]
D=lambda y:(-~len(y)/2*y)[::len(y)/2+1]

Eшифрует и Dдешифрует. Я не считаю E=и D=за счет.

При дешифровании происходит nобтекание каждого символа, причем nполовина длины строки округляется вверх. Причина, по которой это инвертирует, состоит в том, что 2и nявляются инверсиями по модулю длины строки, поэтому, принимая каждый nй символ, инвертирует, принимая каждый2 .

Если бы разрешалось использовать одну функцию, я мог бы сделать 44 байта

def F(x,b):n=1+len(x)**b>>b;return(n*x)[::n]

Шифрует, когда bесть, Falseи дешифрует, когда bесть True. Выражение 1+len(x)**b>>bравно [2,len(x)/2+1][b].

XNOR
источник
4

J 10 + 10 = 20

   ({~#|2*i.@#) 'Hello World'
HloWrdel ol

   (/:#|2*i.@#) 'HloWrdel ol'
Hello World

(Окружающие скобки не учитываются при подсчете, поскольку они не являются частью определения функции.)

Спасибо за FUZxxl за 3-байтовое улучшение.

Теперь хорошо показано, что две функции являются обратными, так как первая принимает символы с позиций, определенных списком, #|2*i.@#а вторая функция упорядочивает символы назад, используя тот же список, что и при упорядочивании.

Попробуйте это онлайн здесь.

randomra
источник
Первые из них могут быть сделаны в 10 символов , а также: {~#|2*i.@#.
FUZxxl
@FUZxxl Спасибо, обновлено. Теперь связь между двумя функциями показана действительно красиво.
Рандомра
3

Pyth - 5 + 11 = 16 байт

Я заметил образец! ~ Делает счастливый танец ~ Трансформация просто на самом деле просто петля через строку, выбирая все остальные элементы. Он работает только на нечетных, так как иначе он никогда не получит половину элементов. Это эквивалентно вращению матрицы шириной 2.

Кодер:

%2*2z

Шаг нарезки Python не зацикливается, поэтому я повторил строку.

%2      Take every other elements
 *2z    Double input string

декодер:

K/hlz2%K*Kz

Снова нет обертывания для пошаговой нарезки.

K/hlz2       K=length of (input+1)/2
%K           Every kth element
 *Kz         From K*the input
Maltysen
источник
@FryAmTheEggman Я уверен, что он должен принимать только строки нечетной длины. Это было в начале описания.
Maltysen
Ой, извините. : S
FryAmTheEggman
2

GNU sed -r, (20 + 104 + 1) = 125

Дополнительный +1 в счете за опцию -r для sed. Входные строки нечетной длины предполагаются.

Кодер:

s/.*/&&/
s/(.)./\1/g
  • Удвойте входную строку
  • Бросьте каждый нечетный (считая от 1) символа

декодер:

Декодер использует его :как временный маркерный символ, поэтому, если он появится во входной строке, вы получите неопределенное поведение. Если входная строка ограничена 95 символами ASCII, то эти маркеры могут быть заменены чем-то вне диапазона ASCII (например, BEL 0x7), чтобы это исправить.

s/.*/:&:/
:l;s/:(.)(.+)(.):/\1:\2:\3/;tl
s/:(.*)/\1:/
:m;s/(.)(.*):(.?)(.*):(.*)/\2:\4:\5\1\3/;tm
s/://g
  • Поместите :маркеры в начале и конце строки ввода
  • Перемешивайте первого :вперед и второго :назад по одному символу за раз, пока :маркеры не окажутся по обе стороны от среднего символа
  • Убери первое :и добавь другое: в конец, оставив «A: B:», где A - это строка, состоящая из нечетных символов из открытого текста, а B - строка, состоящая из четных символов.
  • Перефразируйте символы A и B вместе после последнего, :чтобы собрать исходный текст
  • Удалить оставшиеся :маркеры
Цифровая травма
источник
2

JavaScript ES6, 41 + 49 = 90 байт

кодировщик

(t=>t.replace(/./g,(_,o)=>t[o*2%t.length]))('Hello World')

дешифратор

(t=>t.replace(/./g,(_,o)=>t[-~(l=t.length)/2*o%l]))('HloWrdel ol')

Это анонимные функции, поэтому я считаю только код в скобках, потому что это целое определение функции. Попробуйте это с помощью фрагмента ниже: (модифицировано для использования ES5)

NinjaBearMonkey
источник
Как насчет этого: [t=>t.replace(/./g,(_,o)=>t[o*2%t.length]),t=>t.replace(/./g,(_,o)=>t[(1+(l=t.length))/2*o%l])]? Вы используете это как [...][0]('encode string')и [...][1]('decode string'). Ничто не говорит о том, что этого нельзя сделать! И вы экономите 1 байт.
Исмаэль Мигель
Спасибо, но написано 2 функции, и я не думаю, что это будет иметь значение.
NinjaBearMonkey
Это все еще 2 функции. Правила не определяют имена или способы доступа к функциям. Это только говорит о том, что вы должны использовать 2 функции.
Исмаэль Мигель
1
@IsmaelMiguel Теперь, когда я думаю об этом, я думаю, что анонимные функции разрешены сами по себе, поэтому использование этого экономит мне еще больше байтов.
NinjaBearMonkey
Я рад, что вы сократили количество байтов.
Исмаэль Мигель