Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving

Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving

You are given a list of n float numbers x_1, x_2, x_3, … x_n, where x_i > 0. A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counter-clockwise).
Write an single-pass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's self-intersecting)
e.g.
2 1 1 2 -> crosses
1 2 3 4 -> doesn't cross

Note that, the traveller is actually moving in spiral (either decreasing or increasing) with only exception that while moving in a outward (or increasing) spiral the traveller can change its direction to a inward (or decreasing) spiral.

So, it is clear that the travelers path doesn't cross as long as the spiral in increasing or decreasing. But if the traveler starts with a increasing spiral and then at some point it moves into an decreasing spiral, we need to check whether the changing move itself crosses the increasing spiral the traveller was moving on just before the move.

For example, if the moves are s1=[2, 1, 4, 4, 3, 2, 2, 1, 1] the we can see that there is a increasing spiral and then it changes to a inward spiral with no self-intersection. In case of s2=[2, 1, 4, 4, 3, 3, 2, 1, 1] we can see that 6th move intersect with first move. (s= start, e=end)

Read full article from Self-Intersecting spiral moves - Algorithms and Problem SolvingAlgorithms and Problem Solving