5
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ This is under-specified. Be especially clear in the winning criteria. How exactly is it scored? And the rest could be written more… "nicely". \$\endgroup\$ – Ingo Bürk Nov 1 '14 at 17:47
  • \$\begingroup\$ @IngoBürk Ok I wrote it more clearly and added specifications for winning criteria. Is that alright, what else should I add? \$\endgroup\$ – CMCDragonkai Nov 2 '14 at 5:31
  • \$\begingroup\$ The winning criteria are still unclear. What are these "extra points" you're mentioning? How many do we get and how exactly do they add to the score, since the score is a complexity class? Also, this is likely to end in ties, so you should have a tie breaker. \$\endgroup\$ – Ingo Bürk Nov 2 '14 at 7:55
  • \$\begingroup\$ How would you suggest to score time complexity classes? \$\endgroup\$ – CMCDragonkai Nov 2 '14 at 10:51
  • 1
    \$\begingroup\$ Well yes, but what are we talking about at this point? The array of grid points or the array of move points? Because I've used both. On every move, I query the grid points based on the move points. This is not really O(n) because on long distance moves, you'd have to check move point and it's hence O(n * m) where m is the average distance of moves. \$\endgroup\$ – CMCDragonkai Nov 4 '14 at 5:04
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The counting is done in characters, not bytes. Since you claim O(n), it wouldn't matter anyway – it would be an automatic win. \$\endgroup\$ – Ingo Bürk Nov 2 '14 at 19:59
  • \$\begingroup\$ Thanks for the answer! Could you explain a bit more what those 2 for loops are doing? Specifically I would a like to know how your algorithm works. \$\endgroup\$ – CMCDragonkai Nov 3 '14 at 5:43
  • \$\begingroup\$ Just wanted to note that if the move is 0, then it means the turtle doesn't move anywhere, but the direction still cycles. That being said, it doesn't really matter now since I didn't specify it. \$\endgroup\$ – CMCDragonkai Nov 3 '14 at 7:10
  • \$\begingroup\$ I added a different solution below which only uses one loop, would that count as being faster? \$\endgroup\$ – ykay says Reinstate Monica Jul 21 '15 at 3:56
  • \$\begingroup\$ @ykay No, it is still O(n) which is the minimal time complexity for this problem. \$\endgroup\$ – feersum Jul 21 '15 at 4:08
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For example, given array A as defined above, the function should return 7, because the turtle touches its previous path at point (2,1) in the 7th move. But your solution returns 6 \$\endgroup\$ – Oleg Abrazhaev Jan 23 '17 at 7:20
  • \$\begingroup\$ @OlegAbrazhaev the array is 0 based so 6 is really the seventh move. -1 indicates that it doesn't cross it's path. You could change the code to return i + 1 and return 0 if you want. \$\endgroup\$ – ykay says Reinstate Monica Jan 23 '17 at 10:01
1
\$\begingroup\$

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));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks! What's the time complexity? \$\endgroup\$ – CMCDragonkai Jun 18 '15 at 5:17
  • \$\begingroup\$ Please include the code in the answer to make it self-contained. \$\endgroup\$ – Martin Ender Jun 18 '15 at 7:49
  • \$\begingroup\$ About time complexity I think It's O(n), as it will end immediately as soon it detects the first collision. Or will reach the end if no one collides. \$\endgroup\$ – Daniel Bonates Jun 18 '15 at 16:42
  • \$\begingroup\$ Time complexity is O(n^2) here, you got nested loops \$\endgroup\$ – Alucard Aug 30 '15 at 22:17
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You're right that mine doesn't work... I seem to have multiplied two length values together, which hardly makes sense. This version fails my test case c though. \$\endgroup\$ – feersum Jul 9 '15 at 22:45
  • \$\begingroup\$ Indeed, my solution fails on your c test case and, what worse, on another type of routes I didn't think of (that's why I didn't use i[~2] as you did). I've provided test case that shows it. \$\endgroup\$ – Serge Mosin Jul 10 '15 at 11:25
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Could you explain a little about how you used cramer's rule? \$\endgroup\$ – CMCDragonkai Aug 22 '15 at 6:05
  • 1
    \$\begingroup\$ I updated the answer with the whole approach plus the link where I took inspiration. I failed to see the point where cramer's rule is used, but the post says it was used. \$\endgroup\$ – Klaus Aug 25 '15 at 14:50
  • \$\begingroup\$ Interesting, the other algorithms are catered to this turtle situation, but don't generalise to arbitrary lines, where there could be 0 distance moves, diagonal moves, or even non-turning moves. Perhaps a bentley-ottman algorithm would be needed. \$\endgroup\$ – CMCDragonkai Sep 2 '15 at 12:59
  • \$\begingroup\$ Ah yes "polygonal chain" was the phrase I was looking for. \$\endgroup\$ – CMCDragonkai Sep 2 '15 at 13:12
1
\$\begingroup\$

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;
}
\$\endgroup\$

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