Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
36-liner: precomputed range with priority queue solution in Speedy category for Power Plants by przemyslaw.daniel
def find_connected(node, power, network):
stack, visited = [(node, power)], set()
while stack:
node, power = stack.pop()
if power < 0:
continue
visited |= {node}
for node_a, node_b in network:
stack += [(node_b, power-1)]*(node_a == node)
stack += [(node_a, power-1)]*(node_b == node)
return visited
def init(network, plants, nodes):
result = {}
for node in nodes:
result[node] = {}
for power in plants:
result[node][power] = find_connected(node, power, network)
return result
def power_plants(network, plants):
from heapq import heappop, heappush
all_nodes = set(sum(network, ()))
power = init(network, plants, all_nodes)
queue = [(0, set(), all_nodes, plants, set())]
while queue:
_, connected, nodes, plants, result = heappop(queue)
if len(connected) == len(all_nodes):
return dict(result)
if not plants:
continue
plant = plants.pop()
for node in nodes:
_connected = connected | power[node][plant]
heappush(queue, (-len(_connected), _connected, nodes-{node},
plants[:], result | {(node, plant)}))
July 22, 2019
Comments:
