Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Power Supply by PythonLearner
from itertools import chain
def build_graph(network):
graph = {}
def add(city1, city2):
if not city1 in graph:
graph[city1] = set()
graph[city1].add(city2)
for city1, city2 in network:
add(city1, city2)
add(city2, city1)
return graph
def power_supply(network, power_plants):
graph = build_graph(network)
saved = set(power_plants)
for power_plant in power_plants:
visited = {power_plant}
current = graph[power_plant]
while current and power_plants[power_plant]:
saved.update(current)
visited.update(current)
current = set(chain(*map(graph.get, current))).difference(visited)
power_plants[power_plant] -= 1
return set(city for city in graph if city not in saved)
if __name__ == '__main__':
assert power_supply([['p1', 'c1'], ['c1', 'c2']], {'p1': 1}) == set(['c2']), 'one blackout'
assert power_supply([['c0', 'c1'], ['c1', 'p1'], ['c1', 'c3'], ['p1', 'c4']], {'p1': 1}) == set(['c0', 'c3']), 'two blackout'
assert power_supply([['p1', 'c1'], ['c1', 'c2'], ['c2', 'c3']], {'p1': 3}) == set([]), 'no blackout'
assert power_supply([['c0', 'p1'], ['p1', 'c2']], {'p1': 0}) == set(['c0', 'c2']), 'weak power-plant'
assert power_supply([['p0', 'c1'], ['p0', 'c2'], ['c2', 'c3'], ['c3', 'p4'], ['p4', 'c5']], {'p0': 1, 'p4': 1}) == set([]), 'cooperation'
assert power_supply([['c0', 'p1'], ['p1', 'c2'], ['c2', 'c3'], ['c2', 'c4'], ['c4', 'c5'],
['c5', 'c6'], ['c5', 'p7']],
{'p1': 1, 'p7': 1}) == set(['c3', 'c4', 'c6']), 'complex cities 1'
assert power_supply([['p0', 'c1'], ['p0', 'c2'], ['p0', 'c3'],
['p0', 'c4'], ['c4', 'c9'], ['c4', 'c10'],
['c10', 'c11'], ['c11', 'p12'], ['c2', 'c5'],
['c2', 'c6'], ['c5', 'c7'], ['c5', 'p8']],
{'p0': 1, 'p12': 4, 'p8': 1}) == set(['c6', 'c7']), 'complex cities 2'
assert power_supply([['c1', 'c2'], ['c2', 'c3']], {}) == set(['c1', 'c2', 'c3']), 'no power plants'
assert power_supply([['p1', 'c2'], ['p1', 'c4'], ['c4', 'c3'], ['c2', 'c3']], {'p1': 1}) == set(['c3']), 'circle'
assert power_supply([['p1', 'c2'], ['p1', 'c4'], ['c2', 'c3']], {'p1': 4}) == set([]), 'more than enough'
print("Looks like you know everything. It is time for 'Check'!")
July 14, 2018
Comments:
