Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Elegant OOP Solution (ready for the 3 Sendgrid Challenges) solution in Clear category for City's Happiness by bsquare
class Connections(set):
__BROKEN_NODE = frozenset('X')
def __init__(self, connections):
super().__init__(map(frozenset, connections))
def nodes(self):
return {node for connection in self for node in connection}
def connected_node(self, name):
return {node for connection in self for node in connection
if name in connection and node != name}
def connected_network(self, node, result):
connected_nodes = self.connected_node(node) - self.__BROKEN_NODE - result
result |= {node}
for other in connected_nodes:
result |= self.connected_network(other, result)
return result
def disconnect(self, nodes):
broken_links = set()
for connection in self:
if nodes & connection:
broken_links.add(connection - nodes | self.__BROKEN_NODE)
self -= {connection for connection in self if nodes & connection}
self |= broken_links
def __str__(self):
return '; '.join([f"({connection})" for connection in self])
def compute_importance(net, users, crushes, all_nodes):
connections = Connections(net)
connections.disconnect(set(crushes))
network_seen = set()
value = 0
for node in all_nodes:
if node in network_seen or not connections.connected_node(node):
continue
network = connections.connected_network(node, set())
network_seen |= network
value += (sum(value for user, value in users.items() if user in network))**2
return value + sum(value for user, value in users.items() if user in crushes)
def most_crucial(net, users):
all_nodes = {nodes for connection in net for nodes in connection}
importances_map = {node: compute_importance(net, users, [node], all_nodes) for node in all_nodes}
min_value = min(importances_map.values())
return [node for node, value in importances_map.items() if value == min_value]
Sept. 7, 2019
Comments: