Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
*Line Class solution in Clear category for Wild Dogs by JimmyCarlos
import itertools
class Coordinate:
def __init__(self,x,y):
self.x = x
self.y = y
def __repr__(self):
return "({},{})".format(self.x,self.y)
def __eq__(self,other):
return (self.x,self.y) == (other.x,other.y)
def line_to(self,other):
"""Returns a Line object from this coordinate to another coordinate."""
assert type(other) == Coordinate
dx = other.x - self.x
dy = other.y - self.y
a = -dy
b = dx
c = dx*(self.y) - dy*(self.x)
return Line(a,b,c)
def distance_to(self,other) -> float:
"""Uses Pythagoras Theorem to find the distance to another Coordinate object."""
assert type(other) == Coordinate
return ((self.x-other.x)**2 + (self.y-other.y)**2)**0.5
class Line:
def __init__(self,a,b,c):
# Line is defined as ax+by=c
self.a = a
self.b = b
self.c = c
self.coords = []
def __repr__(self):
return "{}x+{}y={}".format(self.a,self.b,self.c)
def distance_to(self,other):
"""Finds the shortest distance from a Coordinate object to this line."""
assert type(other) == Coordinate
# Equation of line is ax + by = c₁
a,b,c1 = self.a,self.b,self.c
# The equation of the line perpendicular to the original line and passing through
# the new point (x₂,y₂) is bx + -ay = c₂, with c₂ = bx₂ - ay₂
c2 = b*other.x - a*other.y
# Using simultaneous equations, we can find the coordinate (x,y) where these 2 lines meet.
x = (a*c1 + b*c2) / (a**2 + b**2)
y = (b*c1 - a*c2) / (a**2 + b**2)
intersection_coordinate = Coordinate(x,y)
# Now use Pythagoras' Theorem to find the distance from the original point to the new point.
return other.distance_to(intersection_coordinate)
def wild_dogs(dogs) -> int:
# We can always get 1 dog with a distance moved of 0, so the solution must hit at least 2 dogs.
# Turn the given list to a list of Coordinate Objects
coords = [Coordinate(dog[0],dog[1]) for dog in dogs]
# Create a list to store all lines found
lines = []
# Iterate through each pair of Co-ordinates, looking for any points on this line.
for A,B in itertools.combinations(coords,2):
# If we already have this pair of coords in the lines tested, skip this pair.
if any(all(c in line.coords for c in (A,B)) for line in lines):
continue
# Create a Line object going from the first to the second coordinate.
AB = A.line_to(B)
# Put all coords on the line in the list inside the Line object. Line is defined as ax+by=c.
a,b,c = AB.a,AB.b,AB.c
for C in coords:
if a*C.x + b*C.y == c:
AB.coords.append(C)
# Put the line into the list with the others.
lines.append(AB)
# Put the lines in groups based on how many dogs they hit.
lines_grouped = [[] for i in range(0,max(len(x.coords) for x in lines)+1)]
for line in lines:
dogs_hit = len(line.coords)
lines_grouped[dogs_hit].append(line)
# Look in the last group (the one that hits the most dogs) for the shortest distance.
origin = Coordinate(0,0)
best_distance = min(line.distance_to(origin) for line in lines_grouped[-1])
return round(best_distance,2)
Sept. 15, 2018