DEBUG = True

def partial_digest(L):
	L.sort()
	width = L[-1] # Last Element
	del L[-1]
	X = [0, width]
	place(L,X)
	
def place(L,X):
	if(len(L) == 0): 
		print X
		return
	else:
		if DEBUG: print "L:",L,"X:",X
	# L is already sorted, so the max element will always be the last element
	y = L[-1]
	
	if check_lengths(y,L,X):
		remove_lengths(y,L,X)
		X += [y] # Add y to X
		X.sort()
		place(L,X)
		X.remove(y)
		add_lengths(y,L,X)
	y = abs(X[-1] - y)
	if check_lengths(y,L,X):
		remove_lengths(y,L,X)
		X += [y] # Add (width - y) to X
		X.sort()
		place(L,X)
		X.remove(y)
		add_lengths(y,L,X)
	
def add_lengths(y, L, X):
	for x in X:
		L += [abs(y - x)]
	L.sort()

def check_lengths(y, L, X):
	for x in X:
		if abs(y - x) not in L:
			return False
	return True

def remove_lengths(y,L,X):
	for x in X:
		L.remove(abs(y - x))

# Page 119 example
list = [1,1,1,2,2,3,3,3,4,4,5,5,6,6,6,9,9,10,11,12,15]
print "List 1:",list
partial_digest(list)
# Page 89 example
list = [2,2,3,3,4,5,6,7,8,10]
print "List 2:",list
partial_digest(list)

# Tests
if DEBUG:
	y = 3
	L = [2,3,3,4,5,6,7]
	X = [0,2,10]
	# Tests for check_lengths function
	print check_lengths(y,L,X) == False
	y = 7;
	print check_lengths(y,L,X) == True
	# Tests for remove_lengts function
	remove_lengths(y, L, X)
	print  L == [2,3,4,6]
	# Tests for add_lengths function
	y = 2
	X = [1,3,4,5]
	L = []
	add_lengths(y,L,X)
	print L == [1,1,2,3]