Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
build chains one circle at a time solution in Clear category for Count Chains by r.bathoorn
from typing import List, Tuple
import math
def has_intersections(c0, c1):
# c0: (x0, y0), radius r0
# c1: (x1, y1), radius r1
x0, y0, r0 = c0
x1, y1, r1 = c1
d=math.sqrt((x1-x0)**2 + (y1-y0)**2)
# non intersecting
if d >= r0 + r1 :
return False
# One circle within other
if d <= abs(r0-r1):
return False
# coincident circles
if d == 0 and r0 == r1:
return False
else:
return True
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
# chains is a list of all chains found so far
# For each circle test if it is in a chain or add it as a new chain
# If circle intercests with more than one chain add it to one chain
# and merge the matching chains together
# count number of chains
chains = []
for circle in circles:
matches = []
for chain in chains:
for testcircle in chain:
if has_intersections(circle, testcircle):
matches.append(chain)
break
# no intersection with any chain so we create a new group
if len(matches) == 0:
chains += [[circle]]
elif len(matches) > 0:
# there is at least one intersection
# add circle to the first chain then merge the chains
matches[0].append(circle)
#todo:merge the chains
merge = []
for match in matches:
merge += match
chains.remove(match)
chains.append(merge)
return len(chains)
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 24, 2021