Фон

Преобразование Барроуза-Уилера (BWT) - это обратимая перестановка символов строки, которая приводит к большим сериям похожих символов для определенных типов строк, таких как простой текст. Он используется, например, в алгоритме сжатия bzip2 .

BWT определяется следующим образом:

Для заданной входной строки, такой как codegolf, вычислить все возможные повороты и отсортировать их в лексикографическом порядке:

codegolf
degolfco
egolfcod
fcodegol
golfcode
lfcodego
odegolfc
olfcodeg

BWT строки codegolf- это строка, состоящая из последнего символа каждой строки в этом порядке, т. Е. Последний столбец блока выше. Ибо codegolfэто дает fodleocg.

Само по себе это преобразование необратимо, так как строки codegolfи golfcodeрезультат в одной строке. Однако, если мы знаем, что строка заканчиваетсяf , возможен только один прообраз.

задача

Реализуйте инволютивную программу или функцию, которая считывает одну строку из STDIN или в качестве аргумента командной строки или функции и печатает или возвращает либо BWT, либо его инверсию входной строки.

Если входная строка не содержит пробелов, ваша заявка должна добавить один пробел к входу и вычислить BWT.

Если входная строка уже содержит пробел, она должна вычислить прообраз BWT, который имеет конечный пробел, и убрать этот пробел.

Примеры

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

Дополнительные правила

• Вы не можете использовать любые встроенные операторы, которые вычисляют BWT (или его инверсию) строки.

• Вы не можете использовать любые встроенные операторы, которые инвертируют функции.

• Ваш код может напечатать завершающий символ новой строки, если вы выберете STDOUT для вывода, даже если он не поддерживает завершающие символы новой строки во входных данных.

• Ваш код должен работать для любого ввода 500 или менее печатаемых символов ASCII (от 0x20 до 0x7E), включая не более одного пробела.

• Для любого из возможных входов, описанных выше, ваш код должен завершиться менее чем за десять минут на моем компьютере (Intel Core i7-3770, 16 ГБ ОЗУ). Последний тестовый пример должен быть самым медленным, поэтому убедитесь, что ваш код соответствует этому.

  Для большинства языков и подходов должно быть легко соблюдать ограничение по времени. Это правило предназначено исключительно для того, чтобы предотвратить реализацию одного из преобразований как грубую силу, противоположную другой.

• Применяются стандартные правила игры в гольф. Самая короткая подача в байтах побеждает.

Pyth, 29 байт

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

Демонстрация. Тестовый жгут.

Это напрямую делится на сегмент кодирования и декодирования, причем код решает, какой из них использовать с троичным.

?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 байт

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

Проверьте это здесь.

объяснение

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

Еще один не очень хороший от меня. Вероятно, в этом есть некоторые преимущества, но он не собирается конкурировать с специально созданными языками гольфа.

$_=<>;@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}

Un-golfed:

# 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;
}