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

Question

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<int, List<int>> isn't the most effective way to build this, but I can't place my finger on what else I could use.

I've considered trying to do a bit-manipulation via something like some "magic" code that uses Bit Vector to achieve "greatness" - but I think it would ruin readability (especially once you have to start working with more than 32 "bits").

So I have something I feel is readable and accurate... but slow with bigger numbers/longer runs - that I could make more efficient at the cost of readability and complexity.

If the moves per direction was increased from 1k to 100k - it would blow the space used out of orbit and times would skyrocket accordingly.

using System;
using System.Collections.Generic;
using System.Drawing;
using Xunit;

namespace Critter_Crossing
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            Console.WriteLine((new Classy()).Solution(new[] {1, 1, 1, 1}));
            Console.WriteLine((new Classy()).Solution(new[] {1, 3, 2, 5, 4, 4, 6, 3, 2}));
            Console.WriteLine((new Classy()).Solution(new[]
                        {
                            1000, 1000, 1001, 1001, 1002, 1002, 1003, 1003, 1004, 1004, 1005, 1005, 1006,
                            1006, 1007, 1007, 1008, 1008, 1009, 1009, 1010, 1010, 1010, 1010
                        }));
            //Console.WriteLine((new Classy()).Solution(new[] { 100000, 100000, 100000, 100000 }));
            //Console.WriteLine((new Classy()).Solution(new[]
            //            {
            //                100000, 100000, 100001, 100001, 100002, 100002, 100003, 100003, 100004, 100004, 100005, 100005, 100006,
            //                100006, 100007, 100007, 100008, 100008, 100009, 100009, 100010, 100010, 1
            //            }));
            Console.ReadLine();
        }
    }

    public class Testy
    {
        [Fact] public void Test_Null() { Assert.Equal(-1, (new Classy()).Solution(null)); }
        [Fact] public void Test_0() { Assert.Equal(-1, (new Classy()).Solution(new int[0])); }
        [Fact] public void Test_1() { Assert.Equal(-1, (new Classy()).Solution(new []{1})); }
        [Fact] public void Test_2() { Assert.Equal(-1, (new Classy()).Solution(new []{1,1})); }
        [Fact] public void Test_3() { Assert.Equal(-1, (new Classy()).Solution(new []{1,1,1})); }
        [Fact] public void Test_4() { Assert.Equal( 3, (new Classy()).Solution(new []{1,1,1,1})); }
        [Fact] public void Test_TestExample() { Assert.Equal(6, (new Classy()).Solution(new []{1, 3, 2, 5, 4, 4, 6, 3, 2})); }
        [Fact] public void Test_LongExample() { Assert.Equal(41, (new Classy()).Solution(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,1})); }
        [Fact] public void Test_SemiShort() { Assert.Equal(3, (new Classy()).Solution(new[] {1000, 1000, 1000, 1000})); }
        [Fact] public void Test_SemiLong() { Assert.Equal(23, (new Classy()).Solution(new[]
                {
                    1000, 1000, 1001, 1001, 1002, 1002, 1003, 1003, 1004, 1004, 1005, 1005, 
                    1006, 1006, 1007, 1007, 1008, 1008, 1009, 1009, 1010, 1010, 1010, 1010
                })); }
        [Fact(Skip="Runs Long")] public void Test_ShortLong() { Assert.Equal(3, (new Classy()).Solution(new[] {100000, 100000, 100000, 100000})); }
        [Fact(Skip="Runs Long")] public void Test_LongLong() { Assert.Equal(22, (new Classy()).Solution(new[]
                {
                    100000, 100000, 100001, 100001, 100002, 100002, 100003, 100003, 100004, 100004, 100005, 100005, 100006,
                    100006, 100007, 100007, 100008, 100008, 100009, 100009, 100010, 100010, 1
                }));}
    }

    public class Classy
    {
        public static Point L; /* Tracks current location on cortesian plane */
        public static Dictionary<int, List<int>> P; /* Tracks path taken for collision detection */

        public int Solution(int[] A)
        {
            if (A == null) return -1; /* Invalid Input */
            if (A.Length < 4) return -1; /* Can't cross itself without going at least 4 steps */

            P = new Dictionary<int, List<int>>();
            L = new Point(0, 0);

            var crossed = false;
            var result = -1;

            P[0] = new List<int>();
            P[0].Add(0);
            for (var i = 0; i < A.Length; i++)
            {
                if (A[i] <= 0) return -1; /* Bad input */
                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;
                }
                if (!crossed) continue;

                /* Found a crossing point, get result and break */
                result = i;
                break;
            }

            return result;
        }

        private bool Travel(int x, int y, int distance)
        {
            /* move one space, check location and...
             * ... return if already ticked
             * ... add otherwise 
             */
            int X; /* used for brevity */
            int Y; /* used for brevity */
            for (var j = 1; j <= distance; j++)
            {
                X = L.X += x*1;
                Y = L.Y += y*1;

                if (!P.ContainsKey(L.X))
                {
                    /* First time on this X plane */
                    P[X] = new List<int>();
                    P[X].Add(Y);
                }
                else if (!P[X].Contains(Y))
                {
                    /* First time seeing this Y coordinate on an existing X plane */
                    P[X].Add(Y);
                }
                else
                {
                    /* Existing Y on an existing X */
                    return true;
                }
            }

            return false;
        }
    }
}

