patterncsharpMinor

"Critter Tracking: When does it cross its own path?"

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

trackingpathcrosscritteritsowndoeswhen

Problem

Added: Version #2 of this question

Minor Update/Additonal information: This question is based on a Codility question similar to this one. 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:

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'm mainly concerned about accuracy (correct answer), speed (big O) and space. (not that I won't accept criticism of other parts).

In my SemiShort and my SemiLong tests, this takes a bit of time to run as things get bigger (SemiShort takes 3ms. SemiLong takes 18.). It's obviously because I'm creating a new Dictionary for each X, and new list entry for each Y of each X.

What options do I have to reduce the space complexity while also keeping the run time at \$O(n)\$? I have an itching feeling that Dict> isn't the m

Solution

My solution is a bit longer than the others, but seems to be fast with small number of moves, but dreadfully slow with larger numbers. I go with the philosophy that the moves yields coordinates and coordinate pairs yield segments. The question then becomes whether the current segment collides with the previously known segments (except for the very last one where its ending point is the current segment's starting point).

public class CritterTracker
{
    private const int North = 0;
    private const int East = 1;
    private const int South = 2;
    private const int West = 3;

    private const int NoCollision = -1;

    public IList CompassMoves { get; private set; }

    public CritterTracker(IList compassMoves)
    {
        this.CompassMoves = compassMoves;
    }

    public int FindFirstCrossingIndex()
    {
        if (CompassMoves == null) return NoCollision;
        if (CompassMoves.Count ();

        for (var move = 0; move  Point2.X ? Point1.X : Point2.X; } }
        public int TopMost { get { return Point1.Y > Point2.Y ? Point1.Y : Point2.Y; } }
        public int BottomMost { get { return Point1.Y  segments)
        {
            // You cannot collide with the segment immediately preceding,
            // since you already share a coordinate, i.e. your starting point
            // was the preceding ending point.
            if (IsVertical)
            {
                for (var i = 0; i  segment.RightMost) return false;
            if (TopMost  segment.TopMost) return false;
            return true;
        }

        private bool HorizontalCollision(Segment segment)
        {
            // this is a horizontal segment so this.Point1.Y == this.Point2.Y
            if (Point1.Y  segment.TopMost) return false;
            if (LeftMost > segment.RightMost) return false;
            if (RightMost < segment.LeftMost) return false;
            return true;
        }
    }
}

For readability, I also use better names IMO, e.g. CritterTracker rather than Classy. I even define constants for better readability.

Using @outoftime's test_list(), I run this in about 0.25 milliseconds in Release mode for 1M moves using @outoftime's test_list. For better comparison, using @outoftime's solve method takes me 170 milliseconds.

HOWEVER, the problem is that my code correctly finds criss-crosses and would return find an answer in the first 10 entries out of 1M. When I created a custom 1M item list without any possible collisions, it's taking minutes (as I type and still am waiting for an answer). If time allows tomorrow, I may try to optimize this to not be as embarrassingly slow.

Explanation of my code

So a critter starts at a point of (0,0) and moves in a given compass direction to land on a new point. A segment is formed by 2 consecutive points. Given the app, a segment will either be vertical or horizontal. Except for the first segment in a collection, a segment's Point1 is the same as its immediate predecessor's Point2.

I store all the moves in memory, but will only create points and segments as I am looking for any crossing or collisions. If you have 1M moves but a collision is found on move 6, processing stops.

I keep a simple List.

My class is not static. The constructor accepts an IList for the moves, which works fine with arrays. My solution method is named FindFirstCrossingIndex. While I could have kept it Solution or Solve what happens if someone asks what's that last index where a crossing occurs? The spirit of CR is to provide more meaningful names.

Comments about your code

Better naming ...

a class of Classy doesn't tell me much. It's a critter tracker, why not name it CritterTracker?

Likewise Point L. a dictionary named P, and an input array named A make the code terse and less readable. Straight-forward names are recommended: Location, Paths, and moves would be suitable replacements.

One-liners ...

many at CR think braces should always be used with one-liners, e.g.

if (!crossed) { continue; }

I personally feel omitting braces on one-liners if is acceptable, but never on a switch, for, or any loop really.

Switch ...

The switch caused me the most heartburn. I think it was tougher to read than it needs to be. Instead of:

switch (i%4) /* Rotate through directions NSEW */
{
    case 0: /* North */ crossed = Travel(1, 0, A[i]); break;
    case 1: /* East */  crossed = Travel(0, 1, A[i]); break;
    case 2: /* South */ crossed = Travel(-1, 0, A[i]); break;
    case 3: /* West */  crossed = Travel(0, -1, A[i]); break;
}

I suggest it be like:

```
switch (i % 4) / Rotate through directions NESW /
{
case 0: / North /
crossed = Travel(1, 0, A[i]);
break;
case 1: / East /
crossed = Travel(0, 1, A[i]);
break;
case 2: / South /
crossed = Travel(-1, 0, A[i]);
break;
case 3: / West /
crossed = Travel(0, -1, A[i]);

Code Snippets

public class CritterTracker
{
    private const int North = 0;
    private const int East = 1;
    private const int South = 2;
    private const int West = 3;

    private const int NoCollision = -1;

    public IList<int> CompassMoves { get; private set; }

    public CritterTracker(IList<int> compassMoves)
    {
        this.CompassMoves = compassMoves;
    }

    public int FindFirstCrossingIndex()
    {
        if (CompassMoves == null) return NoCollision;
        if (CompassMoves.Count < 4) return NoCollision;

        // This is a System.Drawing.Point
        var previousPoint = new Point(0, 0);

        var previousSegments = new List<Segment>();

        for (var move = 0; move < CompassMoves.Count; move++)
        {
            var currentPoint = MoveTo(previousPoint, move % 4, CompassMoves[move]);

            var segment = new Segment(previousPoint, currentPoint);

            if (segment.CollidesAnySegment(previousSegments))
            {
                return move;
            }

            previousSegments.Add(segment);
            previousPoint = currentPoint;
        }

        return NoCollision;
    }

    private Point MoveTo(Point previousPoint, int direction, int distance)
    {
        switch (direction)
        {
            case North:
                return new Point(previousPoint.X, previousPoint.Y + distance);
            case East:
                return new Point(previousPoint.X + distance, previousPoint.Y);
            case South:
                return new Point(previousPoint.X, previousPoint.Y - distance);
            case West:
                return new Point(previousPoint.X - distance, previousPoint.Y);
            default:
                // this will never happen but makes the compiler happy
                return new Point(0, 0);
        }
    }

    private class Segment
    {
        public Point Point1 { get; set; }
        public Point Point2 { get; set; }

        // A segment that is both horizontal and vertical is a zero length segment with Point1 == Point2.
        public bool IsHorizontal { get { return Point1.Y == Point2.Y; } }
        public bool IsVertical { get { return Point1.X == Point2.X; } }

        public int LeftMost { get { return Point1.X < Point2.X ? Point1.X : Point2.X; } }
        public int RightMost { get { return Point1.X > Point2.X ? Point1.X : Point2.X; } }
        public int TopMost { get { return Point1.Y > Point2.Y ? Point1.Y : Point2.Y; } }
        public int BottomMost { get { return Point1.Y < Point2.Y ? Point1.Y : Point2.Y; } }

        public Segment(Point point1, Point point2)
        {
            Point1 = point1;
            Point2 = point2;
        }

        public bool CollidesAnySegment(IList<Segment> segments)
        {
            // You cannot collide with the segment immediately preceding,
            // since you already share a coordinate, i.e. your starting point
            // was the preceding ending point.
            if (IsVertical)
            {

if (!crossed) { continue; }

switch (i%4) /* Rotate through directions NSEW */
{
    case 0: /* North */ crossed = Travel(1, 0, A[i]); break;
    case 1: /* East */  crossed = Travel(0, 1, A[i]); break;
    case 2: /* South */ crossed = Travel(-1, 0, A[i]); break;
    case 3: /* West */  crossed = Travel(0, -1, A[i]); break;
}

switch (i % 4) /* Rotate through directions NESW */
{
    case 0: /* North */ 
        crossed = Travel(1, 0, A[i]); 
        break;
    case 1: /* East */  
        crossed = Travel(0, 1, A[i]); 
        break;
    case 2: /* South */ 
        crossed = Travel(-1, 0, A[i]); 
        break;
    case 3: /* West */  
        crossed = Travel(0, -1, A[i]); 
        break;
}

Context

StackExchange Code Review Q#95257, answer score: 3

Revisions (0)

No revisions yet.