introduction

Dans ce défi, vous allez résoudre des transformations diagonales Burrows-Wheeler. Voici un aperçu général de ce qu'est une transformation diagonale de Burrows-Wheeler. Pour encoder un message, vous devez d'abord garantir qu'il est de longueur impaire (c'est-à-dire 5, 7, 9, etc.). Ensuite, vous créez une grille, npar n, où nest la longueur du message. La première ligne est le message d'origine. Chaque ligne après cela est la ligne au-dessus, mais décalée d'un caractère vers la gauche avec le premier caractère se déplaçant vers l'arrière. Par exemple:

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

Ensuite, vous prenez chaque lettre sur la diagonale NW à SE et la mettez dans une nouvelle chaîne:

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

Votre message encodé est HloWrdel ol. Pour décoder, prenez d'abord la longueur du message codé, ajoutez 1 et divisez par 2. Appelons ce numéro x. Maintenant que nous savons x, en commençant par la première lettre, chaque lettre est xaprès la dernière, en boucle. Par exemple:

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

Maintenant, réorganisez simplement les lettres dans le bon ordre pour les obtenir Hello World!

Défi

Votre défi consiste à écrire soit deux programmes, des fonctions, soit un de chacun. Cependant, les deux doivent utiliser la même langue. Le premier programme acceptera une chaîne en entrée via STDIN, des arguments de programme ou des paramètres de fonction et la codera en utilisant cette méthode. Le deuxième programme acceptera une chaîne en entrée via STDIN, des arguments de programme ou des paramètres de fonction et la décodera en utilisant cette méthode.

Exigences

Premier programme / fonction

• Une entrée de chaîne unique à l'aide de l'une des méthodes répertoriées ci-dessus.
• Doit coder la chaîne en utilisant un style de transformation diagonale Burrows-Wheeler.

Deuxième programme / fonction

• Une entrée de chaîne unique à l'aide de l'une des méthodes répertoriées ci-dessus.
• Doit décoder la chaîne en utilisant un style de transformation diagonale Burrows-Wheeler.

Contraintes

• Vous ne pouvez pas utiliser de fonctions intégrées ou externes pour accomplir cette tâche.
• Les échappatoires standard ne sont pas autorisées.
• Les deux programmes / fonctions doivent être dans la même langue.

Notation

C'est le golf de code, donc le programme le plus court en octets gagne.

Si j'ai besoin d'ajouter plus d'informations, laissez un commentaire!

CJam, (4 + 8 =) 12 octets

Programme d'encodage:

q2/z

Essayez-le en ligne ici

Programme de décodage:

q_,2/)/z

Essayez-le en ligne ici

Comment (ou plutôt pourquoi) ils fonctionnent :

La transformation Diagonal Burrows-Wheeler est essentiellement tous les autres caractères de la chaîne, avec un enroulement à la fin. Si nous traitons la chaîne comme une matrice 2D de 2 colonnes, cela revient simplement à prendre la transformation de la matrice. Exemple:

Hello World

Est représenté comme matrice 2D comme

He
ll
o 
Wo
rl
d

Maintenant, en le lisant simplement colonne par colonne, donnez:

HloWrdel ol

Quelle est la transformation Burrows-Wheeler.

Le décodage est simplement inverse du processus, écrivez la chaîne comme une matrice 2D à 2 lignes et lisez les colonnes.

Expansion du code :

Encodeur:

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

Décodeur:

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 octets

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

Echiffre et Ddéchiffre. Je ne compte pas le E=et D=pour le score.

Le déchiffrement prend chaque ncaractère autour, où nest la moitié de la longueur de la chaîne arrondie. La raison pour laquelle cette inversion est que 2et nsont inverses modulo la longueur de la chaîne, donc prendre chaque nth caractère inverse en prenant chaque 2nd.

Si l'utilisation d'une seule fonction était autorisée, je pourrais faire 44 octets

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

Le chiffre quand best Falseet déchiffre quand best True. L'expression 1+len(x)**b>>best égale à [2,len(x)/2+1][b].

J, 10 + 10 = 20

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

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

(Les accolades environnantes ne sont pas prises en compte dans la partition car elles ne font pas partie de la définition de la fonction.)

Merci pour FUZxxl pour une amélioration de 3 octets.

Maintenant, il est bien montré que les deux fonctions sont inverses car la première prend des caractères aux positions définies par la liste #|2*i.@#et la deuxième fonction réorganise les caractères en utilisant la même liste que la commande.

Essayez-le en ligne ici.

Pyth - 5 + 11 = 16 octets

J'ai remarqué un motif! ~ Est-ce que la danse est heureuse ~ La transformation est juste vraiment en boucle à travers la corde en choisissant tous les autres éléments. Cela ne fonctionne que sur les impairs car sinon il n'obtiendrait jamais la moitié des éléments. Cela équivaut à faire tourner une matrice à 2 larges.

Encodeur:

%2*2z

Le découpage par étapes de Python ne fait pas de boucle, j'ai donc répété la chaîne.

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

Décodeur:

K/hlz2%K*Kz

Encore une fois, pas d'enveloppement pour le découpage en tranches.

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

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

Le +1 supplémentaire dans le score correspond à l'option -r de sed. Des chaînes d'entrée de longueur impaire sont supposées.

Encodeur:

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

• Doublez la chaîne d'entrée
• Lâchez chaque caractère impair (à partir de 1)

Décodeur:

Le décodeur utilise :un caractère marqueur temporaire, donc s'il apparaît dans la chaîne d'entrée, vous obtiendrez un comportement indéfini. Si la chaîne d'entrée est limitée aux 95 caractères ASCII, ces marqueurs peuvent être remplacés par quelque chose en dehors de la plage ASCII (par exemple BEL 0x7) pour résoudre ce problème.

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

• Placer des :marqueurs au début et à la fin de la chaîne d'entrée
• Mélangez le premier :vers l'avant et le deuxième :vers l'arrière un caractère à la fois jusqu'à ce que les :marqueurs soient de chaque côté du caractère du milieu
• Supprimez le premier :et ajoutez un autre :à la fin en laissant "A: B:", où A est la chaîne composée de caractères impairs de l'entrée en texte brut et B est la chaîne composée des caractères pairs
• Riffle les caractères de A et B ensemble après le dernier :pour réassembler l'entrée en texte brut
• Retirez les :marqueurs restants

JavaScript ES6, 41 + 49 = 90 octets

Encodeur

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

Décodeur

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

Ce sont des fonctions anonymes, donc je ne compte que le code entre parenthèses car c'est la définition de la fonction entière. Essayez-le avec l'extrait ci-dessous: (modifié pour utiliser 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))