I was given the following problem in an test (at codility.com)
A turtle starts at (0, 0) on a cartesian graph. We have a non-empty zero-indexed "moves" list that contains positive integer numbers. Each number represents the distance moved. The first number is the distance north, the second is the distance east, the third is the distance south, the fourth is the distance west, and so forth. Therefore the directions cycle every four moves.
Find an algorithm that gives the move number that makes the turtle cross a point that it has already visited before.
The move number is the index of the "moves" list.
This algorithm should have O(n) time complexity and O(1) space complexity.
If given this move list: [1, 3, 2, 5, 4, 4, 6, 3, 2]
The move number answer is then 6. (It's the 7th move).
Draw it on a graph, the turtle will go:
(0,0) -> (0,1) -> (3,1) -> (3,-1) -> (-2,-1) -> (-2,3) -> (2,3) -> (2,-3)
At this 6 move number (7th move) it will meet (2,1) which is a point that the turtle has already crossed.
I have been struggling with for quite a time, because I intuitively think there's no way to meet both space and time complexity requirements, unless there's some hidden structural property in the problem I'm not noticing. For example, if the path does not cross itself it forms an spiral-like curve, and therefore each north move must be greater than the previous south move, and viceversa. The same applies to the east and west moves. Therefore, not meeting this property implies the curve will eventually cross itself, but gives no indication on which move does it.
My main problem is that I've not been able to identify the type or algorithmic problem this problem relates (e.g. sorting)