from itertools import chain, groupby
from random import random
 
upperBound = 512
 
#numbers = [n for n in range(0, upperBound) if random() < 0.5]
numbers = [n for n in range(0, upperBound) if n % 3 != 0]
 
bits = ''.join([str(1 if n in numbers else 0) for n in range(0, upperBound)])
 
def flatten(l):
    return list(chain.from_iterable(l))
 
def encode(l):
    return flatten([[k, len(list(g))] for k, g in groupby(l)])
 
def decode(l):
    return flatten([[l[i * 2]] * l[i * 2 + 1] for i in range(int(len(l) / 2))])
 
def bwt(s):
 
    assert "^" not in s, "Input string cannot contain '^'"
 
    s += "^"  # Add end of file marker
    table = sorted(s[i:] + s[:i] for i in range(len(s)))  # Table of rotations of string
    last_column = [row[-1:] for row in table]  # Last characters of each row
 
    return "".join(last_column)  # Convert list of characters into string
 
def ibwt(r, *args):
 
        firstCol = "".join(sorted(r))
        count = [0]*256
        byteStart = [-1]*256
        output = [""] * len(r)
        shortcut = [None]*len(r)
 
        #Generates shortcut lists
        for i in range(len(r)):
                shortcutIndex = ord(r[i])
                shortcut[i] = count[shortcutIndex]
                count[shortcutIndex] += 1
                shortcutIndex = ord(firstCol[i])
                if byteStart[shortcutIndex] == -1:
                        byteStart[shortcutIndex] = i
 
        localIndex = (r.index("^") if not args else args[0])
 
        for i in range(len(r)):
                #takes the next index indicated by the transformation vector
                nextByte = r[localIndex]
                output [len(r)-i-1] = nextByte
                shortcutIndex = ord(nextByte)
                #assigns localIndex to the next index in the transformation vector
                localIndex = byteStart[shortcutIndex] + shortcut[localIndex]
 
        return "".join(output).rstrip("^")
 
ppbits = [bits[i : i + 8] for i in range(0, len(bits), 8)]
ppbits = [ppbits[i : i + 8] for i in range(0, len(ppbits), 8)]
 
print '\n'.join(map(lambda l : ' '.join(l), ppbits)), '\n'
 
compressed = encode(list(bwt(bits)))
print compressed, '\n'
 
bits_ = ibwt(''.join(decode(compressed)))
numbers_ = [n for n in range(len(bits_)) if bits_[n] == '1']
 
print bits == bits_ and numbers == numbers_

ZnJvbSBpdGVydG9vbHMgaW1wb3J0IGNoYWluLCBncm91cGJ5CmZyb20gcmFuZG9tIGltcG9ydCByYW5kb20KCnVwcGVyQm91bmQgPSA1MTIKCiNudW1iZXJzID0gW24gZm9yIG4gaW4gcmFuZ2UoMCwgdXBwZXJCb3VuZCkgaWYgcmFuZG9tKCkgPCAwLjVdCm51bWJlcnMgPSBbbiBmb3IgbiBpbiByYW5nZSgwLCB1cHBlckJvdW5kKSBpZiBuICUgMyAhPSAwXQoKYml0cyA9ICcnLmpvaW4oW3N0cigxIGlmIG4gaW4gbnVtYmVycyBlbHNlIDApIGZvciBuIGluIHJhbmdlKDAsIHVwcGVyQm91bmQpXSkKCmRlZiBmbGF0dGVuKGwpOgogICAgcmV0dXJuIGxpc3QoY2hhaW4uZnJvbV9pdGVyYWJsZShsKSkKCmRlZiBlbmNvZGUobCk6CiAgICByZXR1cm4gZmxhdHRlbihbW2ssIGxlbihsaXN0KGcpKV0gZm9yIGssIGcgaW4gZ3JvdXBieShsKV0pCgpkZWYgZGVjb2RlKGwpOgogICAgcmV0dXJuIGZsYXR0ZW4oW1tsW2kgKiAyXV0gKiBsW2kgKiAyICsgMV0gZm9yIGkgaW4gcmFuZ2UoaW50KGxlbihsKSAvIDIpKV0pCgpkZWYgYnd0KHMpOgoKICAgIGFzc2VydCAiXiIgbm90IGluIHMsICJJbnB1dCBzdHJpbmcgY2Fubm90IGNvbnRhaW4gJ14nIgoKICAgIHMgKz0gIl4iICAjIEFkZCBlbmQgb2YgZmlsZSBtYXJrZXIKICAgIHRhYmxlID0gc29ydGVkKHNbaTpdICsgc1s6aV0gZm9yIGkgaW4gcmFuZ2UobGVuKHMpKSkgICMgVGFibGUgb2Ygcm90YXRpb25zIG9mIHN0cmluZwogICAgbGFzdF9jb2x1bW4gPSBbcm93Wy0xOl0gZm9yIHJvdyBpbiB0YWJsZV0gICMgTGFzdCBjaGFyYWN0ZXJzIG9mIGVhY2ggcm93CgogICAgcmV0dXJuICIiLmpvaW4obGFzdF9jb2x1bW4pICAjIENvbnZlcnQgbGlzdCBvZiBjaGFyYWN0ZXJzIGludG8gc3RyaW5nCgpkZWYgaWJ3dChyLCAqYXJncyk6CgogICAgICAgIGZpcnN0Q29sID0gIiIuam9pbihzb3J0ZWQocikpCiAgICAgICAgY291bnQgPSBbMF0qMjU2CiAgICAgICAgYnl0ZVN0YXJ0ID0gWy0xXSoyNTYKICAgICAgICBvdXRwdXQgPSBbIiJdICogbGVuKHIpCiAgICAgICAgc2hvcnRjdXQgPSBbTm9uZV0qbGVuKHIpCgogICAgICAgICNHZW5lcmF0ZXMgc2hvcnRjdXQgbGlzdHMKICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4ocikpOgogICAgICAgICAgICAgICAgc2hvcnRjdXRJbmRleCA9IG9yZChyW2ldKQogICAgICAgICAgICAgICAgc2hvcnRjdXRbaV0gPSBjb3VudFtzaG9ydGN1dEluZGV4XQogICAgICAgICAgICAgICAgY291bnRbc2hvcnRjdXRJbmRleF0gKz0gMQogICAgICAgICAgICAgICAgc2hvcnRjdXRJbmRleCA9IG9yZChmaXJzdENvbFtpXSkKICAgICAgICAgICAgICAgIGlmIGJ5dGVTdGFydFtzaG9ydGN1dEluZGV4XSA9PSAtMToKICAgICAgICAgICAgICAgICAgICAgICAgYnl0ZVN0YXJ0W3Nob3J0Y3V0SW5kZXhdID0gaQoKICAgICAgICBsb2NhbEluZGV4ID0gKHIuaW5kZXgoIl4iKSBpZiBub3QgYXJncyBlbHNlIGFyZ3NbMF0pCgogICAgICAgIGZvciBpIGluIHJhbmdlKGxlbihyKSk6CiAgICAgICAgICAgICAgICAjdGFrZXMgdGhlIG5leHQgaW5kZXggaW5kaWNhdGVkIGJ5IHRoZSB0cmFuc2Zvcm1hdGlvbiB2ZWN0b3IKICAgICAgICAgICAgICAgIG5leHRCeXRlID0gcltsb2NhbEluZGV4XQogICAgICAgICAgICAgICAgb3V0cHV0IFtsZW4ociktaS0xXSA9IG5leHRCeXRlCiAgICAgICAgICAgICAgICBzaG9ydGN1dEluZGV4ID0gb3JkKG5leHRCeXRlKQogICAgICAgICAgICAgICAgI2Fzc2lnbnMgbG9jYWxJbmRleCB0byB0aGUgbmV4dCBpbmRleCBpbiB0aGUgdHJhbnNmb3JtYXRpb24gdmVjdG9yCiAgICAgICAgICAgICAgICBsb2NhbEluZGV4ID0gYnl0ZVN0YXJ0W3Nob3J0Y3V0SW5kZXhdICsgc2hvcnRjdXRbbG9jYWxJbmRleF0KCiAgICAgICAgcmV0dXJuICIiLmpvaW4ob3V0cHV0KS5yc3RyaXAoIl4iKQoKcHBiaXRzID0gW2JpdHNbaSA6IGkgKyA4XSBmb3IgaSBpbiByYW5nZSgwLCBsZW4oYml0cyksIDgpXQpwcGJpdHMgPSBbcHBiaXRzW2kgOiBpICsgOF0gZm9yIGkgaW4gcmFuZ2UoMCwgbGVuKHBwYml0cyksIDgpXQoKcHJpbnQgJ1xuJy5qb2luKG1hcChsYW1iZGEgbCA6ICcgJy5qb2luKGwpLCBwcGJpdHMpKSwgJ1xuJwoKY29tcHJlc3NlZCA9IGVuY29kZShsaXN0KGJ3dChiaXRzKSkpCnByaW50IGNvbXByZXNzZWQsICdcbicKCmJpdHNfID0gaWJ3dCgnJy5qb2luKGRlY29kZShjb21wcmVzc2VkKSkpCm51bWJlcnNfID0gW24gZm9yIG4gaW4gcmFuZ2UobGVuKGJpdHNfKSkgaWYgYml0c19bbl0gPT0gJzEnXQoKcHJpbnQgYml0cyA9PSBiaXRzXyBhbmQgbnVtYmVycyA9PSBudW1iZXJzXw==