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
}
}
Segment
class you could haveTopMost
et al be{ get; private set; }
and just set them once in the constructor. \$\endgroup\$