shutdown servers

shutdown_servers.py

# given matrix of servers, servers connect to servers in their row or column. 'C' denotes a server computer.
# shutdown the servers in an order such that shutdown servers pass their data on to nearby servers, such that
# the minimum number of servers need to stay on.

# author: @robertkingnz

def make():
	M = []
	rows = 10
	cols = 20

	for i in range(rows):
		row = [''] * cols
		M.append(row)
		if i < 5:
			row[0] ='C'
		row[i] = 'C'
	M[-1][-1] = 'C'
	M[-2][-1] = 'C'
	return M

def display(M):
	for row in M:
		print(row)

def neighbours(M, i ,j):
	for i2 in range(len(M)):
		if M[i2][j] == 'C':
			yield (i2, j)
	for j2 in range(len(M[i])):
		if M[i][j2] == 'C':
			yield (i, j2)


def connected_component(M, i, j):
	parent = {}
	added = set([(i, j)])
	fringe = [(i, j)]
	while True:
		new_fringe = []
		for (i2, j2) in fringe:
			for (i3,j3) in neighbours(M, i2, j2):
				if (i3, j3) not in added:
					added.add((i3, j3))
					new_fringe.append((i3, j3))
					parent[(i3,j3)] = (i2, j2)
		if not new_fringe:
			break
		fringe = new_fringe
	return added, parent

def find_components(M):
	done = set()
	components = []
	for i in range(len(M)):
		for j in range(len(M[i])):
			if M[i][j] == 'C' and (i, j) not in done:
				cc, parent = connected_component(M, i, j)
				components.append((cc, parent))
				done.add((i, j))
				for (i2, j2) in cc:
					done.add((i2, j2))
	return components

def shutdown(component, parent):
	outside = []
	parents = set(parent.values())
	for node in component:
		if node not in parents:
			outside.append(node)

	i = 0
	done = set()
	while i < len(outside):
		child = outside[i]
		if child in parent:
			if parent[child] not in done:
				outside.append(parent[child])
				done.add(parent[child])
		i += 1
	assert(len(outside) == len(component))
	return outside[:-1]

def run():
	M = make()
	display(M)
	components = find_components(M)
	for component, parent in components:
		print('component {}'.format(component))
		print('shutdown {}'.format(shutdown(component, parent)))

run()