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 flpo
from itertools import chain
def most_crucial(net, users):
nodes = set(chain.from_iterable(net))
net = set(map(frozenset, net))
def value(crashed_node):
subnodes = nodes - {crashed_node}
subnet = set(c for c in net if crashed_node not in c)
node_value = users[crashed_node]
while subnodes:
node = subnodes.pop()
visited = {node}
stack = {node}
while stack:
node = stack.pop()
news = {n for n in subnodes if frozenset([n, node]) in subnet}
stack |= news - visited
visited |= news
subnodes -= news
node_value += sum(users[n] for n in visited) ** 2
return node_value
node_values = {node: value(node) for node in nodes}
return [n for n, val in node_values.items() if val == min(node_values.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!')
May 29, 2017
Comments: