Last active
October 28, 2016 01:06
-
-
Save resalisbury/81ad3c996de0e15ac056b23b98f2dcf1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| README: | |
| Side Note: | |
| I've never used attrs before, so thought it would be fun to try them out | |
| see https://glyph.twistedmatrix.com/2016/08/attrs.html for an explanation of attrs | |
| Runtime Complexity: | |
| I originaly wrote as nexted for loops, which is O(n^2), but switched to | |
| using combinations to reduce runtime somewhat to O(n choose k) | |
| I'm not sure there's anyway to get faster than that, since it seems you have | |
| to know what all the possible combinations of points are to know about all | |
| possible lines. | |
| For the future, could add support for verticle lines, but didnt seem necessary | |
| for this exercise... | |
| """ | |
| import itertools | |
| # pip install attrs | |
| # https://glyph.twistedmatrix.com/2016/08/attrs.html | |
| import attr | |
| from attr.validators import instance_of | |
| ############################# | |
| # classes # | |
| ############################# | |
| @attr.s | |
| class P(object): | |
| """ | |
| Point | |
| x coord | |
| y coord | |
| """ | |
| x = attr.ib(validator=instance_of(float)) | |
| y = attr.ib(validator=instance_of(float)) | |
| @attr.s | |
| class Line(object): | |
| """ | |
| WARNING: does not support verticle lines. ie x = 2 | |
| """ | |
| slope = attr.ib(validator=instance_of(float)) | |
| yi = attr.ib(validator=instance_of(float)) # y intercept | |
| @classmethod | |
| def create_from_points(cls, p1, p2): | |
| """ | |
| create a line from two points | |
| if the two points are on a verticle line return None | |
| """ | |
| rise, run = (p2.y - p1.y), (p2.x - p1.x) | |
| if run == 0: | |
| # does not support verticle lines... | |
| return None | |
| slope = rise / run | |
| yi = p1.y - slope * p1.x | |
| return cls(slope, yi) | |
| ############################# | |
| # solution # | |
| ############################# | |
| def _find_lines(points): | |
| """ | |
| finds all possible combinations of lines for a given set of points | |
| args: points = List of Points (Class P) | |
| returns: dictionary (K = Line, Value = set of points) | |
| example: | |
| _find_lines[P(0., 0.), P(1., 1.), P(3., 4.), P(2., 2.)]() => | |
| { | |
| Line(slope=1.0. yi=0.0): set([P(x=0.0, y=0.0), | |
| P(x=1.0, y=1.0), | |
| P(x=2.0, y=2.0)]) | |
| etc... | |
| } | |
| """ | |
| lines = {} | |
| p_combinations = itertools.combinations(points, 2) | |
| for p1, p2 in p_combinations: | |
| l = Line.create_from_points(p1, p2) | |
| exists = lines.get(l, False) if l else False # skip if none is returned, which implies a verticle line | |
| if exists: | |
| lines[l] = lines[l] | set([p1, p2]) | |
| else: | |
| lines[l] = set([p1, p2]) | |
| return lines | |
| def lines_with_more_than_n_points(points, n_points=2): | |
| """ | |
| returns the lines that have greater than n_points from a list of points | |
| """ | |
| lines = _find_lines(points) | |
| return [line for line, points in lines.iteritems() if len(points) > n_points] | |
| ############################# | |
| # tests # | |
| ############################# | |
| def test(points, expected): | |
| assert lines_with_more_than_n_points(points) == expected | |
| test([], []) | |
| test([P(0., 0.)], []) | |
| test([P(0., 0.), P(1., 1.)], []) | |
| test([P(0., 0.), P(1., 1.), P(2., 2.)], [Line(slope=1.0, yi=0.0)]) | |
| test([P(0., 0.), P(1., 1.), P(2., 3.)], []) | |
| test([P(0., 0.), P(1., 1.), P(2., 2.), P(3., 4.)], [Line(slope=1.0, yi=0.0)]) # Provided example | |
| test([P(0., 0.), P(1., 1.), P(2., 2.), P(0., 3.), P(1., 6.), P(2., 9.)], | |
| [Line(slope=3.0, yi=3.0), Line(slope=1.0, yi=0.0)]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment