Introdução

Neste desafio, você resolverá as transformações diagonais de Burrows-Wheeler. Aqui está uma visão geral do que é uma transformação diagonal de Burrows-Wheeler. Para codificar uma mensagem, primeiro você deve garantir que ela tenha um comprimento ímpar (por exemplo, 5, 7, 9 etc.). Então você faz uma grade, npor n, onde né o comprimento da mensagem. A primeira linha é a mensagem original. Cada linha seguinte é a linha acima dela, mas mudou 1 caractere para a esquerda, com o primeiro caractere movendo-se para trás. Por exemplo:

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

Em seguida, você pega cada letra da diagonal NW para SE e a coloca em uma nova string:

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

Sua mensagem codificada é HloWrdel ol. Para decodificar, primeiro pegue o tamanho da mensagem codificada, adicione 1 e divida por 2. Vamos ligar para esse número x. Agora que sabemos x, começando na primeira letra, cada letra é xa última, dando a volta. Por exemplo:

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

Agora basta reorganizar as letras na ordem correta para obter Hello World!

Desafio

Seu desafio é escrever dois programas, funções ou um de cada. No entanto, ambos devem usar o mesmo idioma. O primeiro programa aceitará uma string como entrada via STDIN, argumentos do programa ou parâmetros de função e a codificará usando esse método. O segundo programa aceitará uma string como entrada via STDIN, argumentos do programa ou parâmetros de função e a decodificará usando esse método.

Exigências

Primeiro Programa / Função

• Uma entrada de sequência única usando qualquer método listado acima.
• Deve codificar a sequência usando um estilo de transformação diagonal Burrows-Wheeler.

Segundo Programa / Função

• Uma entrada de sequência única usando qualquer método listado acima.
• É necessário decodificar a sequência usando um estilo de transformação diagonal Burrows-Wheeler.

Restrições

• Você não pode usar nenhuma função interna ou externa que realize esta tarefa.
• As brechas padrão não são permitidas.
• Ambos os programas / funções devem estar no mesmo idioma.

Pontuação

Este é um código de golfe, e o programa mais curto em bytes vence.

Se precisar adicionar mais informações, deixe um comentário!

CJam, (4 + 8 =) 12 bytes

Programa de codificação:

q2/z

Experimente online aqui

Programa de decodificação:

q_,2/)/z

Experimente online aqui

Como (ou melhor, por que) eles funcionam :

A transformação Diagonal Burrows-Wheeler é basicamente qualquer outro caractere da sequência, com quebra automática no final. Se tratarmos a String como uma matriz 2D de 2 colunas, tudo se resume a realizar a transformação da matriz. Exemplo:

Hello World

É representado como matriz 2D como

He
ll
o 
Wo
rl
d

Agora, basta ler a coluna, dê:

HloWrdel ol

Qual é a transformação Burrows-Wheeler.

A decodificação é simplesmente o inverso do processo, escreva a string como uma matriz 2D de 2 linhas e leia a coluna.

Expansão do código :

Codificador:

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

Decodificador:

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";

Python 2, 61 bytes

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

Ecriptografa e Ddescriptografa. Não estou contando o E=e D=para a pontuação.

A descriptografia leva todos nos caracteres enroscados, com nmetade do comprimento da string. A razão pela qual isso inverte é que 2e né inverso modula o comprimento da string, portanto, cada ncaractere inverte cada 2um.

Se o uso de uma única função fosse permitido, eu poderia fazer 44 bytes

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

Criptografa quando bé Falsee descriptografa quando bé True. A expressão 1+len(x)**b>>bé igual a [2,len(x)/2+1][b].

J, 10 + 10 = 20

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

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

(Os colchetes não são contados na pontuação, pois não fazem parte da definição da função.)

Obrigado por FUZxxl por uma melhoria de 3 bytes.

Agora, é bem demonstrado que as duas funções são inversas, pois a primeira recebe caracteres das posições definidas pela lista #|2*i.@#e a segunda função organiza os caracteres de volta, usando a mesma lista de pedidos.

Experimente online aqui.

Pitão - 5 + 11 = 16 bytes

Eu notei um padrão! ~ Dança feliz ~ A transformação é realmente apenas percorrendo a corda, escolhendo todos os outros elementos. Funciona apenas no ímpar, pois, caso contrário, nunca obteria metade dos elementos. Isso é equivalente a girar uma matriz de 2 larguras.

Codificador:

%2*2z

A fatia de passos do Python não gira em volta, então repeti a string.

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

Decodificador:

K/hlz2%K*Kz

Novamente, não envolva em fatias.

K/hlz2       K=length of (input+1)/2
%K           Every kth element
 *Kz         From K*the input

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

O +1 extra na pontuação é para a opção -r sed. As strings de entrada de comprimento ímpar são assumidas.

Codificador:

s/.*/&&/
s/(.)./\1/g

• Dobrar a sequência de entrada
• Largue todos os caracteres ímpares (contando de 1)

Decodificador:

O decodificador é usado :como um caractere de marcador temporário; portanto, se ele aparecer na string de entrada, você terá um comportamento indefinido. Se a sequência de entrada estiver restrita aos 95 caracteres ASCII, esses marcadores poderão ser substituídos por algo fora do intervalo ASCII (por exemplo, BEL 0x7) para corrigir isso.

s/.*/:&:/
:l;s/:(.)(.+)(.):/\1:\2:\3/;tl
s/:(.*)/\1:/
:m;s/(.)(.*):(.?)(.*):(.*)/\2:\4:\5\1\3/;tm
s/://g

• Coloque :marcadores no início e no final da sequência de entrada
• Embaralhe o primeiro caractere :para frente e :para trás um caractere de cada vez até que os :marcadores fiquem em ambos os lados do caractere do meio
• Remova a primeira :e adicione outra :ao final, deixando "A: B:", onde A é a sequência composta por caracteres ímpares da entrada de texto sem formatação e B é a sequência composta pelos caracteres pares
• Organize novamente os caracteres de A e B após o último :para remontar a entrada de texto sem formatação
• Remova os :marcadores restantes

JavaScript ES6, 41 + 49 = 90 bytes

Codificador

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

Decodificador

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

Essas são funções anônimas, portanto, contando apenas o código entre parênteses, porque essa é toda a definição da função. Experimente com o trecho abaixo: (modificado para usar o ES5)

E=function(t){
  return t.replace(/./g,function(_,o){
    return t[o*2%t.length]
  })
}
D=function(t){
  return t.replace(/./g,function(_,o){
    return t[-~(l=t.length)/2*o%l]
  })
}
i=prompt();
alert('Encoded: '+E(i)+'\nDecoded: '+D(i))