Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First: sets solution in Clear category for Count Chains by ainoneko
# The module `builtins` is not allowed on checkio
# from builtins import bool
from typing import List, Tuple
from itertools import combinations
# The circles are "chained"
# if their centers are closer than the sum of their radii
# and farther than the difference of them.
# To stay with integer numbers,
# compare the squared distances.
# def chained(a, b: Tuple[int, int, int]) -> bool:
def chained(a, b: Tuple[int, int, int]):
dist_sq = (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
rad_sum_sq = (a[2] + b[2]) ** 2
rad_diff_sq = (a[2] - b[2]) ** 2
return rad_diff_sq < dist_sq < rad_sum_sq
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
# First, suppose that the circles are all separate:
# each circle has a set containing only itself.
chains_count = len(circles)
chains = {x: {x} for x in range(len(circles))}
# Then check all possible pairs.
for pair in combinations(range(len(circles)), 2):
a, b = pair
if chained(circles[a], circles[b]):
if not (chains[a] & chains[b]): # set intersection
# Two chains are joined, so the count is decreased.
chains_count -= 1
# Join the sets...
union = chains[a] | chains[b] # set union
# and assign the joined set (the union) to each element.
for x in union:
chains[x] = union
return chains_count
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!")
July 21, 2021
Comments:
