Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
scipy connected_components, not elementary mission solution in 3rd party category for Count Chains by fokusd
from typing import List, Tuple
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
from scipy.spatial.distance import euclidean
import numpy as np
# Elementary? Really? this is hard
def count_chains(circles: List[Tuple[int, int, int]]) -> int:
circles = np.array(circles)
c, r = circles[:, :2], circles[:, 2]
graph = np.zeros((len(circles), len(circles)))
for i in range(len(circles) - 1):
for j in range(i + 1, len(circles)):
if abs(r[i] - r[j]) < euclidean(c[i], c[j]) < (r[i] + r[j]):
graph[i][j] = 1
graph = csr_matrix(graph)
n_comp, _ = connected_components(csgraph=graph, directed=False)
return n_comp
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 21, 2020
