Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Black Holes by colinmcnicholl
from itertools import combinations
from math import acos, hypot, pi
# Software model spec item 5. If distance between different black holes is equal, then lefmost should merge first.
left = lambda hole_a, hole_b: min(hole_a[0], hole_b[0])
area = lambda r: r**2 * pi
def distance(hole_a, hole_b):
"""input: two lists of format(x, y, r) each representing a hole.
output: a float, the distance between the centers of the pair of holes
"""
# Unpacking a 3-tuple but only using the first and second values.
x1, y1, _ = hole_a
x2, y2, _ = hole_b
# hypot(x, y) is a function in the math module that returns the euclidean norm, sqrt(x*x + y*y)
return hypot(x1-x2, y1-y2)
def intersection_area(hole_a, hole_b, d):
# radius of hole "a" is at last index in the 3-tuple. Same for hole "b".
r1, r2 = hole_a[-1], hole_b[-1]
# If sum of the radii for the pair of holes being compared is less than the distance between them then no intersection.
if r1 + r2 <= d:
return 0
# If radius of bigger hole is > radius smaller hole + distance between the pair smaller hole lies inside bigger.
if r1 > d + r2:
return area(r2)
''' http://mathworld.wolfram.com/Circle-CircleIntersection.html (equation 14)
s equals y^2 / d^2, where y is the half length of the chord connecting the cusp of the lens (two circles
intersect in a region shaped like an asymmetric lens) and d is the distance between the circle centers.'''
s = (2 * d * r1)**2 - (d**2 + r1**2 - r2**2)**2
d1 = (d**2 + r1**2 - r2**2) / (2 * d * r1)
d2 = (d**2 + r2**2 - r1**2) / (2 * d * r2)
# The area of intersection.
return r1**2 * acos(d1) + r2**2 * acos(d2) - 0.5 * s**0.5
def checkio(data):
# Change each 3-tuple to a list
holes = [list(hole) for hole in data]
while True:
''' "pairs" is a set list of format (distance between 2 holes named "a" and "b",
the x co-ordinate of the hole from the pair which if furthest to the left,
list of x, y, r for hole "a" and list of x, y, r for hole "b".'''
pairs = sorted((distance(hole_a, hole_b), left(hole_a, hole_b), hole_a, hole_b) for hole_a, hole_b in combinations(holes, 2))
for d, _, hole_a, hole_b in pairs:
# As long as "pairs" is not an empty list, execute this block.
# Sort ascending (smaller hole on left) the pairs of holes by the radius (last index in the list)
smaller, bigger = sorted((hole_a, hole_b), key=lambda x: x[-1])
# Call lambda function area on the radius (last element in list) of the pair of holes and assign to A1, A2
A1, A2 = area(bigger[-1]), area(smaller[-1])
# Call intersection_area function, passing bigger, smaller: each a list of [x, y, r], and d, distance between the pair of holes.
A_inter = intersection_area(bigger, smaller, d)
if A_inter >= 0.55 * A2 and A1 >= 1.2 * A2:
# Both conditions for merger met. Calculate new radius for bigger hole.
bigger[-1] = ((A1 + A2) / pi)**0.5
# Remove the smaller hole that has been merged.
holes.remove(smaller)
# Jump out of for loop. Go back up to "pairs"
break
# "pairs" is an empty list which equals False and while loop will end.
else:
break
return [(x, y, round(r, 2)) for (x, y, r) in holes]
if __name__ == '__main__':
# These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio([(2, 4, 2), (3, 9, 3)]) == [(2, 4, 2), (3, 9, 3)]
assert checkio([(0, 0, 2), (-1, 0, 2)]) == [(0, 0, 2), (-1, 0, 2)]
assert checkio([(4, 3, 2), (2.5, 3.5, 1.4)]) == [(4, 3, 2.44)]
assert checkio([(3, 3, 3), (2, 2, 1), (3, 5, 1.5)]) == [(3, 3, 3.5)]
Sept. 29, 2017
Comments:
