Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Power Plants by kazuki.h
from collections import deque, Counter
from itertools import starmap
from functools import lru_cache
from copy import copy
from random import sample
def power_plants(network, ranges):
nodes = set([i for i, j in network]+[j for i, j in network])
ranges = sorted(ranges, key = lambda x: x*-1)
@lru_cache
def BFS_with_deep(start, deep):
if deep == 0: return ({start}, {start})
result, boundary = BFS_with_deep(start, deep-1)
new_boundary = set()
for p1, p2 in {(p1, p2) for p1, p2 in network if p1 in boundary or p2 in boundary}: new_boundary = new_boundary|{p1, p2}
return (result|new_boundary, new_boundary-result)
while True:
select_nodes = sample(nodes, len(ranges))
nodes_copy = copy(nodes)
for supply in starmap(BFS_with_deep, zip(select_nodes, ranges)):
nodes_copy -= supply[0]
if not nodes_copy: return {key:val for key, val in zip(select_nodes, ranges)}
Jan. 2, 2022
Comments:
