Codility

gistfile1.py

#!/usr/bin/python

def line_intersection(line1, line2):
    xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0])
    ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1])

    def det(a, b):
        return a[0] * b[1] - a[1] * b[0]

    div = det(xdiff, ydiff)
    if div == 0:
       return False

    d = (det(*line1), det(*line2))
    x = det(d, xdiff) / div
    y = det(d, ydiff) / div
    
    #line 1 y
    l1y = sorted([line1[0][1], line1[1][1]])
    if y < l1y[0] or y > l1y[1]:
    	return False

    #line 2 y
    l2y = sorted([line2[0][1], line2[1][1]])
    if y < l2y[0] or y > l2y[1]:
    	return False

    #line 1 x
    l1x = sorted([line1[0][0], line1[1][0]])
    if x < l1x[0] or x > l1x[1]:
    	return False

    #line 2 x
    l2x = sorted([line2[0][0], line2[1][0]])
    if x < l2x[0] or x > l2x[1]:
    	return False
   	
    return x, y

def add_way(point, count):
	new_point = list(point)
	for i in xrange(len(new_point)):
		if new_point[i] != 0:
			new_point[i] = count * new_point[i]
	return new_point

def count_points(point1, point2):
	return [point1[0]+point2[0], point1[1]+point2[1]]

def collision(cache):
	for i in xrange(0,len(cache)-2):
			if line_intersection(cache[-1], cache[i]):
				return True
	return False

def solution(A):
	directions = [[0,1], [1,0], [0,-1], [-1,0]]
	cache = list()
	current = [0,0]

	for step in xrange(len(A)):
		direction = step % 4
		new_current = count_points(current, add_way(directions[direction], A[step]))

		#add to cache
		cache.append(list([list(current), list(new_current)]))

		#clearing cache
		if len(cache) > 5:
			del cache[0]

		#testing colisions
		if step > 2 and collision(cache):
			return step+1
		current = new_current

	return False

if __name__ == "__main__":
	A = [1,3,2,5,4,4,6,3,2]
	print solution(A)