Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Break Rings solution in Uncategorized category for Break Rings by capback250
import itertools
def all_rings(connections):
"""
:param connections: исходные связи
:return: set: все образованные кольца
"""
return set(itertools.chain(*connections))
def reduced_connections(connections, ring):
"""
:param connections: исходные связи
:param ring: удаляемое кольцо
:return: list сетов со связями без удаленного кольца
"""
return [x for x in connections if ring not in x]
def links_of_ring(connections, ring):
"""
:param connections:
:param ring:
:return: считаю линки от узла ( кольца )
"""
return [x for x in connections if ring in x]
def finder(connections, attempt, counter=0):
# рекурсия возвращала None, хотя принтовалось корректно, ЯННП и сделал через вайл
while connections:
rings, rings_after_delete, ring_links = all_rings(connections), [], [] # начальное к-во узлов и пустые массивы
for ring in rings:
rings_after_delete.append([ring, len(all_rings(reduced_connections(connections, ring)))]) # для каждого узла добавляю инфо о к-ве колец оставющися после удаления
ring_links.append([ring, len(links_of_ring(connections, ring))]) # считаю сколько линков из узла выходит для второго варианта
if len(set([y for x,y in rings_after_delete])) > 1: # проверяю что после удаления хотя бы 1лй из вершин можно уменишть коннекты
connections = reduced_connections(connections, sorted(rings_after_delete, key=lambda x:x[1])[0][0]) # уменьшаю коннекты
counter += 1
else: #если удаление колец дает одинаковй рез-т, дропаю самый загруженный коннектами узел
try:
connections = reduced_connections(connections, sorted(ring_links, key=lambda x:x[1], reverse=True)[attempt][0]) # уменьшаю коннекты
except IndexError:return
counter += 1
return counter
def break_rings(connections):
return min([finder(connections, x) for x in range(10) if finder(connections, x)])
Dec. 12, 2015