using System.Collections.Generic;
using System.Diagnostics;
namespace Critter_Crossing_2
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,
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,
1000, 1000, 1001, 1001, 1002, 1002, 1003, 1003, 1004, 1004, 1005, 1005,
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,
100000, 100000, 100001, 100001, 100002, 100002, 100003, 100003, 100004, 100004, 100005, 100005,
100006, 100006, 100007, 100007, 100008, 100008, 100009, 100009, 100010, 100010, 100011, 100011,
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("Press Enter to Continue...");
public static string TimedTest(string desc, int expected, int[] A)
var sw = new Stopwatch();
var result = (new CritterCrossing()).Solution(A);
return string.Format("{0,10}, ({2,5}={1:4}) vs ({3,5}=Expected), Ticks: {4,10}",
result == expected ? "Good" : " Bad",
private static IEnumerable<int> SequenceDoubler(int n1, int n2, double step = 0.5)
public class CritterCrossing
readonly VerticalSegments _segmentsVertical = new VerticalSegments();
readonly HorizontalSegments _segmentsHorizontal = new HorizontalSegments();
Point _currentLocation = new Point(0, 0);
public int Solution(int[] moves)
if (moves == null) return -1;
if (moves.Length < 4) return -1;
_currentSegment = new Segment(_currentLocation, Direction.North, moves[0]);
_segmentsVertical.AddLast(_currentSegment);
_currentLocation = _currentSegment.EndPoint;
_currentSegment = new Segment(_currentLocation, Direction.East, moves[1]);
_segmentsHorizontal.AddLast(_currentSegment);
_currentLocation = _currentSegment.EndPoint;
_currentSegment = new Segment(_currentLocation, Direction.South, moves[2]);
_segmentsVertical.AddLast(_currentSegment);
_currentLocation = _currentSegment.EndPoint;
for (var index = 3; index < moves.Length; index++)
var direction = (Direction)(index%4);
var distance = moves[index];
if (distance <= 0) return -1;
_currentSegment = new Segment(_currentLocation, direction, distance);
if (_currentSegment.Orientation == Orientation.Horizontal)
if (_segmentsHorizontal.CheckSegment(_currentSegment))
_segmentsVertical.AddLast(_currentSegment);
_segmentsVertical.Prune(25);
if (_segmentsVertical.CheckSegment(_currentSegment))
_segmentsHorizontal.AddLast(_currentSegment);
_segmentsHorizontal.Prune(25);
_currentLocation = _currentSegment.EndPoint;
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)
if (line1.LeftMost > line2.RightMost || line1.RightMost < line2.LeftMost)
if (line1.BottomMost > line2.TopMost || line1.TopMost < line2.BottomMost)
public void Prune(int keep = 10)
while (Count > keep) RemoveFirst();
public Segment(Point startPoint, Direction direction, int distance)
move => EndPoint.Y += move,
move => EndPoint.X += move,
move => EndPoint.Y -= move,
move => EndPoint.X -= move
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);