using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Drawing;

using System.Linq;

​

namespace Critter_Crossing_2

{

    public class Program

    {

        public static void Main(string[] args)

        {

            Console.WriteLine(TimedTest("Null",    -1, null));

            Console.WriteLine(TimedTest("Short 1", -1, new[] {1}));

            Console.WriteLine(TimedTest("Short 2", -1, new[] {1, 1}));

            Console.WriteLine(TimedTest("Short 3", -1, new[] {1, 1, 1}));

            Console.WriteLine(TimedTest("Short 4",  3, new[] {1, 1, 1, 1}));

            Console.WriteLine(TimedTest("Short 5",  3, new[] {1, 1, 1, 1, 1}));

            Console.WriteLine(TimedTest("Short 6",  6, new[] {1, 3, 2, 5, 4, 4, 6, 3, 2}));

            Console.WriteLine(TimedTest("Long 1", 41,

                new[]

                {

                    1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15,

                    16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 20, 20, 20

                }));

            Console.WriteLine(TimedTest("Long 2", 23,

                new[]

                {

                    /* 0     1     2     3     4     5     6     7     8     9    10    11    12 */

                    1000, 1000, 1001, 1001, 1002, 1002, 1003, 1003, 1004, 1004, 1005, 1005,

                    /*12    13    14    15    16    17    18    19    20    21    22    23    24 */

                    1006, 1006, 1007, 1007, 1008, 1008, 1009, 1009, 1010, 1010,    1,    1

                }));

            Console.WriteLine(TimedTest("Long 3",  3, new[] { 100000, 100000, 100000, 100000 }));

            Console.WriteLine(TimedTest("Long 4", 25,

​

                new[]

                {

                    /*   0       1       2       3       4       5       6       7       8       9      10      11   */

                    100000, 100000, 100001, 100001, 100002, 100002, 100003, 100003, 100004, 100004, 100005, 100005,

                    /*  12      13      14      15      16      17      18      19      20      21      22      23   */

                    100006, 100006, 100007, 100007, 100008, 100008, 100009, 100009, 100010, 100010, 100011, 100011, 

                    /*  24      25       2       3       4       5       6       7       8       9      10      11   */

                         1,      1,      1,      1,      1

                }));

            Console.WriteLine(TimedTest(            "1", -1, SequenceDoubler(1, 1).ToArray()));

            Console.WriteLine(TimedTest(           "10", -1, SequenceDoubler(1, 10).ToArray()));

            Console.WriteLine(TimedTest(          "100", -1, SequenceDoubler(1, 100).ToArray()));

            Console.WriteLine(TimedTest(        "1,000", -1, SequenceDoubler(1, 1000).ToArray()));

            Console.WriteLine(TimedTest(       "10,000", -1, SequenceDoubler(1, 10000).ToArray()));

            Console.WriteLine(TimedTest(      "100,000", -1, SequenceDoubler(1, 100000).ToArray()));

            Console.WriteLine(TimedTest(    "1,000,000", -1, SequenceDoubler(1, 1000000).ToArray()));

            Console.WriteLine(TimedTest(   "10,000,000", -1, SequenceDoubler(1, 10000000).ToArray()));

            //Console.WriteLine(TimedTest(  "100,000,000", -1, SequenceDoubler(1, 100000000).ToArray()));

            //Console.WriteLine(TimedTest("1,000,000,000", -1, SequenceDoubler(1, 1000000000).ToArray()));

            Console.WriteLine("Press Enter to Continue...");

            Console.ReadLine();

        }

​

        public static string TimedTest(string desc, int expected, int[] A)

        {

            var sw = new Stopwatch();

            sw.Start();

            var result = (new CritterCrossing()).Solution(A);

            sw.Stop();

​

            return string.Format("{0,10}, ({2,5}={1:4}) vs ({3,5}=Expected), Ticks: {4,10}",

                desc, //A,

                result == expected ? "Good" : " Bad",

                result,

                expected,

                sw.ElapsedTicks

                );

        }

​

        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;

            }

        }

    }

​

    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;

            TopMost   = Math.Max(StartPoint.Y, EndPoint.Y);

            BottomMost = Math.Min(StartPoint.Y, EndPoint.Y);

            RightMost = Math.Max(StartPoint.X, EndPoint.X);

            LeftMost  = Math.Min(StartPoint.X, EndPoint.X);

        }

​

        public Orientation Orientation { private set; get; }

        public int TopMost    { private set; get; }

        public int BottomMost { private set; get; }

        public int RightMost  { private set; get; }

        public int LeftMost   { private set; get; }

​

        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

    }

}