Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Network Attack by UFO665
# migrated from python 2.7
def connectedComps(dctComps, matrix, iComp, bInfected=True):
return [i for i, val in enumerate(matrix[iComp]) if dctComps[i]["infected"] is bInfected and val == 1]
def infectComps(dctComps, lstComps):
for key, val in dctComps.items():
if key in lstComps:
val["infected"] = True
def minsBefore(dctComps, lstComps):
return min([val["mins"] for key, val in dctComps.items() if key in lstComps])
def capture(matrix):
dctComps = {i: {"infected": i == 0, "mins": matrix[i][i], "minsBefore": 0} for i in range(len(matrix[0]))}
lstLastInfected = [0]
while not all(val["infected"] for val in dctComps.values()):
lstComps = []
for comp in lstLastInfected:
lstComps += connectedComps(dctComps, matrix, comp, False)
lstComps = list({}.fromkeys(lstComps).keys())
for key, val in dctComps.items():
if key in lstComps:
lstConnected = set(lstLastInfected).intersection(connectedComps(dctComps, matrix, key))
lstMins = [matrix[i][i] + dctComps[i]["minsBefore"] for i in lstConnected]
if lstMins:
val["mins"] += min(lstMins)
val["minsBefore"] = minsBefore(dctComps, lstConnected)
infectComps(dctComps, lstComps)
lstLastInfected = lstComps
return max(val["mins"] for val in dctComps.values())
Dec. 21, 2015
Comments:
