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 -1I 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 ofI'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 minimumFull Code (Including basic testing): https://dotnetfiddle.net/8ByC2bNote: 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    }}
Critter Tracking: When does it cross its own path? Part 2
c#;algorithm;coordinate system