Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for Network Attack by SergeyKomarov
def capture(matrix):
vertices = {i:matrix[i][i] for i in range(len(matrix))}
visited = {0}
time = 0
while any(vertices.values()):
for i,j in vertices.items():
if j == 0:
visited |= {n for n, item in enumerate(matrix[i]) if item == 1}
time += 1
for i, j in vertices.items():
if i in visited and j != 0:
vertices[i] -= 1
return time
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"
July 11, 2014
