Determine the move in which a LOGO turtle crosses a point that it has already visited

Question

Situation:

1. A turtle starts at (0, 0) on a cartesian graph.
2. We have a non-empty zero-indexed "moves" list that contains numbers.
3. Each number represents the distance moved.
4. 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 repeats like this forever. Therefore the directions cycle every four moves.

Goal:

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 preferably be O(n).

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.

Example Implementation

Here was my try in PHP (I think it's kind of like O(n*(m+m)) where m is the average size of the distance):

/**
 * Logo Turtle Challenge
 * This solution is somewhat space inefficient, and could become time inefficient if the distance range for a particular move is huge!
 * There is probably a solution that allows you to persist only the corner coordinates and then using line equations to figure out if they intersect.
 * The space inefficiency could be partially solved with a lazy range generator.
 * Could be further micro-optimised by only checking the coordinates on the fourth[3] movement.
 */

function logo_turtle($movements) {

    $coordinates = [0 => [0 => true]];
    $current_coordinate = [
        'x' => 0, 
        'y' => 0
    ];
    $directions = ['n', 'e', 's', 'w'];

    foreach($movements as $move => $distance){

        // cycle through the directions
        $current_direction = array_shift($directions);
        array_push($directions, $current_direction);

        // if the distance is less than 1, then skip it, but we still cycle the direction!
        if ($distance < 1) {
            continue;
        }

        // clean slate
        $coordinates_to_check = [];

        // for each direction, acquire a list of coordinates derived from its traverse
        // these coordinates will be used to check if turtle crosses its own previous path
        switch($current_direction){
            case 'n':

                $x_end = $current_coordinate['x'];
                $y_end = $current_coordinate['y'] + $distance;

                $start = $current_coordinate['y'] + 1;
                foreach(range($start, $y_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $current_coordinate['x'], 'y' => $value];
                }

            break;
            case 'e':

                $x_end = $current_coordinate['x'] + $distance;
                $y_end = $current_coordinate['y'];

                $start = $current_coordinate['x'] + 1;
                foreach(range($start, $x_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $value, 'y' => $current_coordinate['y']];
                }

            break;
            case 's':

                $x_end = $current_coordinate['x'];
                $y_end = $current_coordinate['y'] - $distance;

                $start = $current_coordinate['y'] - 1;
                foreach(range($start, $y_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $current_coordinate['x'], 'y' => $value];
                }

            break;
            case 'w':

                $x_end = $current_coordinate['x'] - $distance;
                $y_end = $current_coordinate['y'];

                $start = $current_coordinate['x'] - 1;
                foreach(range($start, $x_end) as $value){
                    $coordinates_to_check[] = [ 'x' => $value, 'y' => $current_coordinate['y']];
                }

            break;
        }

        // if the traversal meets one of the existing coordinates, then the current move is an interception
        foreach($coordinates_to_check as $xy){

            if(
                isset(
                    $coordinates[
                        $xy['x']
                    ][
                        $xy['y']
                    ]
                )
            ){
                return $move;
            }

            // add the point to the list of coordinates that has been traversed
            $coordinates[$xy['x']][$xy['y']] = true;

        }

        // update the current coordinate for the next iteration
        $current_coordinate = [
            'x' => $x_end, 
            'y' => $y_end
        ];

    }

    return -1;

}

$moves = [1, 3, 2, 5, 4, 4, 6, 3, 2];
$turtle_move = logo_turtle($moves); // returns 6

Criteria:

1. Feel free to write it in any language you want.
2. Winning algorithm is the first one that is published with an O(n) implementation.
3. With regards to algorithms with the same time complexity class, whichever code has the least amount of characters win.
4. Time limit is the best answer by 30th November 2014.

Answer 1

C, O(n), 65 95 102 bytes

After I made at least one additional test case, some more code naturally needed to be added.

Thanks to Serge Mosin for finding another bug.

k(int*m){int*i=m;for(;2[i]>*i++;);for(*i-=i[~1]*(1[i]+(i-m>2)*i[~2]>=i[-1]);2[i]<*i++;);return 1+i-m;}

Test cases:

int a[] = {1, 3, 2, 5, 4, 4, 6, 3, 2}; // -> 6
int b[] = {4, 4, 5, 7, 8, 6, 5}; // -> 6
int c[] = {1, 1, 2, 1, 1}; // -> 4

Behavior is unspecified if there is a 0 in the array, since OP didn't specify whether that counts as the path crossing itself. Also, it is assumed that the path does cross at some point.

It might be undefined behavior to have 2[i] > *i++ but in code golf, that's like (negative) bonus points.

The first loop processes the part of the path that forms an outward spiral, which continues as long as each segment is longer than the previous parallel segment. The second loop traverses an inward spiral, in which each segment is shorter than the previous segment. At the beginning of the second spiral, there needs to be an adjustment to detect a possible collision with the previous stuff.

Answer 2

Here is a solution in JavaScript

function turtle(A) {
    for (i=3;i<A.length;i++) {
        if (A[i-1] <= A[i-3] && (A[i] >= A[i-2] || A[i-1] >= A[i-3]-(A[i-5] || 0) && A[i] >= A[i-2]-A[i-4] && A[i-2] >= A[i-4]))
            return i
    }
    return -1
}

Test Cases

var a = [1, 3, 2, 5, 4, 4, 6, 3, 2] // -> 6
var b = [4, 4, 5, 7, 8, 6, 5] // -> 6
var c = [1, 1, 2, 1, 1] // -> 4
var d = [1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10] // -> 8
var e = [1, 1, 1, 1] // -> 3
var f = [1, 1, 5, 3, 3, 2, 2, 1, 1, 3] // -> 9
var g = [1, 2, 2, 1, 1] // -> -1

Basically the turtle can only cross if the line from one time ago is less than or equal to the line from three times ago. Then check two cases, one where the current line is greater than or equal to the line from two times ago, and one where the current line crosses the line from five times ago.

The question doesn't specify what happens if the turtle moves 0. If that would be considered crossing his own path it would be easy to check for. If not, it would complicate things a bit.

Answer 3

I've made this teste just yesterday. This is my Objective-C version. It not meant to be the perfect, the latest and blah blah blah that Cordiality cries for, but a enough and readable version:

Its check the segment on vertical or horizontal to check if any previous drawn will be crossed.

https://gist.github.com/dbonates/818d6cea288a81cf888f

Hope it helps, if anyone wanna improve it feel free :)

Here goes the code as asked:

#import <Foundation/Foundation.h>

// Determine the move in which a LOGO turtle crosses a point that it has already visited

BOOL isBetween(int valueToTest, int limitOne, int limitTwo) {

    if (limitOne > limitTwo) {
        return (limitTwo <= valueToTest && valueToTest <= limitOne);
    } else {
        return (limitOne <= valueToTest && valueToTest <= limitTwo);
    }
}
int stepColistionCheck(NSMutableArray *stepsArray) {

    // NSLog(@"stepsArr: [%@]", [stepsArray componentsJoinedByString:@","] );

    int cx = 0;
    int cy = 0;

    int len = (int)[stepsArray count];

    // array with x and y position on grid
    NSMutableArray *deltaArray = [NSMutableArray array];

    for (int i=0; i<len; i++) {

        int direction = i%4;

        switch (direction) {
            case 0: // going NORTH
                cy -= [stepsArray[i] integerValue];
                [deltaArray addObject:@(cy)];
                break;

            case 1: // going EAST
                cx += [stepsArray[i] integerValue];
                [deltaArray addObject:@(cx)];
                break;

            case 2: //going SOUTH
                cy += [stepsArray[i] integerValue];
                [deltaArray addObject:@(cy)];
                break;

            case 3: //going WEST
                cx -= [stepsArray[i] integerValue];
                [deltaArray addObject:@(cx)];
                break;

            default:
                break;
        }
    }

    // array de deltas produzidos
    // NSLog(@"deltaArray: [%@]\n\n", [deltaArray componentsJoinedByString:@","] );


    // testing starting from third (the first that could colide, with the first vertical     in this case)
    for (int i=3; i< len; i++) {


        //check if will test horizontal colliding or vertical
        // 0, stands for vertical, 1 for horizontal
        int orientation = i%2;

        if (orientation == 0) { //vertical

            // the x value for this vertical segment is equal do the x from previous one
            int segmentX = [deltaArray[i-1] intValue];

            // NSLog(@"- testing vertical segment at index: %d, myX = %d:", i, segmentX);

            //loop from first horizontal to here
            // j is the horizontal segment
            int previousValue;

            for (int j=1; j < i; j+=2) {



                // first test, cant be adjacents
                if (j != (i-1) && j != (i+1)) {

                    if (j < 2) {
                        previousValue = 0;
                    } else {
                        previousValue = [deltaArray[j-2] intValue];
                    }

                    // trying to find if my x (segmentX) is between the values:     previousValue e [deltaArray[j] intValue]

                    if (isBetween(segmentX, [deltaArray[j] intValue], previousValue)) {

                        // NSLog(@"\tok, found candidate horizontal contains myX at     index %d", j);

                        // that horizontal segment contains my x,
                        // now I should check for y interpolation

                        // the y for current horizontal candidate for colision,
                        // is the y value before this index on delta array

                        int canditateY;
                        canditateY = [deltaArray[j-1] intValue];

                        // the Y of this horizontal segment found (canditateY), must me     in my y range, between [deltaArray[i] intValue] and [deltaArray[    i-2] intValue]


                        if (isBetween(canditateY, [deltaArray[i] intValue], [deltaArray[    i-2] intValue])) {
                            // the candidate Y has been found on current range of y for     this segment
                            // NSLog(@"\t\t***** FOUND SEGMENT THAT CROSS at index step     %d", (i+1));
                            return (i+1);
                        }
                    }
                }
            }

        }
        else if (orientation == 1) { //horizontal

            int segmentY = [deltaArray[i-1] intValue];

            // NSLog(@"- testing horizontal in index: %d, myY = %d:", i, segmentY);

            //loop from first vertical to here
            // j is the vertical segment
            int previousValue;

            // test which includes my x
            for (int j=0; j < i; j+=2) {

                if (j<1) {
                    previousValue = 0;
                } else {
                    previousValue = [deltaArray[j-2] intValue];
                }

                // first test, cant be adjacents
                if (j != (i-1) && j != (i+1)) {
                    if (isBetween(segmentY, [deltaArray[j] intValue], previousValue)) {

                        // NSLog(@"\tcandidate vertical contains myY at index %d", j);

                        // that vertical segment contains my y,
                        // now I should check for x interpolation

                        // the x for current vertical candidate for colision,
                        // is the x value before this index on delta array

                        int canditateX;
                        if (j<1) {
                            canditateX = 0;
                        } else {
                            canditateX = [deltaArray[j-1] intValue];
                        }

                        if (isBetween(canditateX, [deltaArray[i] intValue], [deltaArray[    i-2] intValue])) {
                            // the candidate X has been found on current range of x for     this segment
                            // NSLog(@"\t\t***** FOUND SEGMENT THAT CROSS at index step     %d", (i+1));
                            return (i+1);
                        }
                    }
                }
            }
        }

        // NSLog(@"- no colision with this segment");
    }

    return -1;
}

int main(int argc, char *argv[]) {
    @autoreleasepool {

        NSMutableArray *arr = [NSMutableArray arrayWithObjects: @7, @6, @9, @5, @8, @4,     @7, @3, @5, @2, @4, @1, @6, nil]; //return 13 // collide going to north

        printf("will collide on step %d", stepColistionCheck(arr));
    }
}

Answer 4

EDIT:

The bugs were found in this solution so don't use it. Refer to this one instead. Here is rich list of different test cases (including the one showing bugs in my solution).

int a[] = {1, 1, 1, 2}; // 3
int b[] = {1, 1, 2, 1, 1}; //4
int c[] = {1, 3, 2, 5, 4, 4, 6, 3, 2}; // 6
int d[] = {4, 4, 5, 7, 8, 6, 5}; // 6
int e[] = {1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10}; // 8
int f[] = {1, 1, 5, 3, 3, 2, 2, 1, 1, 3}; // 9 <-- this is the one I failed on

---

C, O(n), 82 bytes.

This is a fix for feersum's solution. I cannot write comments so I post it here as an answer:

k(int*m){int*i=m;for(;2[i]>*i++;);for(*i-=(i-m>2)*i[~1];2[i]<*i++;);return 1+i-m;}

Here is the case where his solution fails:

int a[] = {1, 1, 2, 2, 4, 2, 1, 1, 2, 5, 10};

His function returns 6, though the correct answer is 8.

All other notes about his solution are held here as well.

Answer 5

Here is my approach done in Ruby, it uses Cramer's Rule to deduce if 2 segments cross each other. Since we are dealing only with horizontal and vertical lines maybe its an overkill but it passed all the test cases.

https://gist.github.com/Janther/089b2a4338760c057cbf

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)

  denomPositive = 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) == denomPositive

  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) == denomPositive

  # both t and s must be <= 1 so |s_numer| <= |denom| AND |t_numer| <= |denom|
  (s_numer <= denom) == denomPositive && (t_numer <= denom) == denomPositive
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

Explanation of intersects?

We have 2 segments represented by p0, p1 and p2, p3.

Let's call the vector that joins p0 and p1 "s1" and the vector that joins p2 and p3 "s2".

s1 = p1 - p0
s2 = p3 - p2

Then we can represent the 2 lines by using the starting point and the vector like this:

L1 = p0 + t * s1
L2 = p2 + s * s2

If the two lines were to cross each other we should find a single value for t and s that fulfils the following equation

p0 + t * s1 = p2 + s * s2

If we cross multiply each side with s1 we get

(p0 + t * s1) x s1 = (p2 + s * s2) x s1

Since s1 x s1 = 0

(p0 - p2) x s1 = s * (s2 x s1)

And finally

s = (p0 - p2) x s1 / (s2 x s1)

Let's follow the same steps to solve for t

(p0 + t * s1) x s2 = (p2 + s * s2) x s2
t * (s1 x s2) = (p2 - p0) x s2
t = (p2 - p0) x s2 / (s1 x s2)

Having s1 x s2 = - (s2 x s1)

t = (p0 - p2) x s2 / (s2 x s1)

We have 2 equations

s = (p0 - p2) x s1 / (s2 x s1)
t = (p0 - p2) x s2 / (s2 x s1)

Since we don't want extra calculations let's have 2 more variables

denom = s2 x s1
s3 = p0 - p2

If denom is 0 segments are parallel and extra analysis should be made if they overlap.

If 0 ≤ t ≤ 1 AND 0 ≤ s ≤ 1 the lines cross inside the given segments, otherwise they cross in some other point.

Since floating point division is more CPU demanding than comparing 2 integers the code was modified to avoid dividing but still having the logic of 0 ≤ t ≤ 1 AND 0 ≤ s ≤ 1 and I added comments on the code to explain the logic.

Here you can find the original analysis which I used. https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

Answer 6

Just adding my php solution, runs in O(n):

$arr = [1, 3, 2, 5, 4, 4, 6, 3, 2];

$sol = solution($arr);
var_dump($sol);

function solution($arr) {
    $state = 0;
    $dmax  = 0;
    $arrCount = count($arr);

    for($i = 2; $i < $arrCount; $i++) {
        switch ($state) {
            case 0:
                if($arr[$i] <= $arr[$i-2]) {
                    $dmax = ($i >= 4 && $arr[$i-4] >= $arr[$i-2]) ? $arr[$i-1] - $arr[$i-3] : $arr[$i-1];
                    $state = 1;
                }
                break;

            case 1:
                if ($arr[$i] >= $dmax) {
                    return $i+1;
                } else {
                    $dmax = $arr[$i-1];
                }
                break;

        }
    }
    return -1;
}