C# Check if sections intersect

Question

I have a list of N consecutive vertical and horizontal sections of fixed dimensions in a form of a succession of directions (right → ; left ←; down ↓; up ↑). The program should return true if the sections intersect. For example: N = 6: { up, left, down, down, right, up} - return True. I got the coordinates for every section, but I don't really know how to finish this. Any ideeas?

static (int, int) GetCoordinates(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0, 0);
    foreach (string move in sectionDirection)
    {
        switch (move)
        {
            case "left":
                pos = (0, 0);
                pos.X--;
                break;
            case "right":
                pos = (0, 0);
                pos.X++;
                break;
            case "down":
                pos = (0, 0);
                pos.Y--;
                break;
            case "up":
                pos = (0, 0);
                pos.Y++;
                break;
        }
    }

    return (pos.X, pos.Y);
}

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    // I need help here.
}

Answer 1

The simplest code change I can think of would be to use something that will remember all the visited locations and can tell you whether or not you have visited a location before. Such an object needs a way to add a location to its memory, and needs a way to test to see if a location is remembered.

Believe it or not, you can just use string to do this. Because a tuple will convert to a string as (0, 0) with parentheses and commas delimiting the fields, it's fine to just concatenate them all into a string and then use string.Contains to see if a location exists. (This is kind of silly, and I'd prefer a HashSet instead of a string for efficiency, but you said in your comment you cannot.)

It will build up a string that looks like: (0, 0)(0, 1)(-1, 1)(-1, 0)...

To remember a location, append it to the end of the string with the += operator. When you do memory += pos then pos will automatically get converted to a string using ToString().

To check if a location exists, use memory.Contains(pos.ToString()). In this case you have to explicitly convert the tuple to a string with .ToString() to pass it as an argument to .Contains.

private static bool CheckForIntersections(string[] sectionDirection)
{
    string memory = "";
    (int X, int Y) pos = (0, 0);
    memory += pos;
    foreach (string move in sectionDirection)
    {
        switch (move)
        {
            case "left":
                pos.X--;
                break;
            case "right":
                pos.X++;
                break;
            case "down":
                pos.Y--;
                break;
            case "up":
                pos.Y++;
                break;
        }
        if (memory.Contains(pos.ToString())) return true; // It was revisited
        memory += pos;
    }
    return false;
}

Answer 2

This is how I would do it in one line essentially.

public static (int x, int y)[] GetCoordinates(Directions directions)
{
   // accumulate a list with coordinates here
}

public static bool Intersect(params Direction[] directions)
{
    var coord = GetCoordinates(directions);
    return coord.Distinct().Count() < coord.Count();
}

Check if any of the coordinates are duplicates by seeing if the set of distinct values has less elements that the full set of coordinates.

PS. I prefer to use enum for things with finite values like directions

public enum Direction
{
    None,
    Left,
    Right,
    Up,
    Down,
}

Answer 3

Just imagine yourself being on an infinitely large chess board and somebody tells you to put a step in any direction he tells you. The only way to know if you have already crossed a point is by putting some stuff on every point you have passed and in case you get the command to go to such a point, you shout "Intersect!" :-)

If it's just about getting back to your starting point, you just count the amount of commands you've received: if the number of "up"s equals the number of "down"s and the number of "left"s equals the number of "right"s, you know that you have reached your starting point.
If you are not allowed to keep four counters, you can do it with two variables, "hor" (for horizontal) and "ver" (for vertical):

up means ver++
down means ver--
left means hor--
right means hor++

If, at the end, both "hor" and "ver" are back to zero, you have reached again your starting point.

Have fun :-)