Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Count Chains by PythonLearner
from itertools import chain
from typing import Iterable, List, Set, Tuple
Circle = Tuple[int, int, int]
Point = Tuple[int, int]
def get_square_distance(point1: Point, point2: Point) -> int:
return (point1[0]-point2[0])**2+(point1[1]-point2[1])**2
def is_inside(circle_1: Circle, circle_2: Circle) -> bool:
x1, y1, r1 = circle_1
x2, y2, r2 = circle_2
return get_square_distance((x1, y1), (x2, y2)) <= (r1 - r2) ** 2
def is_connected(circle_1: Circle, circle_2: Circle) -> bool:
x1, y1, r1 = circle_1
x2, y2, r2 = circle_2
return not is_inside(circle_1, circle_2) and get_square_distance((x1, y1), (x2, y2)) < (r1 + r2) ** 2
def find_connected(pivot_circle: Circle, circles: Iterable[Circle]) -> Set[Circle]:
return {circle for circle in circles if circle != pivot_circle and is_connected(pivot_circle, circle)}
def find_chain(circles: Iterable[Circle]) -> Set[Circle]:
circles_chain = set()
if circles:
circles_set = set(circles)
circles_chain.add(circles_set.pop())
chain_increment = set(chain.from_iterable(find_connected(circle, circles_set) for circle in circles_chain))
while chain_increment:
circles_chain = circles_chain.union(chain_increment)
circles_set = circles_set.difference(circles_chain)
chain_increment = set(chain.from_iterable(find_connected(circle, circles_set) for circle in circles_chain))
return circles_chain
def count_chains(circles: List[Circle]) -> int:
count = 0
circles_set = set(circles)
while circles_set:
circles_chain = find_chain(circles_set)
circles_set = circles_set.difference(circles_chain)
count += 1
return 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!")
March 14, 2020