[BasE91](http://base91.sourceforge.net/) is a method for encoding binary as ASCII characters. It is more efficient than Base64 and needs 91 characters to represent the encoded data.

The following ASCII charakters are used:

    'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
    '!#$%&()*+,./:;<=>?@[]^_`{|}~"'
    
Create two functions that encode strings to basE91 string and decodes the other way round. 

    b91encode('test') = 'fPNKd'
    b91decode('fPNKd') = 'test'
    
    b91decode('>OwJh>Io0Tv!8PE') = 'Hello World!'
    b91encode('Hello World!') = '>OwJh>Io0Tv!8PE'
    
Input strings are valid.

Difficulty: interview

Starter code:

def b91decode(strng):
	

Solutions:
from math import ceil
def b91decode(strng):
    ret = ''
    base91_alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '#', '$',
    '%', '&', '(', ')', '*', '+', ',', '.', '/', ':', ';', '<', '=',
    '>', '?', '@', '[', ']', '^', '_', '`', '{', '|', '}', '~', '"']
    strng_arr = [strng[i:i+2] for i in range(0, len(strng), 2)]
    origin_bin = ''
    for str in strng_arr:
        num = 0
        if len(str) == 1:
            num += base91_alphabet.index(str[0])
            origin_bin = bin(num)[2:] + origin_bin
        else:
            num += base91_alphabet.index(str[0])
            num += base91_alphabet.index(str[1])*91
            if num & 8191 > 88:
                origin_bin = bin(num)[2:].zfill(13) + origin_bin
            else:
                origin_bin = bin(num)[2:].zfill(14) + origin_bin
    origin_bin = origin_bin.zfill(int(ceil(len(origin_bin)/8.0))*8)
    ret = [origin_bin[i:i+8] for i in range(0, len(origin_bin), 8)]
    return ''.join(map(lambda x:chr(int(x, 2)), ret))[::-1]
        
            
            
    
def b91encode(strng):
    base91_alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '#', '$',
    '%', '&', '(', ')', '*', '+', ',', '.', '/', ':', ';', '<', '=',
    '>', '?', '@', '[', ']', '^', '_', '`', '{', '|', '}', '~', '"']
    ret = ''
    strng_bin = map(lambda x:bin(ord(x))[2:].zfill(8), list(strng))
    strng_bin_r = ''
    for i in range(len(strng_bin)):
        strng_bin_r = strng_bin[i] + strng_bin_r
    strng_bin_r = strng_bin_r[::-1]
    index = 0
    while index < len(strng_bin_r):
        num = int(strng_bin_r[index:index+13][::-1], 2)
        if num > 88:
            index += 13
            ret += base91_alphabet[num%91] + base91_alphabet[num/91]
        else:
            num = int(strng_bin_r[index:index+14][::-1], 2)
            index += 14
            ret += base91_alphabet[num%91] + base91_alphabet[num/91]
    ret = ret[0:len(ret)-2]
    if num > 90:
        ret += base91_alphabet[num%91] + base91_alphabet[num/91]
    else:
        ret += base91_alphabet[num%91]
    return ret

import struct

b91abc = ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
          '!#$%&()*+,./:;<=>?@[]^_`{|}~"')

def b91decode(strng):
    a, b, c = -1, 0, 0
    result = bytearray()
    for char in strng:
        if not char in b91abc:
            continue
        ind = b91abc.index(char)
        if(a < 0): a = ind
        else:
            a += ind * 91; b |= a << c
            c += 13 if (a & 8191) > 88 else 14
            while True:
                result += struct.pack('B', b & 255); b >>= 8; c -= 8
                if c <= 7: break
            a = -1
    if a + 1: result += struct.pack('B', (b | a << c) & 255 )
    return result.decode()

