“Critter Tracking: When does it cross its own path?” Part 2

Question

Basic Info: This question is my second attempt at this question. It is based on a question similar to this Codility question. The input (an int array), the outpout (an integer) and the method signature (public int solution(int[] A)) are given.

Situation:

A critter starts at (0, 0) on a Cartesian graph. We have a non-empty zero-indexed "moves" list that contains numbers. Each number represents the distance moved. (Similar to this question) 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 critter cross a point that it has already visited before. The move number is the index of the "moves" list.

Example:

If given this move list: [1, 3, 2, 5, 4, 4, 6, 3, 2]
The 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 the 6th index (move number 7th) it will meet (2,1) which is a point that the turtle has already crossed.

Notes:

n = moves
m = avg steps per move
Algorithm should preferably be O(n).
algorithm space Complexity should be __?
n (Number of moves) is an integer between 1 and 100,000
m (distance per move) is a positive integers between 1 and 1,000
"No collision" should return -1

I initially had a Dictionary<Int,List<Int>> to track the path a critter traveled for detecting when he crossed he trail. That answer was O(n) in complexity but O(crap) in space usage when the lines got long - a walk of 1k steps could add as many lists - then as many points on the next step.

Thanks to this answer I was given then idea of tracking line segments - and then comparing the newest line segment with previous for cross overs. (I've also worked on some of the naming and layout inconsistencies)

It seems the trade-off is Space Complexity (Attempt #1) for Computational complexity (Attempt #2. this attempt). Computationally, the #1 should be O(n), since it's doing a single pass and tracking all the path points - eating up memory. #2 is more computational, since you are doing a full pass of moves and then comparing each move to previous segments: O(n^2) but it's more likely to use less space since it's using O(n) space and not O(n*avg(m)) space.

But looking it over, I've come to a couple conclusions:

• I don't think a line can cross anything further than a hand full of lines back. It always has to go in a "clockwise circle" and can't cross itself but once. If I haven't crossed a segment in 4? moves... I won't cross that segment and can forget about it. (point out if I'm wrong on this... Its more a feeling than something I can prove)

  x is number of segments in each list I'm keeping track of

• I've switched my List to a LinkedList since my goal is to now Add to list, remove if list is longer than x.
• Since I'm keeping track of x*2 segments (Horz/Vert) instead of n segments, this should keep the space complexity to a minimum

Full Code (Including basic testing): https://dotnetfiddle.net/8ByC2b

Note: Fiddle complains about space at 100k moves. My computer doesn't error until 100m moves or more. I'll figure that error out at somepoint, but those numbers are outside of "scope" but I wanted to "test" them to see if/when I ran out of memory with a List/LinkedList/Queue/etc. The "specs" say 100k moves, which this handles easily even though fiddle complains about it.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;

namespace Critter_Crossing_2
{
    public class CritterCrossing
    {
        readonly VerticalSegments _segmentsVertical = new VerticalSegments();
        readonly HorizontalSegments _segmentsHorizontal = new HorizontalSegments();
        Point _currentLocation = new Point(0, 0);
        Segment _currentSegment;

        public int Solution(int[] moves)
        {
            if (moves == null) return -1; /* Invalid Inputs */
            if (moves.Length < 4) return -1; /* Can't cross in less than 4 moves */

            /* First Move */
            _currentSegment = new Segment(_currentLocation, Direction.North, moves[0]);
            _segmentsVertical.AddLast(_currentSegment);
            _currentLocation = _currentSegment.EndPoint;

            /* Second Move */
            _currentSegment = new Segment(_currentLocation, Direction.East, moves[1]);
            _segmentsHorizontal.AddLast(_currentSegment);
            _currentLocation = _currentSegment.EndPoint;

            /* Third Move */
            _currentSegment = new Segment(_currentLocation, Direction.South, moves[2]);
            _segmentsVertical.AddLast(_currentSegment);
            _currentLocation = _currentSegment.EndPoint;

            /* Fourth and beyond */
            for (var index = 3; index < moves.Length; index++)
            {
                var direction = (Direction)(index%4); /* Mod to Directionality */
                var distance = moves[index];
                if (distance <= 0) return -1; /* illegal move */

                _currentSegment = new Segment(_currentLocation, direction, distance);

                /* Check Orientation.
                 * Compare Segments for overlap
                 *    return index if crossover found
                 *    Add to LinkedList if no crossover found
                 *    "Prune" list to keep memory manageable
                 */
                if (_currentSegment.Orientation == Orientation.Horizontal)
                {
                    if (_segmentsHorizontal.CheckSegment(_currentSegment))
                        return index;
                    _segmentsVertical.AddLast(_currentSegment);
                    _segmentsVertical.Prune(25);
                }
                else
                {
                    if (_segmentsVertical.CheckSegment(_currentSegment))
                        return index;
                    _segmentsHorizontal.AddLast(_currentSegment);
                    _segmentsHorizontal.Prune(25);
                }

                _currentLocation = _currentSegment.EndPoint;
            }

            return -1;
        }
    }

    public class HorizontalSegments : Segments { }

    public class VerticalSegments : Segments { }

    public class Segments : LinkedList<Segment>
    {
        public bool CheckSegment(Segment line1)
        {
            if (Count < 2) return false;

            for (var index = First; index != null && index.Next != null; index = index.Next)
            {
                var line2 = index.Value;

                if (line1.LeftMost > line2.RightMost || line1.RightMost < line2.LeftMost)
                    continue; /* X's don't overlap */
                if (line1.BottomMost > line2.TopMost || line1.TopMost < line2.BottomMost)
                    continue; /* Y's don't overlap */
                return true;
            }
            return false;
        }

        public void Prune(int keep = 10)
        {
            while (Count > keep) RemoveFirst();
        }
    }

    public class Segment
    {
        public Point EndPoint;
        public Point StartPoint;

        public Segment(Point startPoint, Direction direction, int distance)
        {
            StartPoint = startPoint;
            EndPoint = startPoint;

            Action<int>[] moves =
            {
                move => EndPoint.Y += move, /* North */
                move => EndPoint.X += move, /* East  */
                move => EndPoint.Y -= move, /* South */
                move => EndPoint.X -= move /* West  */
            };

            moves[(int) direction].Invoke(distance);
            if (direction == Direction.North || direction == Direction.South) Orientation = Orientation.Horizontal;
            else Orientation = Orientation.Vertical;
        }

        public Orientation Orientation { private set; get; }
        public int TopMost    { get { return Math.Max(StartPoint.Y, EndPoint.Y); } }
        public int BottomMost { get { return Math.Min(StartPoint.Y, EndPoint.Y); } }
        public int RightMost  { get { return Math.Max(StartPoint.X, EndPoint.X); } }
        public int LeftMost   { get { return Math.Min(StartPoint.X, EndPoint.X); } }

        public override string ToString()
        {
            return string.Format("Start: ({0},{1}), End: ({2},{3})", StartPoint.X, StartPoint.Y, EndPoint.X, EndPoint.Y);
        }
    }

    public enum Direction
    {
        North = 0,
        East = 1,
        South = 2,
        West = 3
    }

    public enum Orientation
    {
        Horizontal,
        Vertical
    }
}

Answer 1

Your SequenceDoubler method posted at https://dotnetfiddle.net/8ByC2b could be improved. Here's the original version:

private static IEnumerable<int> SequenceDoubler(int n1, int n2, double step = 0.5)
{
    double d1 = n1;
    double d2 = n2;

    while (d1 <= d2)
    {
        d1 += step;
        yield return (int) d1;
    }
}

The parameter and local variable names aren't very readable, it uses doubles when it doesn't have to, and step isn't very intuitive. What if, for some reason, you wanted to triple the sequence? Here is an improved version using LINQ:

private static IEnumerable<int> SequenceDoubler(int start, int finish, int repeatAmount = 2)
{
    int count = finish - start + 1;
    return
        from x in Enumerable.Range(start, count)
        from _ in Enumerable.Repeat(0, repeatAmount)
        select x;
}

If you prefer to use loops, you can use this version:

private static IEnumerable<int> SequenceDoubler(int start, int finish, int repeatAmount = 2)
{
    for (int i = start; i <= finish; i++)
    {
        for (int j = 0; j < repeatAmount; j++)
        {
            yield return i;
        }
    }
}

Answer 2

UPDATE: this is 1 of 3 answers I have provided. It is more of a really big comment along with code. Look for my full, very long, more complete answer.

I think your code is good enough as-is and its been a nice discussion. I offer this as "food for thought", not as a specific fix to anything.

When I was playing around yesterday trying to improve my sluggish performance, I kept the path segment philosophy but totally redefined what a segment is. So a segment could be from a starting point to an ending point. Or it could be starting point with a distance and a direction.

Since the orientation will either be vertical or horizontal, there's another way to consider a segment: something with an orientation (vertical or horizontal), a constant (vertical has constant X, horizontal constant Y), and a Min/Max value (vertical has Min/Max Y, horizontal Min/Max X).

This kind of cleans up or simplifies the code.

private class Segment
{
    // Segments will never be diagonal.  It will always either be vertical or horizontal.
    public Orientation  Orientation { get; private set; }
    public int Constant { get; private set; }
    public int Min { get; private set; }
    public int Max { get; private set; }

    private Segment() { }

    public static Segment Empty { get { return new Segment(); } }

    public static Segment CreateFromPoints(Point startPoint, Direction direction, int distance)
    {
        var instance = new Segment();

        var endPoint = startPoint;

        Action<int>[] moves =
        {
            move => endPoint.Y += move, /* North */
            move => endPoint.X += move, /* East  */
            move => endPoint.Y -= move, /* South */
            move => endPoint.X -= move /* West  */
        };

        moves[(int)direction].Invoke(distance);

        if ((direction == Direction.North) || (direction == Direction.South))
        {
            instance.Orientation = Orientation.Vertical;
            instance.Constant = startPoint.X;
            instance.Min = Math.Min(startPoint.Y, endPoint.Y);
            instance.Max = Math.Max(startPoint.Y, endPoint.Y);
        }
        else
        {
            instance.Orientation = Orientation.Horizontal;
            instance.Constant = startPoint.Y;
            instance.Min = Math.Min(startPoint.X, endPoint.X);
            instance.Max = Math.Max(startPoint.X, endPoint.X);
        }

        return instance;
    }

    public bool Collides(Segment segment)
    {
        if (Orientation == segment.Orientation) return CollidesSameOrientation(segment);
        return CollidesDifferentOrientation(segment);
    }

    private bool CollidesSameOrientation(Segment segment)
    {
        if (Constant != segment.Constant) return false;
        if (Min > segment.Max) return false;
        if (Max < segment.Min) return false;
        return true;
    }

    private bool CollidesDifferentOrientation(Segment segment)
    {
        if ((Min > segment.Constant) || (Max < segment.Constant)) return false;
        return  (Constant >= segment.Min) && (Constant <= segment.Max);
    }
}

Answer 3

If (and only if) every move is guaranteed to be of non-negative and nonzero distance, you only need to track 6 moves, and you only need to compare a move against the move 3 moves ago or 5 moves ago.

This move cannot cross any move an even number of moves ago; they are parallel. It cannot cross the previous move; they touch at one corner and are perpendicular -- they cannot meet twice. And any move more than 5 moves ago will be "shielded" by one of the more recent moves.

Answer 4

UPDATE: this is 1 of 3 answers I have provided. It is more of a really big comment along with code. Look for my full, very long, more complete answer.

Since I am the one who came up with tracking of path segments, I must warn it that it scales HORRIBLY. I tried optimizing my code to use dictionaries but became too slow. That's the crux of the issue for huge number of moves: either you run out of memory for fast access, or you take too long for performing searches.

For anyone wanting to test their answers, keep in mind that this input:

new[] { 1, 3, 2, 5, 4, 4, 6, 3, 2 }

Should return: 6 as the correct answer.

Also if you want to test an arbitrarily long spiral that will never have any crossings, you may use:

public static int[] SpiralWithoutCrossing(int size)
{
    var result = new int[size];
    for (var i = 0; i < size; i++)
    {
        result[i] = i + 1;
    }
    return result;
}

As I mentioned, I wrote a lot of code to try to optimize my solution. I could post it here out of general interest but should warn it is quite slow with a large number of moves. General timings for spirals of varying sizes:

• 100 moves took 0.7 milliseconds
• 1,000 moves took 23 milliseconds
• 10,000 moves took 1.9 seconds
• 100,000 moves took 223 seconds
• 1,000,000 moves projected to take over 12 hours!

Questions like this are interesting for honing one's skills but I think there should be a practical limit. I think of games I've played on slower devices and why they can be so fast. That's because they are bounded by the limits of the display. So on a practical level, they are quite fast for the small number of pixels or cells to track. In that case, your version 1 would be most suitable.

Answer 5

My previous 2 answers may be thought of as extended comments with accompanying code snippets. I now offer a more comprehensive answer that addresses your specific code and the problem at hand.

SegmentPool Replaces HorizontalSegments and VerticalSegments

I see no reason to have 2 segment groups partitioned by orientation. Likewise, being a LinkedList is overkill as items are frequently added or removed. My analysis reveals that you need to only keep track of at most 6 segments: the latest one defined by the very last move, and up to 5 previous moves.

This is a tiny list and works well as a ‘circular’ pool. That is to say it could be an array of Segment, i.e. Segment[]. I keep incrementing the index of the last segment added to the pool. If the index reaches the end of the array, I will cycle back around to 0. I now eliminate any overhead of inserting or removing items from a list. Older segments merely become overwritten.

Note the SegmentPool is not just a simple array with a last index property. I will put several important duties in the SegmentPool class such as the collision logic. And its memory footprint will be fairly minimal (more below).

Reduce and Simplify the Problem Space

After analyzing the problem, one can reduce the solution by checking the segment formed by the latest move against only 2 other segments: one occurring 3 moves prior, and another occurring 5 moves prior. Note I will call these -3 and -5 away moves. And by nature of the way a critter moves, the -3 and -5 moves are perpendicular to the current move’s orientation.

Well, that’s true in general but there are exceptions to every rule, or as we sometimes call it, corner cases. The above rule applies to moves 6 and greater. But the first 5 moves are all special cases:

• Moves 1-3 cannot cross anything. They lack both a -3 and -5 away move.
• Move 4 has only one possible crossing at segment 1, which is -3 away. That is to say, it doesn’t have a -5 away move.
• Move 5 could possibly cross segment 1, which has the same orientation but more importantly is -4 away. The pattern is broken (but it can be fixed).

One way to account for these corner cases is putting several conditionals and checks in place. This makes the logic chopped up.

Wouldn’t the problem space be simpler if each and every move always has a -3 and -5 away move? It’s not an impossible dream if we have the SegmentPool load appropriately configured zero length dummy segments (more later).

I will do just that: load zero length dummy segments when the SegmentPool is created, and this will guarantee that each and every real move will always have a -3 and -5 away move. The collision checking section will be more streamlined by doing it this way.

Plus, for each move you will only check 2 segments AT MOST. This scales extremely well.

First 3 moves logic bug

Your code for the first 3 moves is missing a critical check. You do not check that the distance for a respective move is greater than 0.

Optional General Considerations

These next items are purely optional and are general in nature. The better CR answers not only address the heart of the problem you are trying to solve but also bring up other issues that can make you a better, well-rounded developer.

Class-level variables

My solution will not need any class level properties or fields. I see no need for a _currentLocation or _currentSegment. In fact, CritterCrossing can be a static class and Solution can be a static method.

Given the special nature of Segment and SegmentPool, I likewise choose for them to be private and nested classes inside of CritterCrossing. The only things that I have exposed as public are those minimal things that truly need to be public. Even the constructor to Segment or SegmentPool are private; instead I require you to use the Create method for them, where Create is both public and static.

This reduces the ‘surface area’ of my classes to the bare minimum.

Named constant for output of -1

I also like assigning the index not found (-1) as a named constant: noCrossingIndex. Sure -1 works but what happens if someone changes the requirement to be some other negative number, e.g. -9? Do you change your code in 4 places or just 1? Plus the code reads cleaner with return noCrossingIndex; since its intent is clearly apparent.

Flexible method signature

Others have suggested it before that you could make the signature to be IList<int> moves. If it’s not apparent to you, this signature will accept an int[] as input. Sure you can say that the original problem required the signature be int[] but you’ve already reworded the original problem to make it your own. So you have the liberty to reword the signature requirement.

To throw or not to throw

The last general consideration is whether or not to throw an exception on bad inputs. Understand that I get it: you have an interesting math problem in front of you and you care most about the logic to solve that problem, and not so much in the finer implementation details of dealing with bad inputs. That’s just ‘finishing’ work after the main task at hand. Some could argue that you code works fine in this regard.

To complete the topic, however, I think one should throw on invalid data, and not simply return -1. To me invalid data is when the array (or IList) is null, or when any move is <= 0. Having less than 4 moves isn’t invalid since I can imagine it is valid to consider that a critter may travel less than 4 spaces, as long as each move is > 0.

That concludes the sidetrack. Back to the meat of the problem.

First 3 moves – staying DRY

Replacing the 2 lists with a single SegmentPool, I could load the first 3 moves this way:

for (var i = 0; i < 4; i++)
{
    // The first 3 moves must also check valid distance
    var distance = moves[i];
    if (distance <= 0)
    {
        throw new ArgumentException(string.Format("Invalid distance {0} at index {1}", distance, i));
    }

    var segment = Segment.Create(startPoint, (Direction)(i % 4), distance);
    pool.AddSegment(segment);

    // DO NOT CHECK FOR COLLISION

    startPoint = segment.EndPoint;
}

It’s more DRY, that is adheres to principle of Don’t Repeat Yourself, than code to load each segment, which you had to do to flip between vertical and horizontal lists. It fixes the missing check for distance. But if you examine the next section, it doesn’t seem DRY after all.

for (var i = 4; i < moves.Count; i++)
{
    var distance = moves[i];
    if (distance <= 0)
    {
        throw new ArgumentException(string.Format("Invalid distance {0} at index {1}", distance, i));
    }

    var segment = Segment.Create(startPoint, (Direction)(i % 4), distance);
    pool.AddSegment(segment);
    // The first 3 moves cannot collide but I leave it up to the SegmentPool to worry about that.
    if (pool.HasCollision) return i;

    startPoint = segment.EndPoint;
}

Both loops look almost the same with the exception of whether or not a collision check is performed near the bottom. I could have one loop that has an internal check:

// The first 3 moves cannot collide 
if (i > 3)
{
    if (pool.HasCollision) return i;
}

But if I have a million moves, I just performed 999997 checks that I really shouldn’t have had.

I mentioned earlier that I would let the SegmentPool worry about the collision checks and it will take care of the first 3 moves, as well as corner case of moves 4 and 5. Therefore, my resulting class becomes:

public static class CritterCrossing
{
    public static int Solution(IList<int> moves)
    {
        const int noCrossingIndex = -1;

        if (moves == null)
        {
            throw new ArgumentNullException("moves");
        }

        if (moves.Count < 4) return noCrossingIndex;  // Can't cross in less than 4 moves

        var startPoint = new Point(0, 0);
        var pool = SegmentPool.Create();

        for (var i = 0; i < moves.Count; i++)
        {
            var distance = moves[i];
            if (distance <= 0)
            {
                throw new ArgumentException(string.Format("Invalid distance {0} at index {1}", distance, i));
            }

            var segment = Segment.Create(startPoint, (Direction)(i % 4), distance);
            pool.AddSegment(segment);
            // The first 3 moves cannot collide but I leave it up to the SegmentPool to worry about that.
            if (pool.HasCollision) return i;

            startPoint = segment.EndPoint;
        }

        return noCrossingIndex;
    }

    // NESTED: private class Segment

    // NESTED: private class SegmentPool
}

You will note the class and method are both public static. There are not class level properties or fields. The method contains instances for a startPoint and pool.

All moves are handled in one loop, and there is no special check based on move number.

Private Nested Segment Class

A segment can be characterized as StartPoint and an EndPoint. Or it could be a Direction, Constant, Min, and Max. Whichever you go with can derive or calculate other properties. I personally like Direction, Constant, Min, and Max. Yet below I set everything during Create and don’t worry about read only getters.

This is a tiny bit of bloat on an instance, but since I have at most 6 instances, this bloat is okay by me. If I have a million moves, I don’t have to perform 1 or 2 million getter calculations.

private class Segment
{
    // If I only stored StartPoint and EndPoint, I could calculate: Direction, Orientation, Constant, Min, and Max.
    // If I only stored Direction, Constant, Min, and Max, I could calculate: Orientation, StartPoint, and EndPoint.
    // Yet I store all of them here.  
    // If I were to have a million segments, this would be very wasteful bloat.
    // But since I will only have AT MOST 6 segments, I find the waste minimal and acceptable.

    public Direction Direction { get; private set; }
    public Orientation Orientation { get; private set; }
    public int Constant { get; private set; }
    public int Min { get; private set; }
    public int Max { get; private set; }

    public Point StartPoint { get; private set; }
    public Point EndPoint { get; private set; }

    private Segment() { }

    public static Segment Create(Point startPoint, Direction direction, int distance)
    {
        var instance = new Segment();

        instance.Direction = direction;

        instance.Orientation = (direction == Direction.North) || (direction == Direction.South)
                                ? Orientation.Vertical
                                : Orientation.Horizontal;

        var endPoint = startPoint;

        Action<int>[] moves =
        {
            move => endPoint.Y += move, /* North */
            move => endPoint.X += move, /* East  */
            move => endPoint.Y -= move, /* South */
            move => endPoint.X -= move  /* West  */
        };

        moves[(int)direction].Invoke(distance);

        if (instance.Orientation == Orientation.Vertical)
        {
            instance.Constant = startPoint.X;
            instance.Min = Math.Min(startPoint.Y, endPoint.Y);
            instance.Max = Math.Max(startPoint.Y, endPoint.Y);
        }
        else
        {
            instance.Constant = startPoint.Y;
            instance.Min = Math.Min(startPoint.X, endPoint.X);
            instance.Max = Math.Max(startPoint.X, endPoint.X);
        }

        instance.StartPoint = startPoint;
        instance.EndPoint = endPoint;

        return instance;
    }

    public override string ToString()
    {
        return string.Format("Start: ({0},{1}), End: ({2},{3}), {4}", StartPoint.X, StartPoint.Y, EndPoint.X, EndPoint.Y, Direction);
    }
}

The Segment class has no concern about collision logic. It leaves that to the SegmentPool. I did try a test relying more on getter calculations: it took 30 milliseconds longer for a million move spiral. I leave it to the reader to decide whether a small amount of memory is worth saving 30 ms.

Private Nested SegmentPool Class

The big lead up finally gets addressed! The collision logic – not just limited to comparing segments for a collision but deciding on the critical -3 and -5 away segments – is all done here.

Most methods and properties in the class are fairly short and straightforward, with one notable exception: the LoadDummySegments method. Some could suggest ways to make that method a tiny bit more DRY but I configure the individual dummy segments one at a time with appropriate comments.

private class SegmentPool
{
    // The SegmentsPool will be a 'circular' pool, which is a small array of Segment.
    // I won't bother removing, adding, or shifting array elements.
    // Instead I keep track of the index of the most recently pooled segment,
    // and this index will rotate from the end back to the beginning of the array.

    private Segment[] _pool = null;
    private int _latestIndex = -1;

    private SegmentPool() { }

    public static SegmentPool Create()
    {
        const int maxSize = 6;
        var instance = new SegmentPool();
        instance._pool = new Segment[maxSize];
        instance.LoadDummySegments();
        return instance;
    }

    private void LoadDummySegments()
    {
        // Initially _pool's elements are null.
        // Later we check back -3 and -5 segments to determine collisions,
        // so we will load 5 zero length segments with appropriate configuration
        // to keep the Collides logic correct.

        var impossible1and3 = new Point(int.MinValue, int.MinValue);
        var impossible2and4 = new Point(int.MinValue, int.MaxValue);

        // The first 4 dummy indices 0..3 are totally bogus and should always return false for HasCollision.

        // dummy 0 will be -5 from move #1 (Vertical)
        _pool[0] = Segment.Create(impossible1and3, Direction.West, 0);

        // dummy 1 will be -5 from move #2 (Horizontal)
        _pool[1] = Segment.Create(impossible2and4, Direction.North, 0);

        // dummy 2 will be -3 from move #1 and -5 from move #3 (Vertical)
        _pool[2] = Segment.Create(impossible1and3, Direction.East, 0);

        // index 3 will be -3 from move #2 and -5 from move #4 (Horizontal)
        _pool[3] = Segment.Create(impossible2and4, Direction.South, 0);

        // index 4 will be -3 from move #3 and -5 from move #5. 
        // CORNER CASE: moves = new int[] {1, 1, 2, 1, 2}
        // Move #5 could cross #1 at the origin BUT #1 and #5 are both vertical,
        // and more importantly, move #1 is -4 moves from #5, not the expected -3 or -5.
        // So this dummy segment is quite important since it could possibly collide with move #5.
        // Note than that move #5 would not be colliding with #1 but rather with this
        // dummy segment which shares #1's StartPoint.  But that's okay.  
        // It's one of the reasons why we load the dummies in the first place.
        // The other reason is to not have null segments for -3 and -5 checks.
        _pool[4] = Segment.Create(new Point(0, 0), Direction.West, 0);

        // That's the end of the initial dummy segments.
        // The logic in Collides is preserved for all future generations as these
        // dummy segments will later be discarded for newer real segments.
        //    move #1 becomes check -3 for move #4, and check -5 for move #6.
        //    move #2 becomes check -3 for move #5, and check -5 for move #7. 
        //    And so on.
        _latestIndex = 4;
    }

    public void AddSegment(Segment segment)
    {
        if (segment == null) return;
        _latestIndex++;
        if (_latestIndex == _pool.Length) _latestIndex = 0;
        _pool[_latestIndex] = segment;
    }

    public Segment Latest { get { return _pool[_latestIndex]; } }

    public bool HasCollision
    {
        get
        {
            foreach (var candidate in Candidates)
            {
                if (Collides(Latest, candidate)) return true;
            }
            return false;
        }
    }

    private IEnumerable<Segment> Candidates
    {
        get
        {
            // There are only 2 possible candidates: -3 and -5 from _latestIndex.
            // We may have to cycle around to end to be within range.
            var index = _latestIndex - 1;
            for (var i = 0; i < 2; i++)
            {
                index -= 2;
                if (index < 0) index += _pool.Length;
                yield return _pool[index];
            }
        }
    }

    private bool Collides(Segment segment1, Segment segment2)
    {
        // I don't worry about orientation here.
        // The Candidates produced by the SegmentPool should yield segments that are perpindicular
        // to the latest segment.
        if ((segment1.Min > segment2.Constant) || (segment1.Max < segment2.Constant)) return false;
        return (segment1.Constant >= segment2.Min) && (segment1.Constant <= segment2.Max);
    }
}

I could elaborate more on the dummy segments but it would only be echoing the comments in code.

Suffice to say that the initial loading of these specific zero length segments guarantees me that each and every real move will be checked with a -3 and -5 away move that is perpendicular to the latest segment. This is true starting with move 1 at moves[0]. Doing this converts the corner cases into normal cases.

Performance

Using a spiral containing 1 million moves without crossings takes less than 250 milliseconds on my laptop (actually closer to 240 ms). A million moves requires at most 2 million checks for a possible collision. Ten million moves would require no more than 20 million checks.

Thus, the problem space has been reduced and simplified. It requires very small amount of memory and it scales linearly.