tło

W Transformata Burrowsa-Wheelera (BWT) jest odwracalny permutacji z bohaterów sznurku, że wyniki w dużych seriach podobnych znaków dla niektórych typów ciągów, takich jak zwykły tekst. Jest stosowany na przykład w algorytmie kompresji bzip2 .

BWT definiuje się w następujący sposób:

Biorąc pod uwagę ciąg wejściowy, taki jak codegolf, oblicz wszystkie możliwe obroty i posortuj je w kolejności leksykograficznej:

codegolf
degolfco
egolfcod
fcodegol
golfcode
lfcodego
odegolfc
olfcodeg

BWT łańcucha codegolfjest łańcuchem składającym się z ostatniego znaku każdego łańcucha w tej kolejności, tj. Ostatniej kolumny bloku powyżej. Bo codegolfto daje fodleocg.

Sama transformacja nie jest odwracalna, ponieważ łańcuchy codegolfi golfcodewynik w tym samym łańcuchu. Jeśli jednak wiemy, że ciąg znaków kończy się na f, istnieje tylko jeden możliwy przykład.

Zadanie

Zaimplementuj program lub funkcję, która odczytuje pojedynczy ciąg znaków ze STDIN lub jako argument wiersza polecenia lub funkcji i wypisuje lub zwraca BWT lub odwrotność ciągu wejściowego.

Jeśli ciąg wejściowy nie zawiera spacji, twoje zgłoszenie powinno dołączyć jedną spację do wejścia i obliczyć BWT.

Jeśli łańcuch wejściowy zawiera już spację, powinien obliczyć preimage BWT, który ma spację końcową i usunąć tę spację.

Przykłady

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

Dodatkowe zasady

• Nie można używać żadnych wbudowanych operatorów, które obliczają BWT (lub jego odwrotność) ciągu.

• Nie można używać wbudowanych operatorów odwracających funkcje.

• Twój kod może wydrukować końcowy znak nowej linii, jeśli wybierzesz STDOUT jako wynik, nawet jeśli nie obsługuje końcowego znaku nowej linii na wejściu.

• Twój kod musi działać z dowolnym wprowadzeniem 500 lub mniej znaków drukowalnych ASCII (0x20 do 0x7E), w tym co najwyżej jedną spację.

• W przypadku dowolnego z opisanych powyżej możliwych danych wejściowych kod musi zakończyć się na moim komputerze w ciągu mniej niż dziesięciu minut (Intel Core i7-3770, 16 GiB RAM). Ostatni przypadek testowy powinien być najwolniejszy, więc upewnij się, że kodujesz razem z nim.

  W przypadku większości języków i podejść przestrzeganie limitu czasu powinno być łatwe. Zasada ta ma na celu wyłącznie zapobieganie realizacji jednej transformacji jako odwrotności drugiej brutalnej siły.

• Obowiązują standardowe zasady gry w golfa. Najkrótsze przesłanie w bajtach wygrywa.

Pyth, 29 bajtów

?tthu+VzSGzz}dzseMS.>L+z\ hlz

Demonstracja. Uprząż testowa.

To dzieli się bezpośrednio na segment kodowania i dekodowania, przy czym kod decyduje, który z nich należy zastosować w przypadku trójki.

?tthu+VzSGzz}dzseMS.>L+z\ hlz
                                 Implicit:
                                 z = input()
                                 d = ' '

?           }dz                  If there is a space in the input,
    u     zz                     Update G to the result of the following,
                                 with G starting as z and repeating len(z) times:
     +V                          The vectorized sum of
       zSG                       z and sorted(G)
   h                             Take the first such result, which will consist of
                                 the first character of z followed by the
                                 first cyclic permuation of the pre-BWT string,
                                 which must start with ' '.
 tt                              Remove the first two characters and return.
                 L               Otherwise, left-map (map with the variable as the 
                                 left parameter and a constant as the right)
               .>                cyclic right shift
                  +z\            of z + ' '
                      hlz        over range(len(z)+1)
              S                  Sort the shifted strings,
            eM                   take their last charactes,
           s                     combine into one string and return.

CJam, 41 36 35 bajtów

q:XS&LX,{X\.+$}*0=1>XS+_,,\fm<$zW>?

Sprawdź to tutaj.

Wyjaśnienie

q:X   e# Read STDIN and store it in X.
S&    e# Take the set intersection with " ". We'll use this as a truthy/falsy value to
      e# select the correct output later.

# Compute the iBWT:
LX,   e# Push an empty array, compute the length of X.
{     e# Run the following block that many times:
  X\  e# Push X and pull the other array on top.
  .+  e# Add the characters of X to the corresponding line of the other array,
      e# i.e. prepend X as a new column.
  $   e# Sort the rows.
}*
0=    e# Since we just sorted the rows, the first permutation of the output will be
      e# one starting with a space, followed by the string we actually want. So just
      e# pick the first permutation.
1>    e# Remove the leading space.

# Compute the BWT:
XS+   e# Push X and append a space.
_,    e# Get that string's length N.
,\    e# Turn it into a range [0 .. N-1], swap it with the string.
fm<   e# Map each value in the range to the string shifted left by that many characters.
$     e# Sort the permutations.
zW>   e# Transpose the grid and discard all lines but the last.

?     e# Choose between the iBWT and the BWT based on whether the input had a space.

Perl 5, 179

Kolejny niezbyt dobry ode mnie. Prawdopodobnie można się na tym zyskać, ale nie będzie ona konkurować z specjalnie zaprojektowanymi językami golfa.

$_=<>;@y=/./g;if(/ /){@x=sort@y;for(1..$#y){@x=sort map$y[$_].$x[$_],0..$#x}
say$x[0]=~/^ (.*)/}else{push@y," ";say map/(.)$/,sort map{$i=$_;join"",
map$y[($_+$i)%@y],0..$#y}0..$#y}

Bez golfa:

# Read input
$_ = <>;
# Get all the chars of the input
my @chars = /./g;

if (/ /) {
  # If there's a space, run the IBWT:
  # Make the first column of the table
  my @working = sort @chars;

  # For each remaining character
  for (1 .. $#chars) {
    # Add the input as a new column to the left of @working,
    # then sort @working again
    @working = sort map {
      $chars[$_] . $working[$_]
    } 0 .. $#working;
  }
  # Print the first element of @working (the one beginning with space), sans space
  say $working[0] =~ /^ (.*)/;
} else {
  # BWT
  # Add a space to the end of the string
  push @chars, " ";
  # Get all the rotations of the string and sort them
  @rows = sort map {
    my $offset = $_;
    join "", map {
      $chars[($_ + $offset) % @chars]
    } 0 .. $#chars
  } 0 .. $#chars;

  # Print all the last characters
  say map /(.)$/, @rows;
}