Resolver uma transformação Diagonal Burrows-Wheeler

11

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!

GamrCorps
fonte
2
Temos que converter a sequência de entrada de comprimento par em comprimento ímpar?
Optimizer
5
Esta não é uma transformação de Burrows-Wheeler.
FUZxxl 27/02
3
Uma transformação Burrows-Wheeler é diferente, pois a matriz de todas as rotações é classificada lexicograficamente antes de você executar os últimos itens.
FUZxxl 27/02
@Optimizer não é necessário.
GamrCorps

Respostas:

12

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

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

xnor
fonte
4

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.

randomra
fonte
O primeiro pode ser feito em 10 caracteres, bem como: {~#|2*i.@#.
FUZxxl 28/02
@FUZxxl Obrigado, atualizado. Agora, a relação entre as duas funções é mostrada muito bem.
randomra 28/02
3

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
Maltysen
fonte
@FryAmTheEggman Tenho certeza de que ele deve ter apenas uma string de comprimento ímpar. Foi no começo da descrição.
Maltysen 27/02
OPA, desculpe. : S
FryAmTheEggman 27/02
2

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
Trauma Digital
fonte
2

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)

NinjaBearMonkey
fonte
Que tal isso [t=>t.replace(/./g,(_,o)=>t[o*2%t.length]),t=>t.replace(/./g,(_,o)=>t[(1+(l=t.length))/2*o%l])]:? Você usa como [...][0]('encode string')e [...][1]('decode string'). Não há nada dizendo que isso não possa ser feito! E você economiza 1 byte.
Ismael Miguel
Obrigado, mas diz para escrever 2 funções, e eu não acho que isso contaria.
NinjaBearMonkey 27/02
Ainda são 2 funções. As regras não especificam nomes ou maneiras de acessar as funções. Diz apenas que você deve usar 2 funções.
Ismael Miguel
1
@IsmaelMiguel Agora que penso nisso, acho que as funções anônimas são permitidas por si mesmas, portanto, o uso disso me economiza ainda mais bytes.
NinjaBearMonkey
Estou feliz que você reduziu a contagem de bytes.
Ismael Miguel