Check if N sections intersect

Question

folks! I need to implement the function static bool CheckSectionsIntersect that checks if the sections intersect (right → ; left ←; down ↓; up ↑). Given a list of N consecutive vertical and horizontal sections of fixed dimensions in a form of a succession of directions. I have to think that I would have a route of N sections. The function should return True if I get to a point I've been to before. For example:

N = 6: { up, left, down, down, right, up} - return True.

⬇⬅
⬇⬆  <- Start
➡⬆

N = 4: {down, left, up, left} - return False.

⬅⬇  <- Start
⬆⬅

The code I wrote, but is incomplete because I need some suggestion to how should be the function:

    static void Main()
    {
        string userInput = Console.ReadLine();
        int numberOfSections = Convert.ToInt32(userInput);
        string[] sectionDirection = new string[numberOfSections];
        for (int i = 0; i < numberOfSections; i++)
        {
            sectionDirections[i] = Console.ReadLine();
        }

        Console.WriteLine(CheckSectionsIntersect(sectionDirection, numberOfSections));
    }

    static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
    {
        return true; // I need an implementation here
    }
}

}

May I have any suggestion for this implementation, please? Thank you very much!

Answer 1

I'm not sure I understand what you are saying. If you want to see if you end in a place where you have been, just make an array of tuples. In each move save your coordinates (starting form 0,0). At the end of the path check if your coordinates are in the array. Or at the end of each move that if you want to check for places where you have already been.

Edit:

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
    {
        (int X, int Y) pos = (0, 0); //Variable to track our actual position. Start position (0,0)
        List<(int X, int Y)> coordinates = new List<(int X, int Y)>(); //List where we are going to keep the coordinates
        foreach (string move in sectionDirection) //for each move
        {
            coordinates.Add(pos); //Add our current position to the list
            switch (move)         //Make a move
            {
                case "left":
                    pos.X -= 1;
                    break;
                case "right":
                    pos.X += 1;
                    break;
                case "down":
                    pos.Y -= 1;
                    break;
                case "up":
                    pos.Y += 1;
                    break;
            }
            if (coordinates.Contains(pos)) { return true; } //If our new position is already in the list, we have been there.
        }
        return false;
    }

I have tested it and it works. For this purpose it is easier use a list than an array. This is due the methods .Add() an .contains().

This code is not the strongest one (for example it doesn't accept Upper letters). But since you are a beginner it should be enough. I encourage you to improve it to keep learning.

Answer 2

If you think of a cartesian grid, and you start at 0,0 with a left/right incrementing/decrementing the x coordinate and an up/down the y coordinate, then the answer is do you go back past 0,0 at any point.

static Dictionary<string,(int X,int Y)> transforms = new Dictionary<string, (int X, int Y)>{
    ["U"] = (0,1),
    ["D"] = (0,-1),
    ["L"] = (-1,0),
    ["R"] = (1,0)
};

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0,0);
    for(var i = 0;i<numberOfSections;i++)
    {
        if(!transforms.TryGetValue(sectionDirection[i], out var transform))
           throw new ArgumentException("sectionDirections");
        pos.X += transform.X;
        pos.Y += transform.Y;
        if(pos.X == 0 && pos.Y == 0)
            return true;                
    }
    return false;
}

Live example with your 2 test cases: https://dotnetfiddle.net/p5JY61

The above only checks that you end up back at 0,0 - however if you want to determine if you enter any co-ordine you have been to previously you simply need to keep track of where you've been using a collection and instead of checking whether you're back at 0,0 check if you're anywhere you've been before.

static bool CheckSectionsIntersect(string[] sectionDirection, int numberOfSections)
{
    (int X, int Y) pos = (0,0);
    var visited = new List<(int X, int Y)>{ pos };
    for(var i = 0;i<numberOfSections;i++)
    {
        if(!transforms.TryGetValue(sectionDirection[i], out var transform))
           throw new ArgumentException("sectionDirections");
        (int X, int Y) newPos = (pos.X + transform.X, pos.Y + transform.Y);
        
        if(visited.Contains(newPos))
            return true;    
                    
        pos = newPos;
        visited.Add(newPos);
    }
    return false;
}

Live example: https://dotnetfiddle.net/FyJYrr