Skip to content

Instantly share code, notes, and snippets.

@Janther
Last active June 25, 2018 20:20
Show Gist options
  • Save Janther/089b2a4338760c057cbf to your computer and use it in GitHub Desktop.
Save Janther/089b2a4338760c057cbf to your computer and use it in GitHub Desktop.
Codility Task LOGO turtle - SegmentCrossing
def intersects?(p0, p1, p2, p3)
s1_x = p1[0] - p0[0]
s1_y = p1[1] - p0[1]
s2_x = p3[0] - p2[0]
s2_y = p3[1] - p2[1]
denom = s1_x * s2_y - s2_x * s1_y
# if denom == 0 lines are parallel
# TODO: aditional check if they overlap
return false if (denom == 0)
denom_positive = denom > 0
s3_x = p0[0] - p2[0]
s3_y = p0[1] - p2[1]
s_numer = s1_x * s3_y - s1_y * s3_x
# s must be positive for posible colition
# s = s_numer / demom
return false if (s_numer < 0) == denom_positive
t_numer = s2_x * s3_y - s2_y * s3_x
# t must be positive for posible colition
# t = t_numer / demom
return false if (t_numer < 0) == denom_positive
# both t and s must be <= 1 so |s_numer| <= |denom| AND |t_numer| <= |denom|
(s_numer <= denom) == denom_positive && (t_numer <= denom) == denom_positive
end
def solution(a)
path = [[0, 0]]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
a.each.with_index do |steps, solution_index|
position = path.last
direction = directions[solution_index % 4]
path << [position[0] + steps * direction[0], position[1] + steps * direction[1]]
next if path.size <= 4
end_segment_1 = path[path.size - 1]
# Border case when the path ends at the beginning
return solution_index + 1 if end_segment_1 == [0, 0]
start_segment_1 = path[path.size - 2]
# First check is 4 moves ago
start_segment_0 = path[path.size - 5]
end_segment_0 = path[path.size - 4]
if intersects?(start_segment_0, end_segment_0, start_segment_1, end_segment_1)
return solution_index + 1
end
next if path.size <= 6
# Second check is 6 moves ago
start_segment_0 = path[path.size - 7]
end_segment_0 = path[path.size - 6]
if intersects?(start_segment_0, end_segment_0, start_segment_1, end_segment_1)
return solution_index + 1
end
end
0
end
solution [1, 3, 2, 5, 4, 4, 6, 3, 2] #=> 7
solution [1, 1, 1, 2] #=> 4
solution [1, 1, 2, 1, 1] #=> 5
solution [4, 4, 5, 7, 8, 6, 5] #=> 7
solution [1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10] #=> 9
solution [1, 1, 5, 3, 3, 2, 2, 1, 1, 3] #=> 10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment