Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
connection components after removal of node solution in Clear category for City's Happiness by maybe
def most_crucial(net, users):
def happiness(conn_sets,users):
return sum( sum(users[node] for node in cs)**2 for cs in conn_sets )
def find_connected_sets(net):
remain=set(nn[0] for nn in net) | set(nn[1] for nn in net)
edges=net[:]
conn_sets = []
while len(remain)>0:
node=remain.pop()
cs = set([node])
for edge in edges:
if len(cs.intersection(edge))>0:
cs |= set(edge)
remain -= set(edge)
conn_sets.append(cs)
# print('cs', net, conn_sets)
return conn_sets
def remove_node(net,node):
return [nn for nn in net if node not in nn]
nodes = set(nn[0] for nn in net) | set(nn[1] for nn in net)
residues=dict()
# print(net,users,nodes)
net += [[node,node] for node in nodes] # node connected to itself
for node in nodes:
residues[node]= (
happiness( find_connected_sets(remove_node(net,node)),users )
+ users[node] )
# print(residues)
return [node for node in nodes if residues[node]==min(residues.values())]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert most_crucial([
['A', 'B'],
['B', 'C']
],{
'A': 10,
'B': 10,
'C': 10
}) == ['B'], 'First'
assert most_crucial([
['A', 'B']
],{
'A': 20,
'B': 10
}) == ['A'], 'Second'
assert most_crucial([
['A', 'B'],
['A', 'C'],
['A', 'D'],
['A', 'E']
],{
'A': 0,
'B': 10,
'C': 10,
'D': 10,
'E': 10
}) == ['A'], 'Third'
assert most_crucial([
['A', 'B'],
['B', 'C'],
['C', 'D']
],{
'A': 10,
'B': 20,
'C': 10,
'D': 20
}) == ['B'], 'Forth'
print('Nobody expected that, but you did it! It is time to share it!')
Dec. 21, 2019