Answer 1

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<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)
            {
                for (var i = 0; i < segments.Count - 1; i++)
                {
                    if (VerticalCollision(segments[i])) return true;
                }
            }
            else if (IsHorizontal)
            {
                for (var i = 0; i < segments.Count - 1; i++)
                {
                    if (HorizontalCollision(segments[i])) return true;
                }
            }

            // should never fall throught to here
            return false;
        }

        private bool VerticalCollision(Segment segment)
        {
            // this is a vertical segment so this.Point1.X == this.Point2.X
            if (Point1.X < segment.LeftMost) return false;
            if (Point1.X > segment.RightMost) return false;
            if (TopMost < segment.BottomMost) return false;
            if (BottomMost > 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.BottomMost) return false;
            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<Segment>.

My class is not static. The constructor accepts an IList<int> 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]); 
        break;
}

For several reasons. Note I added spacing around i%4 - it's okay to let it breathe. I ditched the jumbled one-liners. And I even corrected the comment to be NESW instead of NSEW.

Or you could use named constants (as I did) named North, East, South, and West to make it more understandable.

Answer 2

I have a number of thoughts, but I'll start with one - the parameter to the Solution() method would be better off as a constructor parameter and the tests for its fitness would be better served as exceptional conditions. Here's a short snippet (note I also replaced the array with the most generic interface needed for the operation - IList<T>. .Length becomes .Count and you'll need to adjust your calling code and unit tests to accommodate, but that's pretty simple. The modified code:

public class Classy
{
    private readonly IList<int> _A;

    public Classy(IList<int> a)
    {
        if (a == null)
        {
            throw new ArgumentNullException("a", "Invalid Input");
        }

        if (a.Count < 4)
        {
            throw new ArgumentOutOfRangeException("a.Count", a.Count, "Can't cross itself without going at least 4 steps");
        }

        this._A = a;
    }

    public int Solution()
    {
        // ...
    }

    // ...
}

Answer 3

After experiments with Dictionary and Hashtable, I found that dictionary fit best of all.

• Dictionary<Tuple<int,int>, int> ~800ms
• Hashtable ~1200ms (I think it is because of convertation primitive to object before inserting)
• Dictionary<int,int> ~350ms

All data for array length 1M.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Solution 
{
    private static int NumberOfElements = 1000 * 1000;
    private static int MaxMove = 1000;

    private static int CreateKey(int x, int y) {
        return 100 * 1000 * x + y;
    }

    // private static Tuple<int,int> CreateKey(int x, int y) {
    //     return Tuple.Create(x, y);
    // }

    private static IEnumerable<int> test_list() {
        Random rand = new Random();
        for (int i = 0; i < Solution.NumberOfElements; ++i) {
            yield return rand.Next(Solution.MaxMove);
        }
    }

    private static int solve(IEnumerable<int> list) {
        int x = 0, y = 0;
        //var steps = new Dictionary<Tuple<int, int>, int>();
        //var steps = new Hashtable();
        var steps = new Dictionary<int, int>();
        var moves = new Action<int>[] {
            move => x += move,
            move => y += move, 
            move => x -= move,
            move => y -= move
        };

        int count = 0;
        foreach (int elem in list) {
            var step = Solution.CreateKey(x, y);
            if (!steps.ContainsKey(step)) {
                steps.Add(step, count);
            }
            count++;
            moves[count % 4](elem);
        }

        var lastStep = Solution.CreateKey(x, y);
        return steps.ContainsKey(lastStep) ? (int)steps[lastStep] : -1;
    }

    public static void Main(String[] args) {
        int[] list = Solution.test_list().ToArray();

        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();
        System.Console.WriteLine(Solution.solve(list));
        stopWatch.Stop();
        System.Console.WriteLine(stopWatch.ElapsedMilliseconds);
    }
}

Answer 4

I think that algorithm-wise, since we always know which segments are horizontal and vertical, it would be more efficient to separate them. My initial approach would be something like:

public class PathSolver
{
    private struct Range
    {
        private int _min;
        private int _max;

        public Range(int min, int max)
        {
            _min = min;
            _max = max;
        }

        public bool Overlaps(int n)
        {
            return n >= _min && n <= _max;
        }

        public bool Overlaps(Range other)
        {
            return !(_max < other._min || _min > other._max);
        }

        public Range Combine(Range other)
        {
            return new Range(Math.Min(_min, other._min), Math.Max(_max, other._max));
        }
    }

    private class Plane
    {
        private List<Range> _ranges = new List<Range>();

        public bool Intersects(int n)
        {
            return _ranges.Any(x => x.Overlaps(n));
        }

        public void AddRange(Range range)
        {
            var existing = _ranges.FindIndex(x => x.Overlaps(range));
            if (existing >= 0)
            {
                _ranges[existing] = _ranges[existing].Combine(range);
            }
            else
            {
                _ranges.Add(range);
            }
        }
    }

    private class PlaneSet
    {
        private Dictionary<int, Plane> _planes = new Dictionary<int, Plane>();

        public void AddMovement(int a, int b0, int b1)
        {
            Plane plane;
            if (!_planes.TryGetValue(a, out plane))
            {
                plane = new Plane();
                _planes[a] = plane;
            }

            plane.AddRange(new Range(b0, b1));
        }

        public bool Intersects(int a0, int a1, int b)
        {
            var possible = _planes.Where(x => x.Key >= a0 && x.Key <= a1);
            foreach (var plane in possible)
            {
                if (plane.Value.Intersects(b))
                {
                    return true;
                }
            }
            return false;
        }
    }

    private PlaneSet _horizontal;
    private PlaneSet _vertical;
    private int _x;
    private int _y;

    public int FindPathIntersection(IReadOnlyList<int> movements)
    {
        _horizontal = new PlaneSet();
        _vertical = new PlaneSet();
        _x = _y = 0;

        for (int i = 0; i < movements.Count; i++)
        {
            if (Move(movements[i], i % 4))
            {
                return i;
            }
        }

        return -1;
    }

    private bool Move(int amount, int direction)
    {
        switch(direction)
        {
            case 0:
                return MoveVertical(amount);
            case 1:
                return MoveHorizontal(amount);
            case 2:
                return MoveVertical(-amount);
            case 3:
                return MoveHorizontal(-amount);
        }

        throw new ArgumentException("direction = " + direction);
    }

    private bool MoveHorizontal(int amount)
    {
        int x0 = amount < 0 ? _x + amount : _x;
        int x1 = amount < 0 ? _x : _x + amount;
        _x += amount;

        if(_vertical.Intersects(x0, x1, _y))
        {
            return true;
        }

        _horizontal.AddMovement(_y, x0, x1);
        return false;
    }

    private bool MoveVertical(int amount)
    {
        int y0 = amount < 0 ? _y + amount : _y;
        int y1 = amount < 0 ? _y : _y + amount;
        _y += amount;

        if (_horizontal.Intersects(y0, y1, _x))
        {
            return true;
        }

        _vertical.AddMovement(_x, y0, y1);
        return false;
    }
}

I'm taking an IReadOnlyList rather than IEnumerable since returning a result index (and determining direction by index) on a non-indexed collection doesn't seem like a good fit.

One thing I'm not sure about - how much merging Plane should do for overlapping Ranges, which adds more processing time when adding movements but speeds up checking for intersection. It would depend on how common such overlap is; currently it merges with one, if possible, but doesn't go through and do all possible merging.

Also, PlaneSet could use buckets (size = 1000, so a given movement would cross no more than two), but I'm not sure that would have much benefit, given that the collision is likely to happen near the origin.