Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Count Chains. First solution in Uncategorized category for Count Chains by vvm70
from typing import List, Tuple
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
chains = [{i, j} for i, (x1, y1, r1) in enumerate(circles[:-1]) for j, (x2, y2, r2) in enumerate(circles[i+1:], i+1) if (r2 - r1)**2 < (x2 - x1)**2 + (y2 - y1)**2 < (r2 + r1)**2]
s = []
while chains:
s.append(chains.pop(0))
while [y for y in chains if s[-1] & y]:
for x in [y for y in chains if s[-1] & y]:
s[-1] |= chains.pop(chains.index(x))
return len(circles) + len(s) - sum(len(x) for x in s)
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!")
June 20, 2020
