[7/18/2014] Challenge #171 [Hard] Intergalatic Bitstream

'''http://www.reddit.com/r/dailyprogrammer/comments/2b21mp/7182014_challenge_171_hard_intergalatic_bitstream/'''
import math
import sys

CHARS = ' EOTRASINMDGHLPY0BF1CKUWV39254768JQXZ' # sorted by most common
N = 4 # number of bits each group will use

# create maps for compressing and decompressing
comp_map = {}
group_chars = int(math.pow(2,N))-1 # how many chars each group can hold
group_prefix = '{i:b}'.format(i=group_chars) # use 1111 as the prefix
for i,c in enumerate(CHARS):
    quot = i/group_chars
    rem = i%group_chars
    comp_map[c] = '{q}{r}'.format(q=group_prefix*quot,
                                  r='{:b}'.format(rem).zfill(N))
decomp_map = dict((v,k) for k, v in comp_map.iteritems())

def compress(msg):
    '''compress a message to a string of 1 and 0s'''
    output = []
    for c in msg:
        output.append(comp_map[c])
    return ''.join(output)

def decompress(msg):
    '''decompress a string of 1 and 0s back to the original message'''
    output = []
    chunks = [ msg[i:i+N] for i in xrange(0, len(msg), N)]
    prefix = ''
    for c in chunks:
        if c==group_prefix:
            prefix = prefix+c
        else:
            output.append(decomp_map[prefix+c])
            prefix = ''
    return ''.join(output)

if __name__ == '__main__':
    msg = sys.argv[1]
    msg_len = len(msg)*8
    print 'Read Message of {x} Bits.'.format(x=msg_len)
    print 'Message:{}'.format(msg)

    comp_msg = compress(msg)
    comp_msg_len = len(comp_msg)
    print 'Compressing {x} Bits into {y} Bits. ({z}pc compression)'.format(
                                x=msg_len,
                                y=comp_msg_len,
                                z=int(100*float(msg_len-comp_msg_len)/msg_len))
    print 'Compressed Message:{}'.format(comp_msg)

    print 'Sending Message.'

    decomp_msg = decompress(comp_msg)
    decomp_msg_len = len(decomp_msg)*8
    print 'Decompressing Message into {x} Bits.'.format(x=decomp_msg_len)
    print 'Decompressed Message:{}'.format(decomp_msg)
    assert(msg==decomp_msg)
    print 'Message Matches!'