Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Colored connected components solution in Clear category for Count Chains by Phil15
from math import hypot
from itertools import combinations
def intersect(x1, y1, r1, x2, y2, r2):
return abs(r1 - r2) < hypot(x1 - x2, y1 - y2) < r1 + r2
def count_chains(circles):
# Look all pairs to see if they intersects.
G = {c: set() for c in circles}
for c1, c2 in combinations(circles, 2):
if intersect(*c1, *c2):
G[c1].add(c2); G[c2].add(c1)
# Coloring the graph (thanks to DFS).
color, colors = 0, {}
for start in circles:
if start not in colors:
color += 1 # We need a new color.
stack = [start]
while stack:
node = stack.pop()
if node not in colors:
colors[node] = color
# Add to the stack all unvisited neighbors of the node.
stack.extend(G[node] - colors.keys())
return color
Feb. 1, 2020
Comments: