Hintergrund
Die Burrows-Wheeler-Transformation (BWT) ist eine umkehrbare Permutation der Zeichen einer Zeichenfolge, die bei bestimmten Arten von Zeichenfolgen wie z. B. einfachem Text zu großen Folgen ähnlicher Zeichen führt. Es wird beispielsweise im bzip2-Komprimierungsalgorithmus verwendet .
Das BWT ist wie folgt definiert:
codegolf
Berechnen Sie bei einer gegebenen Eingabezeichenfolge wie z. B. alle möglichen Rotationen und sortieren Sie sie in lexikographischer Reihenfolge:
codegolf
degolfco
egolfcod
fcodegol
golfcode
lfcodego
odegolfc
olfcodeg
Die BWT der Zeichenfolge codegolf
ist die Zeichenfolge, die aus dem letzten Zeichen jeder Zeichenfolge in dieser Reihenfolge besteht, dh der letzten Spalte des obigen Blocks. Denn codegolf
das ergibt fodleocg
.
Diese Transformation ist für sich genommen nicht umkehrbar, da die Zeichenfolgen codegolf
und das golfcode
Ergebnis dieselbe Zeichenfolge sind. Wenn wir jedoch wissen, dass die Zeichenfolge mit einem endet f
, gibt es nur ein mögliches Vorbild.
Aufgabe
Implementieren Sie ein involutives Programm oder eine involutive Funktion, die eine einzelne Zeichenfolge aus STDIN oder als Befehlszeilen- oder Funktionsargument liest und entweder die BWT oder deren Inverse der Eingabezeichenfolge ausgibt oder zurückgibt.
Wenn die Eingabezeichenfolge keine Leerzeichen enthält, sollte Ihre Übermittlung der Eingabe ein einzelnes Leerzeichen hinzufügen und die BWT berechnen.
Wenn die Eingabezeichenfolge bereits ein Leerzeichen enthält, sollte sie das Vorabbild der BWT mit einem nachgestellten Leerzeichen berechnen und dieses Leerzeichen entfernen.
Beispiele
INPUT: ProgrammingPuzzles&CodeGolf
OUTPUT: fs&e grodllnomzomaiCrGgPePzu
INPUT: fs&e grodllnomzomaiCrGgPePzu
OUTPUT: ProgrammingPuzzles&CodeGolf
INPUT: bt4{2UK<({ZyJ>LqQQDL6!d,@:~L"#Da\6%EYp%y_{ed2GNmF"1<PkB3tFbyk@u0#^UZ<52-@bw@n%m5xge2w0HeoM#4zaT:OrI1I<|f#jy`V9tGZA5su*b7X:Xn%L|9MX@\2W_NwQ^)2Yc*1b7W<^iY2i2Kr[mB;,c>^}Z]>kT6_c(4}hIJAR~x^HW?l1+^5\VW'\)`h{6:TZ)^#lJyH|J2Jzn=V6cyp&eXo4]el1W`AQpHCCYpc;5Tu@$[P?)_a?-RV82[):[@94{*#!;m8k"LXT~5EYyD<z=n`Gfn/;%}did\fw+/AzVuz]7^N%vm1lJ)PK*-]H~I5ixZ1*Cn]k%dxiQ!UR48<U/fbT\P(!z5l<AefL=q"mx_%C:2=w3rrIL|nghm1i\;Ho7q+44D<74y/l/A)-R5zJx@(h8~KK1H6v/{N8nB)vPgI$\WI;%,DY<#fz>is"eB(/gvvP{7q*$M4@U,AhX=JmZ}L^%*uv=#L#S|4D#<
OUTPUT: <#Q6(LFksq*MD"=L0<f^*@I^;_6nknNp;pWPBc@<A^[JZ?\B{qKc1u%wq1dU%;2)?*nl+U(yvuwZl"KIl*mm5:dJi{\)8YewB+RM|4o7#9t(<~;^IzAmRL\{TVH<bb]{oV4mNh@|VCT6X)@I/Bc\!#YKZDl18WDIvXnzL2Jcz]PaWux[,4X-wk/Z`J<,/enkm%HC*44yQ,#%5mt2t`1p^0;y]gr~W1hrl|yI=zl2PKU~2~#Df"}>%Io$9^{G_:\[)v<viQqwAU--A#ka:b5X@<2!^=R`\zV7H\217hML:eiD2ECETxUG}{m2:$r'@aiT5$dzZ-4n)LQ+x7#<>xW)6yWny)_zD1*f @F_Yp,6!ei}%g"&{A]H|e/G\#Pxn/(}Ag`2x^1d>5#8]yP>/?e51#hv%;[NJ"X@fz8C=|XHeYyQY=77LOrK3i5b39s@T*V6u)v%gf2=bNJi~m5d4YJZ%jbc!<f5Au4J44hP/(_SLH<LZ^%4TH8:R
INPUT: <#Q6(LFksq*MD"=L0<f^*@I^;_6nknNp;pWPBc@<A^[JZ?\B{qKc1u%wq1dU%;2)?*nl+U(yvuwZl"KIl*mm5:dJi{\)8YewB+RM|4o7#9t(<~;^IzAmRL\{TVH<bb]{oV4mNh@|VCT6X)@I/Bc\!#YKZDl18WDIvXnzL2Jcz]PaWux[,4X-wk/Z`J<,/enkm%HC*44yQ,#%5mt2t`1p^0;y]gr~W1hrl|yI=zl2PKU~2~#Df"}>%Io$9^{G_:\[)v<viQqwAU--A#ka:b5X@<2!^=R`\zV7H\217hML:eiD2ECETxUG}{m2:$r'@aiT5$dzZ-4n)LQ+x7#<>xW)6yWny)_zD1*f @F_Yp,6!ei}%g"&{A]H|e/G\#Pxn/(}Ag`2x^1d>5#8]yP>/?e51#hv%;[NJ"X@fz8C=|XHeYyQY=77LOrK3i5b39s@T*V6u)v%gf2=bNJi~m5d4YJZ%jbc!<f5Au4J44hP/(_SLH<LZ^%4TH8:R
OUTPUT: bt4{2UK<({ZyJ>LqQQDL6!d,@:~L"#Da\6%EYp%y_{ed2GNmF"1<PkB3tFbyk@u0#^UZ<52-@bw@n%m5xge2w0HeoM#4zaT:OrI1I<|f#jy`V9tGZA5su*b7X:Xn%L|9MX@\2W_NwQ^)2Yc*1b7W<^iY2i2Kr[mB;,c>^}Z]>kT6_c(4}hIJAR~x^HW?l1+^5\VW'\)`h{6:TZ)^#lJyH|J2Jzn=V6cyp&eXo4]el1W`AQpHCCYpc;5Tu@$[P?)_a?-RV82[):[@94{*#!;m8k"LXT~5EYyD<z=n`Gfn/;%}did\fw+/AzVuz]7^N%vm1lJ)PK*-]H~I5ixZ1*Cn]k%dxiQ!UR48<U/fbT\P(!z5l<AefL=q"mx_%C:2=w3rrIL|nghm1i\;Ho7q+44D<74y/l/A)-R5zJx@(h8~KK1H6v/{N8nB)vPgI$\WI;%,DY<#fz>is"eB(/gvvP{7q*$M4@U,AhX=JmZ}L^%*uv=#L#S|4D#<
INPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OUTPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
INPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OUTPUT: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Zusätzliche Regeln
Sie können keine integrierten Operatoren verwenden, die die BWT (oder deren Inverse) einer Zeichenfolge berechnen.
Sie können keine eingebauten Operatoren verwenden, die Funktionen invertieren.
Ihr Code druckt möglicherweise eine abschließende neue Zeile, wenn Sie STDOUT für die Ausgabe auswählen, auch wenn sie keine abschließenden neuen Zeilen in der Eingabe unterstützt.
Ihr Code muss für jede Eingabe von 500 oder weniger druckbaren ASCII-Zeichen (0x20 bis 0x7E) funktionieren, einschließlich höchstens eines Leerzeichens.
Für jede der oben beschriebenen Eingabemöglichkeiten muss Ihr Code auf meinem Computer (Intel Core i7-3770, 16 GiB RAM) in weniger als zehn Minuten fertig sein. Der letzte Testfall sollte der langsamste sein, stellen Sie also sicher, dass Sie Ihren Code mit diesem zeitlich festlegen.
Für die meisten Sprachen und Ansätze sollte es einfach sein, das Zeitlimit einzuhalten. Diese Regel soll lediglich verhindern, dass eine der Transformationen als Brute-Force-Inverse der anderen implementiert wird.
Es gelten die Standard-Code-Golfregeln. Die kürzeste Übermittlung in Bytes gewinnt.
quelle
inv
.inv
Arbeit an einer benutzerdefinierten Funktion. Ich bin mir nicht sicher, obinv
es für die BWT funktionieren würde, aber es ist sicherer als leid.Antworten:
Pyth, 29 Bytes
Demonstration. Kabelbaum testen.
Dies teilt sich direkt in ein Codierungs- und Decodierungssegment auf, wobei der Code entscheidet, welches mit einem Ternär verwendet wird.
quelle
CJam,
413635 BytesTeste es hier.
Erläuterung
quelle
Perl 5, 179
Ein anderer nicht so guter von mir. Es gibt wahrscheinlich einige Gewinne, die in diesem zu haben sind, aber es wird nicht mit den speziell gebauten Golfsprachen konkurrieren.
Nicht golfen:
quelle
-n
Schalter verwenden (normalerweise als 1 Byte gezählt), brauchen Sie nicht$_=<>;
. 2. werdenfor(1..$#y){...}
können... for 1..$#y
. 3.$"
wird auf" "
und ein Byte kürzer initialisiert .for
an einem Punkt mehrere Aussagen in der , so dass das Postfix-Formular kein Gewinn war, aber als ich es auf eins