Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Network Attack by Rounin
import math
def capture(matrix):
distances = []
visited = set()
for row in matrix:
distances.append(math.inf)
distances[0] = 0
queue = [0]
while len(queue) > 0:
queue = sorted(queue, key=lambda a: -distances[a])
current = queue.pop()
visited.add(current)
for neighbour in range(len(matrix)):
if neighbour != current and matrix[current][neighbour] == 1 and neighbour not in visited:
distances[neighbour] = min(distances[neighbour], distances[current]+matrix[neighbour][neighbour])
queue.append(neighbour)
return max(distances)
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 21, 2017