Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Network Attack by tkujiraski
def capture(matrix):
n = len(matrix)
# only the first node has been attacked and affected(matrix[0][0]=0)
attacked = [False]*n
attacked[0] = True
time = 0
while True:
time += 1
# check newly attacked nodes
for i in range(n):
#if the node is affected, all the connected nodes to it are attacked
if attacked[i] and matrix[i][i] == 0:
for j in range(n):
if matrix[i][j]:
attacked[j] = True
# attacked nodes are decreased in security level and security level of affected nodes is 0
for i in range(n):
if attacked[i] and matrix[i][i] > 0:
matrix[i][i] -= 1
# check if all nodes are taken
check = 0
for i in range(n):
check += matrix[i][i]
if not check: #all noded are taken
break;
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 24, 2016