3
$\begingroup$

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)

Improve this question
$\endgroup$
  • 1
    $\begingroup$ By the way, I came to the formal name of the "logo turtle" is Freeman encoding, after H. Freeman's paper, “On the encoding of arbitrary geometric configuration” $\endgroup$ – pablochacin Oct 4 '15 at 8:43
2
$\begingroup$

Hint: Find some constant $C$ such that if the turtle ever crosses its own path, then it must hit one of the last $C$ segments in the path. (I think that $C=5$ should work.)

Improve this answer
$\endgroup$
  • $\begingroup$ If a turtle walks, say, up and down for a very long time, like this: `` /\/\/\/\.../\ `` and then makes a run for the beginning of the path, and crosses there, it might take a lot more segments than 5. $\endgroup$ – wvxvw Oct 3 '15 at 21:11
  • $\begingroup$ @wvxvw Try constructing such a path. Don't forget that the turtle rotates 90 degrees each turn and always moves. $\endgroup$ – Yuval Filmus Oct 3 '15 at 21:17
  • $\begingroup$ This depends on whether turtle can walk "negative distances". I.e. if it can walk negative one to south, which would be the same as walking one to the north. The description doesn't say this isn't possible, but this isn't in the example, so I don't know. $\endgroup$ – wvxvw Oct 3 '15 at 21:19
  • 1
    $\begingroup$ @wvxvw Read the description very carefully. It uses the word positive. $\endgroup$ – Yuval Filmus Oct 3 '15 at 21:26
  • $\begingroup$ Oh, right, I see now. $\endgroup$ – wvxvw Oct 3 '15 at 21:27
1
$\begingroup$

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.

enter image description here

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. enter image description here

From then on, the inward spiral obeys the following pattern: enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.