Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Count Chains by parfenov1976
from typing import List, Tuple
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
groups = []
i = 0
while i < len(circles): # creating graph of circles, intersecting circles is neighbors
current_circle = circles.pop(0)
group = []
group.append(current_circle)
for circle in circles:
if intersect(current_circle, circle):
group.append(circle)
groups.append(group)
circles.append(current_circle)
i += 1
count = 0 # initialising counter of intersecting circles groups
visited = [False] * len(groups) # list of visited circles
while False in visited: # cycle to walk not visited circles
dfs(visited.index(False), visited, groups, circles)
count += 1
return count
def dfs(v, visited, groups, circles):
"""
Walking graph of circles with Depth-First-Search algorithm
"""
visited[v] = True
for w in groups[v]:
if not visited[circles.index(w)]:
dfs(circles.index(w), visited, groups, circles)
def distance(a, b):
"""
Distance between centers of circles
"""
return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def intersect(c1, c2):
"""
Checks for intersections
"""
dist = distance(c1[0:2], c2[0:2])
if dist + min(c1[2],c2[2]) <= max(c1[2],c2[2]): #inclusion check
return False
return dist < c1[2] + c2[2]
if __name__ == '__main__':
print("Example:")
print(count_chains([(1, 1, 1), (4, 2, 1), (4, 3, 1)]))
# 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!")
Aug. 4, 2021
Comments:
