ditto.py

import unittest
from collections import defaultdict

''' 
find_lines
ON^2 complexity find lines eq with ON space extra space complexity (not counting retval) 
returns array of arrays of points
'''
def find_lines(points):

    assert len(points) == len(set(points)), "find lines doesn support duplicate points"
    retval = []
    if len(points) > 1:
        for i, point_i in enumerate(points):
            ignore_slopes = set()
            slopes = defaultdict(list)
            for j, point_j in enumerate(points):
                if i != j:
                    slope = find_slope(point_i, point_j)
                    if j < i:
                        ignore_slopes.add(slope)
                    elif slope not in ignore_slopes:
                        slopes[slope].append(point_j)
            for line in slopes.values():
                if len(line) > 1:
                    retval.append([point_i] + line)
    return retval

'''
find_slope
helper function for find_lines
returns slope of two points
'''
def find_slope(point_i, point_j):
    if point_i[0] == point_j[0]:
        return 0
    if point_j[1] == point_i[1]:
        return float("inf")
    return float(point_j[1] - point_i[1])/float(point_i[0] - point_j[0])


'''
Unit Tests
'''
class AppTestCase(unittest.TestCase):
    @classmethod
    def assert_equal(cls, line1, line2):
        print(" asset_equal")
        print(line1)
        print(line2)
        assert len(line1) == len(line2)
        for i in range(0, len(line1)):
            assert line1[i] == line2[i]

    def test_empty_list(self):
        self.assert_equal(
            find_lines([]), 
            []
        )
    def test_horizonal(self):
        self.assert_equal(
            find_lines([(0,0), (1, 0), (2, 0), (67,7)]), 
            [[(0,0), (1, 0), (2, 0)]]
        )
    def test_horizonal_4(self):
        self.assert_equal(
            find_lines([(0,0), (1, 0), (2, 0), (3, 0), (99,99)]), 
            [[(0,0), (1, 0), (2, 0), (3, 0)]]
        )
    def test_vertical(self):
        self.assert_equal(
            find_lines([(0,0), (0, 1), (0, 2), (99,99)]), 
            [[(0,0), (0, 1), (0, 2)]]
        )
    def test_both(self):
        self.assert_equal(
            find_lines([(0,0), (1, 0), (2, 0), (99,99), (0, 1), (0, 2)]), 
            [
                [(0,0), (0, 1), (0, 2)],
                [(0,0), (1, 0), (2, 0)]
            ]
        )
    def test_diagonal(self):
        self.assert_equal(
            find_lines([(0,0), (1, 0), (2, 0), (0, 1), (0, 2), (1,1), (2,2), (99,99)]), 
            [
                [(0,0), (0, 1), (0, 2)],
                [(0,0), (1, 1), (2, 2), (99, 99)],
                [(0,0), (1, 0), (2, 0)],
                [(2, 0), (0, 2), (1, 1)]
            ]
        )



if __name__ == '__main__':
    unittest.main()