https en wikipedia orgwikiburrowse28093wheelertransform the burrowswheeler transform bwt also called blocksorting compression rearranges a character string into runs of similar characters this is useful for compression since it tends to be easy to compress a string that has runs of repeated characters by techniques such as movetofront transform and runlength encoding more importantly the transformation is reversible without needing to store any additional data except the position of the first original character the bwt is thus a free method of improving the efficiency of text compression algorithms costing only some extra computation param s the string that will be rotated lens times return a list with the rotations raises typeerror if s is not an instance of str examples allrotationsbanana doctest normalizewhitespace banana banana ananab nanaba anaban nabana abanan banana allrotationsaasadacasa doctest normalizewhitespace aasadacasa asadacasaa asadacasaa sadacasaaa adacasaaas dacasaaasa dacasaaasa acasaaasad casaaasada casaaasada asaaasadac saaasadaca aaasadacas allrotationspanamabanana doctest normalizewhitespace panamabanana anamabananap namabananapa amabananapan mabananapana abananapanam bananapanama ananapanamab nanapanamaba anapanamaban napanamabana apanamabanan allrotations5 traceback most recent call last typeerror the parameter s type must be str param s the string that will be used at bwt algorithm return the string composed of the last char of each row of the ordered rotations and the index of the original string at ordered rotations list raises typeerror if the s parameter type is not str raises valueerror if the s parameter is empty examples bwttransformbanana bwtstring bnnaaa idxoriginalstring 6 bwttransformaasadacasa bwtstring aaaadsscaa idxoriginalstring 3 bwttransformpanamabanana bwtstring mnpbnnaaaaaa idxoriginalstring 11 bwttransform4 traceback most recent call last typeerror the parameter s type must be str bwttransform traceback most recent call last valueerror the parameter s must not be empty make a string composed of the last char of each rotation param bwtstring the string returned from bwt algorithm execution param idxoriginalstring a 0based index of the string that was used to generate bwtstring at ordered rotations list return the string used to generate bwtstring when bwt was executed raises typeerror if the bwtstring parameter type is not str raises valueerror if the bwtstring parameter is empty raises typeerror if the idxoriginalstring type is not int or if not possible to cast it to int raises valueerror if the idxoriginalstring value is lower than 0 or greater than lenbwtstring 1 reversebwtbnnaaa 6 banana reversebwtaaaadsscaa 3 aasadacasa reversebwtmnpbnnaaaaaa 11 panamabanana reversebwt4 11 traceback most recent call last typeerror the parameter bwtstring type must be str reversebwt 11 traceback most recent call last valueerror the parameter bwtstring must not be empty reversebwtmnpbnnaaaaaa asd doctest normalizewhitespace traceback most recent call last typeerror the parameter idxoriginalstring type must be int or passive of cast to int reversebwtmnpbnnaaaaaa 1 traceback most recent call last valueerror the parameter idxoriginalstring must not be lower than 0 reversebwtmnpbnnaaaaaa 12 doctest normalizewhitespace traceback most recent call last valueerror the parameter idxoriginalstring must be lower than lenbwtstring reversebwtmnpbnnaaaaaa 11 0 panamabanana reversebwtmnpbnnaaaaaa 11 4 panamabanana param s the string that will be rotated len s times return a list with the rotations raises typeerror if s is not an instance of str examples all_rotations banana doctest normalize_whitespace banana banana anana b nana ba ana ban na bana a banan banana all_rotations a_asa_da_casa doctest normalize_whitespace a_asa_da_casa _asa_da_casaa asa_da_casaa_ sa_da_casaa_a a_da_casaa_as _da_casaa_asa da_casaa_asa_ a_casaa_asa_d _casaa_asa_da casaa_asa_da_ asaa_asa_da_c saa_asa_da_ca aa_asa_da_cas all_rotations panamabanana doctest normalize_whitespace panamabanana anamabananap namabananapa amabananapan mabananapana abananapanam bananapanama ananapanamab nanapanamaba anapanamaban napanamabana apanamabanan all_rotations 5 traceback most recent call last typeerror the parameter s type must be str param s the string that will be used at bwt algorithm return the string composed of the last char of each row of the ordered rotations and the index of the original string at ordered rotations list raises typeerror if the s parameter type is not str raises valueerror if the s parameter is empty examples bwt_transform banana bwt_string bnn aaa idx_original_string 6 bwt_transform a_asa_da_casa bwt_string aaaadss_c__aa idx_original_string 3 bwt_transform panamabanana bwt_string mnpbnnaaaaaa idx_original_string 11 bwt_transform 4 traceback most recent call last typeerror the parameter s type must be str bwt_transform traceback most recent call last valueerror the parameter s must not be empty sort the list of rotations in alphabetically order make a string composed of the last char of each rotation param bwt_string the string returned from bwt algorithm execution param idx_original_string a 0 based index of the string that was used to generate bwt_string at ordered rotations list return the string used to generate bwt_string when bwt was executed raises typeerror if the bwt_string parameter type is not str raises valueerror if the bwt_string parameter is empty raises typeerror if the idx_original_string type is not int or if not possible to cast it to int raises valueerror if the idx_original_string value is lower than 0 or greater than len bwt_string 1 reverse_bwt bnn aaa 6 banana reverse_bwt aaaadss_c__aa 3 a_asa_da_casa reverse_bwt mnpbnnaaaaaa 11 panamabanana reverse_bwt 4 11 traceback most recent call last typeerror the parameter bwt_string type must be str reverse_bwt 11 traceback most recent call last valueerror the parameter bwt_string must not be empty reverse_bwt mnpbnnaaaaaa asd doctest normalize_whitespace traceback most recent call last typeerror the parameter idx_original_string type must be int or passive of cast to int reverse_bwt mnpbnnaaaaaa 1 traceback most recent call last valueerror the parameter idx_original_string must not be lower than 0 reverse_bwt mnpbnnaaaaaa 12 doctest normalize_whitespace traceback most recent call last valueerror the parameter idx_original_string must be lower than len bwt_string reverse_bwt mnpbnnaaaaaa 11 0 panamabanana reverse_bwt mnpbnnaaaaaa 11 4 panamabanana
from __future__ import annotations

