gistfile1.py

import math
import zlib

def encode(lines):
    if len(lines) == 0: return "0"
    
    # check if 3 points are on the same line, in order
    def ison(a, c, b):
      within = lambda p, q, r: p <= q <= r or r <= q <= p
      return ((b[0] - a[0]) * (c[1] - a[1]) == (c[0] - a[0]) * (b[1] - a[1])
        and (within(a[0], c[0], b[0]) if a[0] != b[0] else 
          within(a[1], c[1], b[1])))
    
    # converts series of lines to 'connect the dots', and looks for single dots
    strokes = [[lines[0][0:2]]]; dots = []
    for line in lines:
      if line[0:2] != strokes[-1][-1]: 
        if len(strokes[-1]) == 1:
          dots += strokes.pop()
        strokes += [[line[0:2]]]
      if line[2:4] != strokes[-1][-1]:
        if len(strokes[-1]) > 1 and \
          ison(strokes[-1][-2], strokes[-1][-1], line[2:4]):
            strokes[-1][-1] = line[2:4]
        else:
          strokes[-1] += [line[2:4]]
    if len(strokes[-1]) == 1:
      dots += strokes.pop()
    
    # big endian, most significant first
    def BEVLI4Enc(num):
      if num == 0: return '0' * 4
      else:
        temp = -(-int(math.log(num, 2) + 1) // 3) * 3
        temp = [bin(num)[2:].zfill(temp)[i:i+3] for i in range(0, temp, 3)]
        return '1'.join([''] + temp[:-1]) + '0' + temp[-1]
    
    # encode dots in binary
    data = ''.join(map(BEVLI4enc, [len(dots)] + [i for d in dots for i in d]))
    
    # convert series of points to deltas, then convert to binary
    directions = [bin(0x7070563)[2:][i:i+3] for i in range(0,27,3)]
    for stroke in strokes:
      prev_point = stroke[0]
      data += ''.join(map(BEVLI4enc, (len(stroke) - 1,) + prev_point))
      for point in stroke[1:]:
        dx, dy = point[0] - prev_point[0], point[1] - prev_point[1]
        prev_point = point
        # format: bit 'is this delta more than 1 pixel?', 3xbits direction
        # directions:   111   000   001
        #               110    #    010
        #               101   100   011
        data += ('1' if abs(dx) > 1 or abs(dy) > 1 else '0') + \
          directions[cmp(dx, 0) + 1 + (cmp(dy, 0) + 1) * 3]
        if abs(dx): data += BEVLI4enc(abs(dx))
        if abs(dy): data += BEVLI4enc(abs(dy))
    
    # pad to byte boundry, then convert to binary
    data = ''.join(map(lambda x: chr(int(x, 2)), \
      [data[i:i+8].ljust(8, '0') for i in range(0,len(data),8)]))
    
    # base 95 encoder
    def b95btoa(b):
        b95 = ''; n = int(('_' + b).encode('hex'), 16)
        while n > 0:
            b95 += chr(int(n % 95 + 32)); n /= 95
        return b95[::-1]
    
    # compress using zlib if it makes it smaller
    z = zlib.compress(data)[2:-4]
    if len(z) < len(data):
      return 'c' + b95btoa(z)
    else:
      return 'e' + b95btoa(data)