def b91encode(strng):
    a, b = 0, 0 
    result = ''
    for count in range(len(strng)):
        byte = strng.encode()[count:count+1]
        b |= struct.unpack('B', byte)[0] << a; a += 8
        if a > 13: 
            c = b & 8191
            if c > 88: b >>= 13; a -= 13
            else: c = b & 16383; b >>= 14; a -= 14
            result += b91abc[c % 91] + b91abc[c // 91]
    if a:
        result += b91abc[b % 91]
        if a > 7 or b > 90: result += b91abc[b // 91]
    return result

import struct

CHARSET = ('ABCDEFGHIJKLMNOPQRSTUVWXYZ'
           'abcdefghijklmnopqrstuvwxyz'
           '0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~"')

def b91decode(message):
    value = stack = 0
    out = bytes()
    for first, second in zip(message[::2], message[1::2]):
        cipher = CHARSET.index(first) + CHARSET.index(second) * 91
        value |= cipher << stack
        stack += 13 + ((cipher & 8191) < 89)
        while stack > 7:
            out    += struct.pack('B', value & 255)
            value >>= 8
            stack  -= 8
    if len(message) % 2:
        rogue = message[-1]
        out  += struct.pack('B', (value | CHARSET.index(rogue) << stack) & 255)
    return out.decode('utf-8')

def b91encode(data):
    value = stack = 0
    out = ''
    for (byte,) in struct.iter_unpack('B', bytes(data, 'utf-8')):
        value |= byte << stack
        stack += 8
        if stack > 13:
            cipher = value & 8191
            if cipher > 88:
                value >>= 13
                stack  -= 13
            else:
                cipher  = value & 16383
                value >>= 14
                stack  -= 14
            out += CHARSET[cipher % 91] + CHARSET[cipher // 91]
    return out + (value > 0) * CHARSET[value % 91]

import struct

mapp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~"'
dmapp = dict((v,k) for k,v in enumerate(mapp))

def b91decode(strng):
    dbq = 0
    dn = 0
    dv = -1
    res = bytearray()
    for s in strng:
        if not s in dmapp.keys():
            continue
        if dv == -1:
            dv = dmapp[s]
        else:
            dv += dmapp[s] * 91
            dbq |= dv << dn
            if dv & 8191 > 88:
                dn += 13
            else:
                dn += 14                
            while True:
                res += struct.pack('B', dbq & 255)
                dbq >>= 8
                dn -= 8
                if dn <= 7:
                    break
            dv = -1
    if dv != -1:
        res += struct.pack('B', (dbq | dv << dn) & 255)
        
    return res.decode('utf-8') 
            
    
def b91encode(strng):
    en = 0
    ebq = 0
    res = ''
    for i in range(len(strng)):
        ebq |= (struct.unpack('B', strng[i].encode())[0] & 255) << en
        en += 8
        if en > 13:
            ev = ebq & 8191
            if ev > 88:
                ebq >>= 13
                en -= 13
            else:
                ev = ebq & 16383
                ebq >>= 14
                en -= 14
            res += mapp[ev % 91] + mapp[ev // 91]
    if en:
        res += mapp[ebq % 91];
        if en > 7 or ebq > 90:
            res += mapp[ebq / 91]

    return res

# yet another rewrite of Joachim Henke's C# implementation

ENCODE = list("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~\"")
DECODE = dict(map(reversed, enumerate(ENCODE)))

def b91encode(s):
    b, i = 0, 0
    r = ""

    for c in s:
        b |= ord(c) << i
        i += 8
        if i > 13:
            v = b & 0x1FFF
            k = 13
            if v < 89:
                v = b & 0x3FFF
                k += 1
            b >>= k
            i -= k
            r += ENCODE[v % 91] + ENCODE[v // 91]
    if i:
        r += ENCODE[b % 91]
        if i > 7 or b > 90: r += ENCODE[b // 91]

    return r

def b91decode(s):
    v, b, i = -1, 0, 0
    r = ""

    for c in s:
        c = DECODE[c]
        if ~v:
            v += c * 91
            b |= v << i
            i += 13 + (v & 0x1FFF < 89)
            while 1:
                r += chr(b & 0xFF)
                b >>= 8
                i -= 8
                if i < 8: break
            v = -1
        else: v = c
    if ~v: r += chr((b | v << i) & 0xFF)

    return r

from itertools import zip_longest as lzip

b91abc = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~"'

def b91decode(string):
    b = ''
    for x, y in lzip(*[iter(string)] * 2):
        num = 0
        if y is None:
            num += b91abc.index(x)
            b = bin(num)[2:] + b
        else:
            num += b91abc.index(x) + b91abc.index(y) * 91
            b = bin(num)[2:].zfill(13 if num & 8191 > 88 else 14) + b
    b = b.zfill((len(b) // 8 + 1) * 8)
    return ''.join(chr(int(''.join(x), 2)) for x in lzip(*[iter(b)] * 8, fillvalue=''))[::-1]


def b91encode(string):
    ret = b = ''
    index = num = 0
    for x in string:
        b = bin(ord(x))[2:].zfill(8) + b
    b = b[::-1]
    while index < len(b):
        num = int(b[index:index + 13][::-1], 2)
        if num <= 88:
            num = int(b[index:index + 14][::-1], 2)
            index += 1
        index += 13
        ret += b91abc[num % 91] + b91abc[num // 91]
    return ret[:len(ret) - 2] + b91abc[num % 91] + b91abc[num // 91] * (num > 90)

from struct import pack, unpack

base91 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
          'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
          'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
          'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
          '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '#', '$',
          '%', '&', '(', ')', '*', '+', ',', '.', '/', ':', ';', '<', '=',
          '>', '?', '@', '[', ']', '^', '_', '`', '{', '|', '}', '~', '"']

decode_table = {v: k for k, v in enumerate(base91)}


def b91encode(string):
    b = n = 0
    out = ''
    for i in range(len(string)):
        byte = string.encode('utf-8')[i:i + 1]
        b |= unpack('B', byte)[0] << n
        n += 8
        if n > 13:
            v = b & 8191
            if v > 88:
                b >>= 13
                n -= 13
            else:
                v = b & 16383
                b >>= 14
                n -= 14
            out += base91[v % 91] + base91[v // 91]
    if n:
        out += base91[b % 91]
        if n > 7 or b > 90:
            out += base91[b // 91]
    return out


def b91decode(string):
    v = -1
    b = n = 0
    out = bytearray()
    for char in string:
        if char not in decode_table:
            continue
        c = decode_table[char]
        if v < 0:
            v = c
        else:
            v += c * 91
            b |= v << n
            n += 13 if (v & 8191) > 88 else 14
            while True:
                out += pack('B', b & 255)
                b >>= 8
                n -= 8
                if not n > 7:
                    break
            v = -1
    if v + 1:
        out += pack('B', (b | v << n) & 255)
    return out.decode('utf-8')

codes='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&()*+,./:;<=>?@[]^_`{|}~"'
def b91decode(strng):
    b=[]
    for i in range(0,len(strng),2):
        if len(strng[i:i+2])==2:
            c1,c2=strng[i:i+2]
            x=codes.index(c1)+codes.index(c2)*91
        else:
            x=codes.index(strng[i:i+2])
        if x<=88 or x>=8192:
            b=list('{:014b}'.format(x))+b
        else:
            b=list('{:013b}'.format(x))+b
    r=''
    while(b):
        x=[]
        for _ in range(8):
            if not b:
                break
            x.insert(0,b.pop())
        r+=chr(int(''.join(x),2))
    return r.rstrip('\x00')
        
    
def b91encode(strng):
    b=[]
    for c in strng:
        b=list('{:08b}'.format(ord(c)))+b
    r=''
    while(b):
        x=[]
        for _ in range(13):
            if not b:
                break
            x.insert(0,b.pop())
        n=int(''.join(x),2)
        if n<=88 and b:
            x.insert(0,b.pop())
            n=int(''.join(x),2)
        r+=codes[n%91]+codes[n//91]
    return r.rstrip('A')

import struct

base91_alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '#', '$',
    '%', '&', '(', ')', '*', '+', ',', '.', '/', ':', ';', '<', '=',
    '>', '?', '@', '[', ']', '^', '_', '`', '{', '|', '}', '~', '"']

decode_table = dict((v,k) for k,v in enumerate(base91_alphabet))


def b91decode(encoded_str):
    v = -1
    b = 0
    n = 0
    out = bytearray()
    for strletter in encoded_str:
        if not strletter in decode_table:
            continue
        c = decode_table[strletter]
        if(v < 0):
            v = c
        else:
            v += c*91
            b |= v << n
            n += 13 if (v & 8191)>88 else 14
            while True:
                out += struct.pack('B', b&255)
                b >>= 8
                n -= 8
                if not n>7:
                    break
            v = -1
    if v+1:
        out += struct.pack('B', (b | v << n) & 255 )
    return out.decode()


def b91encode(string):
    b = 0
    n = 0
    out = ''
    bindata = string.encode()
    for count in range(len(bindata)):
        byte = bindata[count:count+1]
        b |= struct.unpack('B', byte)[0] << n
        n += 8
        if n>13:
            v = b & 8191
            if v > 88:
                b >>= 13
                n -= 13
            else:
                v = b & 16383
                b >>= 14
                n -= 14
            out += base91_alphabet[v % 91] + base91_alphabet[v // 91]
    if n:
        out += base91_alphabet[b % 91]
        if n>7 or b>90:
            out += base91_alphabet[b // 91]
    return out

b91_enctab = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '!', '#', '$',
    '%', '&', '(', ')', '*', '+', ',', '.', '/', ':', ';', '<', '=',
    '>', '?', '@', '[', ']', '^', '_', '`', '{', '|', '}', '~', '"'
]


def b91decode(strng):
    decode_str = ""
    value = -1
    seek = 0
    bynary = 0

    for item in strng:
        code = b91_enctab.index(item)
        if value < 0:
            value = code
        else:
            value += code * 91
            bynary |= value << seek

            if value & 8191 > 88:
                seek += 13
            else:
                seek += 14

            while seek > 7:
                decode_str += chr(bynary & 255)
                bynary >>= 8
                seek -= 8
            value = -1
    if value + 1:
        decode_str += chr((bynary | value << seek) & 255)
    return decode_str


def b91encode(strng):
    encode_str = ''
    bynary = 0
    seek = 0
    for symb in strng:
        bynary |= ord(symb) << seek
        seek += 8
        if seek > 13:
            value = bynary & 8191

            if value <= 88:
                value = bynary & 16383
                bynary >>= 14
                seek -= 14
            else:
                bynary >>= 13
                seek -= 13

            encode_str += b91_enctab[value % 91] + b91_enctab[value // 91]

    if seek != 0:
        encode_str += b91_enctab[bynary % 91]
        if seek > 7 or bynary > 90:
            encode_str += b91_enctab[bynary // 91]

    return encode_str


a = """<txG@<^F#H~H8MxsCYDpde4_SW"yER~]JwO_!g|OcxW$1^:KNRedl$r6l/:=JsiD+[R]bKVws=Op!v"?%9|Tn<7@,{q;r>d:sZH)"""


r = """4J>StI@i5oLyF.Th)8=+!tB9!#/`l$e$+Kz<}c6~%DsV@(rcJJ>yZ=?Y3JU@7bjoME3J<b5*KN.6xTP6zT1B1Zpc%nVRQxp1|+Zh|4@53d">!|$7+)vwUl:>cK"""


a = '''4J>StI@i5oLyF.Th)8=+!tB9!#/`l$e$+Kz<}c6~%DsV@(rcJJ>yZ=?Y3JU@7bjoME3J<b5*KN.6xTP6zT1B1Zpc%nVRQxp1|+Zh|4@53d">!|$7+)vwUl:>cK'''

print((b91encode('<txG@<^F#H~H8MxsCYDpde4_SW"yER~]JwO_!g|OcxW$1^:KNRedl$r6l/:=JsiD+[R]bKVws=Op!v"?%9|Tn<7@,{q;r>d:sZH)')))

print((r == b91encode(a)))