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 freeman_lex
def most_crucial(net: list[list[str]], users: dict[str, int]) -> list[str]:
# Calculate the initial crucial value as the square of the sum of all user values
crucial_val = sum(users.values()) ** 2
# Iterate over each node and its associated user value
for nod, happy in users.items():
# Create a copy of all nodes except the current one, represented as sets
(net1 := list(map(set, users.keys()))).remove({nod})
# Create a new network by adding connections that don't involve the current node
net1 += [set(connection) for connection in net if nod not in connection]
# Process each subnet in the network
while net1:
# Take the first subnet from the list
subnet = net1.pop(0)
# Find and merge overlapping connections in the subnet
while True:
# Create a copy of the remaining connections in the subnet
net2 = [connection.copy() for connection in net1]
# Merge any overlapping connections with the current subnet
for connection in net2:
if subnet & connection:
subnet |= connection
net1.remove(connection)
# If no more connections are merged, exit the loop
if net2 == net1:
break
# Add the sum of user values in the subnet, squared, to the happiness of the current node
happy += sum(users[nod] for nod in subnet) ** 2
# Check if the current happiness is less than or equal to the current crucial value
if happy <= crucial_val:
# If the happiness is less, update the crucial value and reset the crucial nodes list
if happy < crucial_val:
crucial_val = happy
crucial_nodes = []
# Add the current node to the list of crucial nodes
crucial_nodes.append(nod)
# Return the list of crucial nodes
return crucial_nodes
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 16, 2023
Comments:
