Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
21-liner: Dynamic programming to get scopes, heapq to minimize unsupplied cities solution in Clear category for Power Plants by Phil15
from heapq import heappop, heappush
def power_plants(network, ranges):
# Get cities and make the graph.
cities, G = set(), {}
for A, B in network:
G.setdefault(A, []).append(B)
G.setdefault(B, []).append(A)
cities |= {A, B}
# Dynamic programming: get all possible scopes from every city/range.
scopes = {(city, 0): {city} for city in cities}
for r in range(max(ranges)):
for A in cities:
scopes[A, r+1] = scopes[A, r].union(*(scopes[B, r] for B in G[A]))
# Priority queue: minimizing the number of unpowered cities, until 0.
pqueue = [(len(cities), sorted(ranges), cities, [], cities)]
while pqueue:
_, (*ranges, r), unpowered, placements, without_plant = heappop(pqueue)
for A in without_plant: # Place a power plant of range r in city A.
new_unpowered = unpowered - scopes[A, r]
if not new_unpowered: # All cities are powered now.
return dict(placements + [(A, r)])
if ranges: # Continue while there is a power plant to place.
heappush(pqueue, (len(new_unpowered), ranges, new_unpowered,
placements + [(A, r)], without_plant - {A}))
July 23, 2019
Comments:
