patternMinor
Determine the move in which a LOGO turtle crosses a point that it has already visited
Viewed 0 times
theturtlepointvisitedmovelogohasalreadythatdetermine
Problem
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.
Example:
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)
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.
Example:
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)
Solution
Complementing Yuval's hint: the turtle will necessarily produce one (and only one, possibly infinite) outward spiral, and possibly an additional inward spiral, necessarily finite. For each of these two stages, the algorithm is a bit different.
For the first stage (see picture below) there are at most 4 reachable segments, two of them (numbers 3 and 4) possibly in two different ways $-$ from the inside, or from the outside. The blue area is completely unreachable.
For the second stage, the number of reachable segments is three. The transition between these two stages is shown in the next picture. The dotted segments are now unreachable.
From then on, the inward spiral obeys the following pattern:
For the first stage (see picture below) there are at most 4 reachable segments, two of them (numbers 3 and 4) possibly in two different ways $-$ from the inside, or from the outside. The blue area is completely unreachable.
For the second stage, the number of reachable segments is three. The transition between these two stages is shown in the next picture. The dotted segments are now unreachable.
From then on, the inward spiral obeys the following pattern:
Context
StackExchange Computer Science Q#47826, answer score: 2
Revisions (0)
No revisions yet.