1b_compress_numbers.py

import unittest

def compress_numbers_helper(ts):
	"""
	This helper function takes in a list of tuples indicating the ranges of 
	numbers and outputs the compressed numbers as an iterator of strings.
	"""
	for start, end in ts:
		# handle singleton ranges
		if start == end:
			yield str(start)
			continue

		xs = str(start)
		ys = str(end)
		for i in range(4): # it's a 4 digit phone number
			if not xs[i] == ys[i]:
				break
		yield "{}-{}".format(start, ys[i:])

def compress_numbers(xs):
	"""
	Adapted from LA 2189 (Dhaka06) - TA will be Aaditya.

	Alif’s notebook contains many different phone numbers from 1000 to 9999, and 
	there may exist some consecutive numbers. To save space, he wants to save 
	space by writing the consecutive numbers as a range. For example, if there are 
	three numbers 2396, 2397, 2398, Alif will write the numbers as “2396-8”. This 
	comprises the smallest number in the sequence, followed by a hyphen, and then 
	the rightmost digits of the largest number that are different from the 
	smallest number. Similarly, if there are eleven numbers 1123, 1124, ..., 1133, 
	Alif will write them as "1123-33", and if there are five numbers 5998, 5999, 
	..., 6002, Alif will write them as “5998-6002”.

	A helper function compress_numbers_helper has been provided for you which 
	converts a list of tuples indicating the ranges of numbers into this format. 
	For a list of numbers like:

	[1123, 1124, 1125, 1126, 1129, 1130, 1131, 1132, 1298, 1299, 1300, 1401, 1903]

	the function will take in a list of tuples in this format:

	[(1123, 1126), (1129, 1132), (1298, 1300), (1401, 1401), (1903, 1903)]

	and output these numbers:

	['1123-6', '1129-32', '1298-300', '1401', '1903']

	Using this helper function, write a function compress_numbers which takes in 
	a list of phone numbers and outputs the compressed list, as a list of strings. 
	(Another function compress_numbers_stats has been provided which gives 
	statistics on how well the list would be compressed.)
	"""
	# xs is the list of phone numbers.
	# TODO: Fill up your code here, and set ts to the final answer.
	ts = []
		
	# This returns the final list of phone numbers.
	return list(compress_numbers_helper(ts))

def compress_numbers_stats(xs, ys):
	"""
	This function evaluates the compression rate of the compress_numbers function.
	The formula is:
	no. of chars used before compression / no. of chars used after compression
	ignoring whitespace.
	"""
	x = len(xs) * 4 # every phone number in the uncompressed list uses 4 chars
	y = sum(len(y) for y in ys)
	return y / x

class TestCompressNumbers(unittest.TestCase):
	def test_compress_numbers(self):
		f = compress_numbers
		self.assertEqual(f([1123]), ['1123'])
		self.assertEqual(f([1123, 1124, 1125]), ['1123-5'])
		self.assertEqual(
			f([1123, 1129, 1130, 1131, 1145]),
			['1123', '1129-31', '1145']
		)
		self.assertEqual(
			f([1123, 1124, 1125, 1126, 1129, 1130, 1131, 1132, 1298, 1299, 1300, 1401, 1903]),
			['1123-6', '1129-32', '1298-300', '1401', '1903']
		)

		print(compress_numbers_stats(
			[1123, 1124, 1125, 1126, 1129, 1130, 1131, 1132, 1298, 1299, 1300, 1401, 1903],
			['1123-6', '1129-32', '1298-300', '1401', '1903']
		))

if __name__ == '__main__':
	unittest.main()