Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Set-based approach solution in Clear category for Wild Dogs by JamesArruda
from collections import defaultdict
from itertools import combinations
from math import sqrt
def _get_line(pt1, pt2):
"""
Return the standard form coefficients of a line from two points.
The points must be in (x, y) form.
"""
try:
slope = (pt1[1] - pt2[1]) / (pt1[0] - pt2[0])
intercept = pt1[1] - slope * pt1[0]
a, b, c = slope, -1, intercept
except ZeroDivisionError:
a = 1
b = 0
c = - pt1[0]
return a, b, c
def _get_lines(coords):
"""
Return a dictionary of standard form lines and the points they pass through.
coords is a list of (x, y) points.
"""
lines = defaultdict(set)
for pt1, pt2 in combinations(coords, 2):
if pt1 == pt2:
continue
a, b, c = _get_line(pt1, pt2)
lines[a, b, c].add(tuple(pt1))
lines[a, b, c].add(tuple(pt2))
return lines
def _distance(a, b, c, x, y):
"""
Return the distance from a standard form line and a point.
"""
num = abs(a * x + b * y + c)
den = sqrt(a**2 + b**2)
return num / den
def wild_dogs(coords):
lines = _get_lines(coords)
# Find the line with the most dogs and the least distance
# That's the minimum of negative dogs and distance
sorted_lines = sorted(
lines,
key=lambda x: (
-len(lines[x]),
_distance(*x, 0, 0)
),
)
line = sorted_lines[0]
dist = _distance(*line, 0, 0)
use_dist = dist if dist // 1 == dist else round(dist, 2)
return use_dist
if __name__ == '__main__':
print("Example:")
print(wild_dogs([(7, 122), (8, 139), (9, 156),
(10, 173), (11, 190), (-100, 1)]))
#These "asserts" using only for self-checking and not necessary for auto-testing
assert wild_dogs([(7, 122), (8, 139), (9, 156),
(10, 173), (11, 190), (-100, 1)]) == 0.18
assert wild_dogs([(6, -0.5), (3, -5), (1, -20)]) == 3.63
assert wild_dogs([(10, 10), (13, 13), (21, 18)]) == 0
print("Coding complete? Click 'Check' to earn cool rewards!")
Sept. 11, 2018
