Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second version, extremely fast, combining my first version and Phil15 solutions solution in Speedy category for Power Plants by Ylliw
from typing import Set, Tuple, List, Dict
from itertools import chain,combinations
from heapq import heappop, heappush
def power_plants(network: Set[Tuple[str, str]], ranges: List[int]) -> Dict[str, int]:
powers=[(power,ranges.count(power)) for power in sorted(set(ranges),reverse=True)]
cities=set(chain(*network))
def network_map(max_power: int) -> Dict[str, Dict[int, List[str]]]:
reachable_in_one={city:set() for city in cities}
for city_a,city_b in network:
reachable_in_one[city_a]|={city_b}
reachable_in_one[city_b]|={city_a}
cities_map={city:{0:set(city)} for city in cities}
for distance in range(0,max_power):
for city in cities:
reachable={city_b for city_a in cities_map[city][distance] for city_b in reachable_in_one[city_a]}
cities_map[city][distance+1]=reachable|cities_map[city][distance]
return cities_map
cities_map=network_map(powers[0][0])
steps=[(0,powers,set(cities),[])]
while steps:
_,((power,nb_occurences),*powers),unpowered,plants=heappop(steps)
if len(unpowered)<=nb_occurences:
return dict(plants+ [(city,power) for city in unpowered])
for combination in combinations(unpowered,nb_occurences):
new_unpowered=set(unpowered)
for city in combination:
new_unpowered-=cities_map[city][power]
if not new_unpowered:
return dict(plants+[(city,power) for city in combination])
if powers:
heappush(steps,(len(new_unpowered),powers,new_unpowered,plants+[(city,power) for city in combination]))
Nov. 7, 2019
Comments:
