Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second solution in Clear category for Count Chains by mortonfox
from typing import List, Tuple
from math import hypot
def intersect(circ1, circ2):
distance = hypot(circ1[0] - circ2[0], circ1[1] - circ2[1])
# Test that the two circles intersect and not (circ1 is inside circ2 or circ2 is inside circ1)
return distance < circ1[2] + circ2[2] and not (distance + circ1[2] <= circ2[2] or distance + circ2[2] <= circ1[2])
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
chains = []
# For each circle, we first place the circle in a chain by itself and then
# check which chains intersect with it.
for circ in circles:
newchain = [circ]
nonconnected_chains = []
for chain in chains:
if any(intersect(c, circ) for c in chain):
newchain += chain
else:
nonconnected_chains.append(chain)
chains = [newchain] + nonconnected_chains
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!")
Feb. 4, 2020
Comments: