Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
using product and combinations solution in Clear category for Count Chains by tokyoamado
from collections import namedtuple
from itertools import chain, combinations, product
from typing import List, Set, Tuple
Circle = namedtuple('Circle', 'x y r')
def is_chain(gr1: Set[Circle], gr2: Set[Circle]) -> bool:
def is_chain_singles(c1: Circle, c2: Circle) -> bool:
return (c2.r - c1.r) ** 2 < (c2.x - c1.x) ** 2 + (c2.y - c1.y) ** 2 < (c2.r + c1.r) ** 2
return any(is_chain_singles(*p1) for p1 in product(gr1, gr2))
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
circle_set = {Circle(*c) for c in circles}
groups = {frozenset([c]) for c in circle_set}
while True:
groups_ = {
frozenset(chain.from_iterable(p))
for p in combinations(groups, 2)
if is_chain(*p)
}
if not groups_:
break
singles = circle_set - set(chain.from_iterable(groups_))
groups = groups_ | {frozenset([c]) for c in singles}
return len(groups)
March 17, 2020
