Einführung
In dieser Herausforderung lösen Sie diagonale Burrows-Wheeler-Transformationen. Hier ist ein allgemeiner Überblick darüber, was eine diagonale Burrows-Wheeler-Transformation ist. Um eine Nachricht zu codieren, müssen Sie zuerst sicherstellen, dass sie ungerade ist (dh 5, 7, 9 usw.). Dann sind Sie ein Gitter bilden, n
durch n
, wobei n
die Länge der Nachricht ist. Die erste Zeile ist die ursprüngliche Nachricht. Jede Zeile danach ist die Zeile darüber, hat jedoch 1 Zeichen nach links verschoben, wobei sich das erste Zeichen nach hinten bewegt. Beispielsweise:
Hello World
ello WorldH
llo WorldHe
lo WorldHel
o WorldHell
WorldHello
WorldHello
orldHello W
rldHello Wo
ldHello Wor
dHello Worl
Dann nehmen Sie jeden Buchstaben in der Diagonale von NW nach SE und fügen ihn in eine neue Zeichenfolge ein:
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
Ihre verschlüsselte Nachricht lautet HloWrdel ol
. Um zu dekodieren, nehmen Sie zuerst die Länge der codierten Nachricht, addieren Sie 1 und dividieren Sie durch 2. Rufen Sie diese Nummer an x
. Jetzt, da wir wissen x
, beginnend mit dem ersten Buchstaben, ist jeder Buchstabe x
nach dem letzten eine Schleife. Beispielsweise:
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
Ordnen Sie jetzt einfach die Buchstaben in der richtigen Reihenfolge um Hello World
!
Herausforderung
Ihre Herausforderung besteht darin, entweder zwei Programme, Funktionen oder jeweils eines zu schreiben. Beide müssen jedoch dieselbe Sprache verwenden. Das erste Programm akzeptiert eine Zeichenfolge als Eingabe über STDIN, Programmargumente oder Funktionsparameter und codiert sie mit dieser Methode. Das zweite Programm akzeptiert eine Zeichenfolge als Eingabe über STDIN, Programmargumente oder Funktionsparameter und decodiert sie mit dieser Methode.
Bedarf
Erstes Programm / Funktion
- Eine einzelne Zeichenfolgeneingabe mit einer der oben aufgeführten Methoden.
- Die Zeichenfolge muss mit einem diagonalen Burrows-Wheeler-Transformationsstil codiert werden.
Zweites Programm / Funktion
- Eine einzelne Zeichenfolgeneingabe mit einer der oben aufgeführten Methoden.
- Die Zeichenfolge muss mit einem diagonalen Burrows-Wheeler-Transformationsstil dekodiert werden.
Einschränkungen
- Sie können keine integrierten oder externen Funktionen verwenden, die diese Aufgabe ausführen.
- Standardlücken sind nicht erlaubt.
- Beide Programme / Funktionen müssen in derselben Sprache sein.
Wertung
Dies ist Code Golf, also gewinnt das kürzeste Programm in Bytes .
Wenn ich weitere Informationen hinzufügen muss, hinterlasse einen Kommentar!
quelle
Antworten:
CJam, (4 + 8 =) 12 Bytes
Kodierungsprogramm:
Probieren Sie es hier online aus
Dekodierungsprogramm:
Probieren Sie es hier online aus
Wie (oder besser, warum) arbeiten sie :
Die Diagonal Burrows-Wheeler-Transformation ist im Grunde jedes andere Zeichen der Zeichenfolge, mit Umbruch vom Ende. Wenn wir den String als 2D-Matrix aus 2 Spalten behandeln, läuft es einfach darauf hinaus, die Transformation der Matrix durchzuführen. Beispiel:
Wird als 2D-Matrix als dargestellt
Wenn Sie es jetzt einfach spaltenweise lesen, geben Sie:
Welches ist die Burrows-Wheeler-Transformation.
Die Dekodierung erfolgt einfach in umgekehrter Reihenfolge. Schreiben Sie die Zeichenfolge als zweizeilige 2D-Matrix und lesen Sie spaltenweise.
Code-Erweiterung :
Encoder:
Decoder:
quelle
Python 2, 61 Bytes
E
verschlüsselt undD
entschlüsselt. Ich zähle nicht dasE=
undD=
für die Punktzahl.Bei der Entschlüsselung wird jedes
n
Zeichen umbrochen, wobein
die halbe Länge der Zeichenfolge aufgerundet wird. Der Grund, warum dies invertiert wird, ist, dass2
undn
modulo die Länge der Zeichenfolge invers sind, so dass jedesn
Zeichen invertiert wird , wobei jedes zweite Zeichen invertiert wird2
.Wenn die Verwendung einer einzelnen Funktion zulässig wäre, könnte ich 44 Bytes ausführen
Das verschlüsselt wann
b
istFalse
und entschlüsselt wannb
istTrue
. Der Ausdruck1+len(x)**b>>b
ist gleich[2,len(x)/2+1][b]
.quelle
J, 10 + 10 = 20
(Umliegende Klammern werden nicht in die Punktzahl einbezogen, da sie nicht Teil der Funktionsdefinition sind.)
Vielen Dank für FUZxxl für eine 3-Byte-Verbesserung.
Nun wird schön gezeigt, dass die beiden Funktionen umgekehrt sind, da die erste Zeichen Zeichen von Positionen nimmt, die durch die Liste definiert sind,
#|2*i.@#
und die zweite Funktion die Zeichen unter Verwendung derselben Liste wie die Reihenfolge zurückordnet.Probieren Sie es hier online aus.
quelle
{~#|2*i.@#
.Pyth - 5 + 11 = 16 Bytes
Ich habe ein Muster bemerkt! ~ Tanzt fröhlich ~ Die Transformation durchläuft einfach nur die Saite und wählt alle anderen Elemente aus. Es funktioniert nur ungerade, da es sonst nie die Hälfte der Elemente bekommen würde. Dies entspricht dem Drehen einer 2-breiten Matrix.
Encoder:
Pythons Step Slicing dreht sich nicht um, also habe ich die Zeichenfolge wiederholt.
Decoder:
Wieder kein Wrap-Around zum Step-Slicing.
quelle
GNU sed -r, (20 + 104 + 1) = 125
Die zusätzlichen +1 in der Punktzahl gelten für die Option -r für sed. Eingabezeichenfolgen mit ungerader Länge werden angenommen.
Encoder:
Decoder:
Der Decoder wird
:
als temporäres Markierungszeichen verwendet. Wenn es also in der Eingabezeichenfolge angezeigt wird, erhalten Sie ein undefiniertes Verhalten. Wenn die Eingabezeichenfolge auf 95 ASCII-Zeichen beschränkt ist, können diese Markierungen durch etwas außerhalb des ASCII-Bereichs (z. B. BEL 0x7) ersetzt werden, um dies zu beheben.:
Markierungen am Anfang und Ende der Eingabezeichenfolge:
Vorwärts- und das zweite:
Rückwärtszeichen nacheinander, bis sich die:
Markierungen auf beiden Seiten des mittleren Zeichens befinden:
und fügen Sie:
am Ende eine weitere hinzu , wobei "A: B:" übrig bleibt, wobei A die Zeichenfolge ist, die aus ungeraden Zeichen aus der Klartexteingabe besteht, und B die Zeichenfolge ist, die aus den geraden Zeichen besteht:
zusammen, um die Klartexteingabe wieder zusammenzusetzen:
Markierungenquelle
JavaScript ES6, 41 + 49 = 90 Bytes
Encoder
Decoder
Da es sich um anonyme Funktionen handelt, zähle ich nur den Code in Klammern, da dies die gesamte Funktionsdefinition ist. Probieren Sie es mit dem folgenden Snippet aus: (geändert, um ES5 zu verwenden)
Code-Snippet anzeigen
quelle
[t=>t.replace(/./g,(_,o)=>t[o*2%t.length]),t=>t.replace(/./g,(_,o)=>t[(1+(l=t.length))/2*o%l])]
? Du benutzt es wie[...][0]('encode string')
und[...][1]('decode string')
. Es gibt nichts zu sagen, dass dies nicht möglich ist! Und Sie sparen 1 Byte.