Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Attack by Amachua
from heapq import *
def capture(matrix):
current, not_infected = [], [i for i in range(1, len(matrix))]
heappush(current, (0, 0))
while not_infected:
time, node = heappop(current)
for i in not_infected[::-1]:
if matrix[node][i]:
not_infected.remove(i)
heappush(current, (time + matrix[i][i], i))
return nlargest(1,current)[0][0]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert capture([[0, 1, 0, 1, 0, 1],
[1, 8, 1, 0, 0, 0],
[0, 1, 2, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 3, 1],
[1, 0, 1, 0, 1, 2]]) == 8, "Base example"
assert capture([[0, 1, 0, 1, 0, 1],
[1, 1, 1, 0, 0, 0],
[0, 1, 2, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 3, 1],
[1, 0, 1, 0, 1, 2]]) == 4, "Low security"
assert capture([[0, 1, 1],
[1, 9, 1],
[1, 1, 9]]) == 9, "Small"
Aug. 19, 2014
