Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
deque and frozensets solution in Clear category for Count Chains by Ulukai85
from typing import List, Tuple
from collections import deque
def intersect(c1, c2):
x1, y1, r1 = c1
x2, y2, r2 = c2
return abs(r1 - r2) < ((y2 - y1) ** 2 + (x2 - x1) ** 2) ** 0.5 < r1 + r2
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
graph, groups, n = {}, set(), len(circles)
for i in range(n):
graph[i] = [j for j in range(n) if intersect(circles[i], circles[j])]
for i in range(n):
visited, stack = {i}, deque(graph[i])
while stack:
current = stack.popleft()
if current in visited:
continue
stack += graph[current]
visited.add(current)
groups.add(frozenset(visited))
return len(groups)
if __name__ == '__main__':
#print("Example:")
#print(count_chains([(1, 1, 1), (4, 2, 1), (4, 3, 1)]))
#assert(count_chains([[-7,4,2],[10,-4,2],[4,-7,3],[7,-6,1],[9,2,2],[5,10,2],[2,2,2],[7,-9,3],[-5,-6,2]])) == 7
assert(count_chains([(0,0,2),(1,0,3),(3,0,1),(2,1,1),(-2,-2,1),(0,0,4),(-3,0,1)])) == 3
# These "asserts" are used for self-checking and not for an auto-testing
'''
assert count_chains([(1, 1, 1), (4, 2, 1), (4, 3, 1)]) == 2, 'basic'
assert count_chains([(1, 1, 1), (2, 2, 1), (3, 3, 1)]) == 1, 'basic #2'
assert count_chains([(2, 2, 2), (4, 2, 2), (3, 4, 2)]) == 1, 'trinity'
assert count_chains([(2, 2, 1), (2, 2, 2)]) == 2, 'inclusion'
assert count_chains([(1, 1, 1), (1, 3, 1), (3, 1, 1), (3, 3, 1)]) == 4, 'adjacent'
assert count_chains([(0, 0, 1), (-1, 1, 1), (1, -1, 1), (-2, -2, 1)]) == 2, 'negative coordinates'
print("Coding complete? Click 'Check' to earn cool rewards!")'''
Oct. 24, 2020
