Wprowadzenie

W tym wyzwaniu rozwiążesz przekątne transformacje Burrows-Wheeler. Oto ogólny przegląd tego, czym jest przekątna transformata Burrowsa-Wheelera. Aby zakodować wiadomość, musisz najpierw zagwarantować, że ma ona nieparzystą długość (tj. 5, 7, 9 itd.). Następnie należy wykonać siatkę, nprzez n, gdzie njest długością wiadomości. Pierwszy wiersz to oryginalna wiadomość. Każdy rząd po nim jest rzędem nad nim, ale przesunął 1 znak w lewo, a pierwszy znak przesuwa się do tyłu. Na przykład:

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

Następnie weź każdą literę na przekątnej NW do SE i umieść ją w nowym ciągu:

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

Twoja zakodowana wiadomość to HloWrdel ol. Aby zdekodować, najpierw weź długość zakodowanej wiadomości, dodaj 1 i podziel przez 2. Zadzwoń pod ten numer x. Teraz, gdy wiemy x, zaczynając od pierwszej litery, każda litera jest xza ostatnią, zapętlając się. Na przykład:

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

Teraz wystarczy zmienić kolejność liter we właściwej kolejności, aby uzyskać Hello World!

Wyzwanie

Wyzwanie polega na napisaniu dwóch programów, funkcji lub jednego z nich. Jednak oba muszą używać tego samego języka. Pierwszy program zaakceptuje ciąg jako dane wejściowe przez STDIN, argumenty programu lub parametry funkcji i zakoduje go przy użyciu tej metody. Drugi program zaakceptuje ciąg jako dane wejściowe przez STDIN, argumenty programu lub parametry funkcji i zdekoduje go przy użyciu tej metody.

Wymagania

Pierwszy program / funkcja

• Pojedynczy ciąg wejściowy przy użyciu dowolnej metody wymienionej powyżej.
• Należy zakodować ciąg przy użyciu ukośnego stylu transformacji Burrows-Wheeler.

Drugi program / funkcja

• Pojedynczy ciąg wejściowy przy użyciu dowolnej metody wymienionej powyżej.
• Należy zdekodować ciąg przy użyciu ukośnego stylu transformacji Burrows-Wheeler.

Ograniczenia

• Nie można używać żadnych wbudowanych ani zewnętrznych funkcji, które realizują to zadanie.
• Standardowe luki są niedozwolone.
• Oba programy / funkcje muszą być w tym samym języku.

Punktacja

To jest kod golfowy, więc wygrywa najkrótszy program w bajtach .

Jeśli muszę dodać więcej informacji, zostaw komentarz!

CJam, (4 + 8 =) 12 bajtów

Program do kodowania:

q2/z

Wypróbuj online tutaj

Program dekodujący:

q_,2/)/z

Wypróbuj online tutaj

Jak (a raczej dlaczego) działają :

Transformacja Diagonal Burrows-Wheeler to w zasadzie każda inna postać struny, z zawijaniem od końca. Jeśli traktujemy Łańcuch jako matrycę 2D złożoną z 2 kolumn, sprowadza się on po prostu do przekształcenia macierzy. Przykład:

Hello World

Jest reprezentowany jako macierz 2D jako

He
ll
o 
Wo
rl
d

Teraz, po prostu czytając kolumnę, podaj:

HloWrdel ol

Która jest transformacją Burrowsa-Wheelera.

Dekodowanie jest po prostu odwrotnością procesu, zapisz ciąg jako 2-rzędową matrycę 2D i odczytaj kolumnę.

Rozszerzenie kodu :

Enkoder:

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

Dekoder:

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 bajtów

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

Eszyfruje i Dodszyfrowuje. Nie liczę E=i D=za wynik.

Odszyfrowanie zajmuje co ndziesiąty znak, w którym ndługość połowy łańcucha jest zaokrąglona w górę. Powodem tego jest to, że odwraca 2i nsą odwrotności modulo długość łańcucha, więc biorąc co nth odwraca znaków biorąc pod każdą 2nd jeden.

Jeśli używanie jednej funkcji byłoby dozwolone, mógłbym zrobić 44 bajty

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

Szyfruje kiedy bjest Falsei odszyfrowuje kiedy bjest True. Wyrażenie 1+len(x)**b>>bjest równe [2,len(x)/2+1][b].

J, 10 + 10 = 20

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

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

(Nawiasy klamrowe nie są wliczane do wyniku, ponieważ nie są częścią definicji funkcji.)

Dzięki za FUZxxl za 3-bajtową poprawę.

Teraz jest ładnie pokazane, że dwie funkcje są odwrócone, ponieważ pierwsza pobiera znaki z pozycji określonych przez listę, #|2*i.@#a druga funkcja porządkuje znaki, używając tej samej listy jako kolejności.

Wypróbuj online tutaj.

Pyth - 5 + 11 = 16 bajtów

Zauważyłem wzór! ~ Czy taniec szczęśliwy ~ Transformacja po prostu zapętla strunę, zbierając wszystkie pozostałe elementy. Działa tylko na nieparzystych, ponieważ w przeciwnym razie nigdy nie uzyskałby połowy elementów. Jest to równoważne z obrotem 2 szerokiej matrycy.

Enkoder:

%2*2z

Krojenie kroków Pythona nie zapętla się, więc powtórzyłem ciąg.

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

Dekoder:

K/hlz2%K*Kz

Znowu nie owijamy się w krojenie krokowe.

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

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

Dodatkowy +1 w wyniku dotyczy opcji -r sed. Zakłada się łańcuchy wejściowe o nieparzystej długości.

Enkoder:

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

• Podwoj łańcuch wejściowy
• Upuszczaj każdą nieparzystą (licząc od 1) postać

Dekoder:

Dekoder wykorzystuje :jako tymczasowy znak znacznika, więc jeśli pojawi się w ciągu wejściowym, otrzymasz niezdefiniowane zachowanie. Jeśli ciąg wejściowy jest ograniczony do 95 znaków ASCII, wówczas znaczniki te można zastąpić czymś spoza zakresu ASCII (np. BEL 0x7), aby to naprawić.

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

• Umieść :znaczniki na początku i na końcu ciągu wejściowego
• Przetasuj kolejno pierwszą postać do :przodu i drugą :do tyłu, aż :znaczniki znajdą się po obu stronach środkowej postaci
• Usuń pierwszy :i dodaj kolejny :na końcu, pozostawiając „A: B:”, gdzie A to ciąg złożony z nieparzystych znaków z tekstu jawnego, a B to ciąg złożony z parzystych znaków
• Rifle znaków A i B razem po ostatnim, :aby ponownie złożyć tekst jawny
• Usuń pozostałe :markery

JavaScript ES6, 41 + 49 = 90 bajtów

Enkoder

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

Dekoder

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

Są to funkcje anonimowe, więc liczę kod tylko w nawiasach, ponieważ jest to cała definicja funkcji. Wypróbuj go z poniższym fragmentem: (zmodyfikowano, aby używać 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))