Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for City's Happiness by colinmcnicholl
from collections import defaultdict
from operator import itemgetter
from copy import deepcopy
def graph_nodes(net):
G = defaultdict(set)
nodes = set()
for u, v in net:
G[u].add(v)
G[v].add(u)
nodes |= {u, v}
return G, nodes
def walk(G, s, S=set()):
P, Q = dict(), set()
P[s] = None
Q.add(s)
while Q:
u = Q.pop()
for v in G[u].difference(P, S):
Q.add(v)
P[v] = u
return P
def components(G):
comp = []
seen = set()
for u in G:
if u in seen: continue
C = walk(G, u)
seen.update(C)
comp.append(C)
return comp
def graph_with_node_crushed(G, nodes, node):
G_copy = deepcopy(G)
G_copy[node] = set()
for k in G_copy.keys():
G_copy[k].discard(node)
return G_copy
def most_crucial(net, users):
G, nodes = graph_nodes(net)
results = []
happiness = 0
for node in nodes:
new_graph = graph_with_node_crushed(G, nodes, node)
comps = components(new_graph)
connected = set()
for elem in comps:
for k, v in elem.items():
if v:
connected.update({k, v})
sum = 0
for connected_node in connected:
sum += users[connected_node]
other_node = nodes - (connected | {node})
if other_node:
happiness = sum**2 + users[node] + users[other_node.pop()]**2
else:
happiness = sum**2 + users[node]
results.append((node, happiness))
results.sort(key=itemgetter(1))
max_importance = results[0][1]
crucial = sorted([node for node, happiness in results
if happiness == max_importance])
return crucial
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!')
Nov. 9, 2019
