Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Clear solution in Clear category for Count Chains by majusmisiak
from itertools import combinations
from math import hypot
from typing import List, Tuple
def intersects(c1, c2):
distance = hypot(
abs(c1[0] - c2[0]), abs(c1[1] - c2[1])
)
return abs(c1[2] - c2[2]) < distance < c1[2] + c2[2]
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
# This would be better solved using DisjointSet as in here:
# https://py.checkio.org/mission/find-friends/publications/majusmisiak/python-3/clean-approach-using-disjoint-set/
chain_list = [{c} for c in circles ]
for c1, c2 in combinations(circles, 2):
if intersects(c1, c2):
new_chain = set((c1, c2))
for chain in chain_list[:]:
if c1 in chain or c2 in chain:
new_chain = new_chain.union(chain)
chain_list.remove(chain)
chain_list.append(new_chain)
return len(chain_list)
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. 31, 2021