from typing import TypedDict


class BWTTransformDict(TypedDict):
    bwt_string: str
    idx_original_string: int


def all_rotations(s: str) -> list[str]:
    
    if not isinstance(s, str):
        raise TypeError("The parameter s type must be str.")

    return [s[i:] + s[:i] for i in range(len(s))]


def bwt_transform(s: str) -> BWTTransformDict:
    
    if not isinstance(s, str):
        raise TypeError("The parameter s type must be str.")
    if not s:
        raise ValueError("The parameter s must not be empty.")

    rotations = all_rotations(s)
    rotations.sort()  
    
    response: BWTTransformDict = {
        "bwt_string": "".join([word[-1] for word in rotations]),
        "idx_original_string": rotations.index(s),
    }
    return response


def reverse_bwt(bwt_string: str, idx_original_string: int) -> str:
    
    if not isinstance(bwt_string, str):
        raise TypeError("The parameter bwt_string type must be str.")
    if not bwt_string:
        raise ValueError("The parameter bwt_string must not be empty.")
    try:
        idx_original_string = int(idx_original_string)
    except ValueError:
        raise TypeError(
            "The parameter idx_original_string type must be int or passive"
            " of cast to int."
        )
    if idx_original_string < 0:
        raise ValueError("The parameter idx_original_string must not be lower than 0.")
    if idx_original_string >= len(bwt_string):
        raise ValueError(
            "The parameter idx_original_string must be lower than len(bwt_string)."
        )

    ordered_rotations = [""] * len(bwt_string)
    for _ in range(len(bwt_string)):
        for i in range(len(bwt_string)):
            ordered_rotations[i] = bwt_string[i] + ordered_rotations[i]
        ordered_rotations.sort()
    return ordered_rotations[idx_original_string]


if __name__ == "__main__":
    entry_msg = "Provide a string that I will generate its BWT transform: "
    s = input(entry_msg).strip()
    result = bwt_transform(s)
    print(
        f"Burrows Wheeler transform for string '{s}' results "
        f"in '{result['bwt_string']}'"
    )
    original_string = reverse_bwt(result["bwt_string"], result["idx_original_string"])
    print(
        f"Reversing Burrows Wheeler transform for entry '{result['bwt_string']}' "
        f"we get original string '{original_string}'"
    )