Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Power Supply by Sim0000
from collections import deque
def power_supply(networks, power_plants):
net = [set(link) for link in networks]
result = set.union(*net)
for supply in power_plants:
q = deque([(supply, power_plants[supply])])
powered = set()
while q:
s, d = q.popleft()
if s in powered or d < 0: continue
powered |= {s}
q.extend(((link - {s}).pop(), d - 1) for link in net if s in link)
result -= powered
return sorted(result)
if __name__ == '__main__':
assert power_supply([['p1', 'c1'], ['c1', 'c2']], {'p1': 1}) == ['c2'], 'one blackout'
assert power_supply([['c0', 'c1'], ['c1', 'p1'], ['c1', 'c3'], ['p1', 'c4']], {'p1': 1}) == ['c0', 'c3'], 'two blackout'
assert power_supply([['p1', 'c1'], ['c1', 'c2'], ['c2', 'c3']], {'p1': 3}) == [], 'no blackout'
assert power_supply([['c0', 'p1'], ['p1', 'c2']], {'p1': 0}) == ['c0', 'c2'], 'weak power-plant'
assert power_supply([['p0', 'c1'], ['p0', 'c2'], ['c2', 'c3'], ['c3', 'p4'], ['p4', 'c5']], {'p0': 1, 'p4': 1}) == [], 'cooperation'
assert power_supply([['c0', 'p1'], ['p1', 'c2'], ['c2', 'c3'], ['c2', 'c4'], ['c4', 'c5'],
['c5', 'c6'], ['c5', 'p7']],
{'p1': 1, 'p7': 1}) == ['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}) == ['c6', 'c7'], 'complex cities 2'
print("Looks like you know everything. It is time for 'Check'!")
Dec. 6, 2016
Comments:
