Fibonacci coding

fibonacci_coding.py

def fibGenMaxVal(maxnum):
	"""
	>>> fibGenMaxVal(30)
	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

	>>> fibGenMaxVal(150)
	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
	"""
	fibnums = [0, 1, 1]

	while fibnums[-1] < maxnum:
		fibnums.append(fibnums[-2] + fibnums[-1])

	return fibnums

def fibGenMaxSeq(maxseq):
	"""
	>>> fibGenMaxSeq(10)
	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

	>>> fibGenMaxSeq(14)
	[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
	"""
	fibnums = [0, 1]

	for _ in xrange(maxseq):
		fibnums.append(fibnums[-2] + fibnums[-1])

	return fibnums


def fibEncode(inseq):
	"""
	>>> fibEncode([1])
	'11'

	>>> fibEncode([2])
	'011'

	>>> fibEncode([3])
	'0011'

	>>> fibEncode([4])
	'1011'

	>>> fibEncode([5])
	'00011'

	>>> fibEncode([65])
	'0100100011'

	>>> fibEncode([5, 25, 44])
	'0001110100011010010011'

	>>> fibEncode([2012, 2013, 2014, 2015])
	'10100001000010011000100010000100111001000100001001101010001000010011'
	"""
	ret = []

	for num in inseq:

		encoded_num = "1"
		tmp = num
		fibnums = filter(lambda x: x <= num, fibGenMaxVal(num))

		for i in xrange(len(fibnums)-1, 1, -1):
			if fibnums[i] <= tmp:
				tmp -= fibnums[i]
				encoded_num += "1"
			else:
				encoded_num += "0"

		ret.append(encoded_num[::-1])

	return "".join(ret)

def fibDecode(inseq):
	"""
	>>> fibDecode('11')
	[1]

	>>> fibDecode('011')
	[2]

	>>> fibDecode('0011')
	[3]

	>>> fibDecode('1011')
	[4]

	>>> fibDecode('00011')
	[5]

	>>> fibDecode("0100100011")
	[65]

	>>> fibDecode("0001110100011010010011")
	[5, 25, 44]

	>>> fibDecode("10100001000010011000100010000100111001000100001001101010001000010011")
	[2012, 2013, 2014, 2015]
	"""

	encoded_nums = inseq.split("11")
	encoded_nums.pop() # string ends with "11" so last element is empty
	ret = []

	for num in encoded_nums:

		decoded_num = 0
		fibnums = fibGenMaxSeq(len(num)+2)

		for i, k in enumerate(num):
			if k is "1":
				decoded_num += fibnums[i+2]

		decoded_num += fibnums[len(num)+2]
		ret.append(decoded_num)

	return ret

if __name__ == "__main__":
	import doctest
	doctest.testmod()
	pass