Skip to content

Instantly share code, notes, and snippets.

@rich-hart
Created December 2, 2016 20:12
Show Gist options
  • Save rich-hart/c1d5248e56b468f13927ad4a9eba1c78 to your computer and use it in GitHub Desktop.
Save rich-hart/c1d5248e56b468f13927ad4a9eba1c78 to your computer and use it in GitHub Desktop.
One more update
import unittest
def find_slope(x1,y1,x2,y2):
slope = (y2 - y1) / (x2 - x1)
return slope
def find_intercept(x,y,slope):
intercept = y - slope * x
return intercept
# NOTE: runs in O(N^3) time
def solution(point_list):
point_list = [ (float(x),float(y)) for (x,y) in point_list ]
point_list = list(set(point_list)) # remove duplicates
line_list = []
for i in range(0, len(point_list)):
for j in range(i+1, len(point_list)):
for k in range(j+1, len(point_list)):
if i !=j and i!=k and j!=k:
(x1 , y1 ) = point_list[i]
(x2 , y2 ) = point_list[j]
(x3 , y3 ) = point_list[k]
#http://mathworld.wolfram.com/Collinear.html
if x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)==0.0:
#collinear!
try:
vector = find_slope(x1,y1,x2,y2)
point = (0.0,find_intercept(x1,y1,vector))
except ZeroDivisionError:
vector = "UND"
point = (x1,0.0)
line = {'vector':vector, 'point':point}
line_list.append(line)
# remove duplicate lines
line_list=[dict(t) for t in set([tuple(d.items()) for d in line_list])]
return line_list
class Test(unittest.TestCase):
def test_solution_2(self):
problem_instance = [(0, 0), (1, 1), (3, 4), (2, 2)]
expected = [
{'point': (0.0, 0.0), 'vector': 1.0}
]
returned = solution(problem_instance)
self.assertEqual(expected,returned)
def test_solution_a(self):
problem_instance = [(0, 0), (1, 1), (3, 4), (2, 2),(4,5),(5,6)]
expected = [
{'point': (0.0, 0.0), 'vector': 1.0},
{'point': (0.0, 1.0), 'vector': 1.0}
]
returned = solution(problem_instance)
self.assertEqual(expected,returned)
def test_solution_2_empty_sol(self):
problem_instance = [(0, 0), (0, 0), (0,0)]
expected = []
returned = solution(problem_instance)
self.assertEqual(expected,returned)
problem_instance = [(0, 0), (1,1), (1,1)]
expected = []
returned = solution(problem_instance)
self.assertEqual(expected,returned)
def test_solution_2_undefined(self):
problem_instance = [(0, 0), (0, 1), (0,2)]
expected = [{'point': (0.0, 0.0), 'vector': 'UND'}]
returned = solution(problem_instance)
self.assertEqual(expected,returned)
if __name__ == "__main__":
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment