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 arbores401
def find(grp, a):
if grp[a] == a:
return a
grp[a] = find(grp, grp[a])
return grp[a]
def union(grp, a, b):
x, y = sorted([find(grp, a), find(grp, b)], key=grp.__getitem__)
if x != y:
grp[y] = x
def score_when_city_removed(net, users, remove_city):
vs = [v for v in users.keys() if v != remove_city]
es = [e for e in net if remove_city not in e]
grp = {v: v for v in vs}
for e in es:
union(grp, *e)
grp_scrore = [sum(users[v] for v in vs if grp[v] == g) for g in set(grp)]
return sum(x * x for x in grp_scrore) + users[remove_city]
def most_crucial(net, users):
citys = users.keys()
scores = [score_when_city_removed(net, users, c) for c in citys]
return [c for i, c in enumerate(citys) if scores[i] == min(scores)]
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!')
June 26, 2018
Comments: