Topics

C#•14mo ago

❔ Finding the right algorithm for this task 🤔

Hello 👋 I'm quite new to C# and still don't know which algorithm is used when, what it does, how is it implemented, etc. I found some programming tasks on the internet and I'd like to learn the algorithms that way. The first task is:

- You receive input in this form:

2 3
1 0 DVI
2 0 SATA
0 1 HDMI
2 2 HDMI
1 3 USB

2 3
1 0 DVI
2 0 SATA
0 1 HDMI
2 2 HDMI
1 3 USB

The context:

There is a room with cables on the ground everywhere. You need to have 2 cables of the same connector type to connect them together. For example: You can connect USB-C with USB-C but you can't connect USB-C with HDMI.

Where:

2 3 defines the size of the room (a rectangle). 2 is the length of the rectangle and 3 is the width

For each line in this format:

x y connector type E.g. 1 0 DVI

1 is a point on the coordinate of the rectangle's length and 0 is a point on the width

Note:

- All points (connectors) from the input will be on the edges of the rectangle never inside of it.

The goal:

The aim of this program is to find out whether all the cables can be connected together without being crossed. So just imagine the points on the rectangle coordinates. Then connect every TWO points with the same connector with line. Check if the lines don't intersect. If yes, write "It's not possible to connect the cables." If no, write "It's possible to connect the cables."

- I just want to help with what type of algorithm should I use for this task. Just the name is enough, I want to study the algorithm after and then try to code it on my own. Thanks for any help 🫶❤️

No description

65 Replies

Carly.TeamSail•14mo ago

Search intersecting lines algo

hurikanOP•14mo ago

thanks, I will try to study that

Carly.TeamSail•14mo ago

I guess you could use AABB but its more for 3d i think

JansthcirlU•14mo ago

just to give you a taste, I'm not sure how to solve it either but hopefully this points you in the right direction

No description

hurikanOP•14mo ago

well thank you but this doesn't help me

JansthcirlU•14mo ago

from what I've understood from Bing chat, it seems like your problem is analogous to checking if a graph is planar, so that would solve part of your problem I think

hurikanOP•14mo ago

I just generated code from Bing chat and it doesn't work

JansthcirlU•14mo ago

can you post what it said?

hurikanOP•14mo ago

message.txt

JansthcirlU•14mo ago

oof that's a lot

hurikanOP•14mo ago

No description

hurikanOP•14mo ago

No description

JansthcirlU•14mo ago

I don't know if you're allowed to from your school but how about we create a Graph class

hurikanOP•14mo ago

it's not a school assignment, so it's fine 😄

JansthcirlU•14mo ago

I'd start there, given that it's a graph algorithm, it probably makes more sense to use a graph object for it

hurikanOP•14mo ago

I don't know what is a graph object, I'm beginner I know what is class

JansthcirlU•14mo ago

ah hmm, knowing what a class is could help you a lot in programming, they're very commonly used to model systems and a graph you can think of as points that are connected by lines, and the points represent something (like facebook users) and the lines that connect them represent a relationship between them (like friendship or following) I suggest you walk through $helloworld first

MODiX•14mo ago

Written interactive course https://learn.microsoft.com/en-us/dotnet/csharp/tour-of-csharp/tutorials/ Videos https://dotnet.microsoft.com/learn/videos

hurikanOP•14mo ago

I know what is graph from Math, but I don't know how to code it in c#

JansthcirlU•14mo ago

I'm confident Bing chat will be able to help you there, and much faster than I ever could

hurikanOP•14mo ago

do you think you could code it for me? I need some reference to learn from it, I can learn by thinking about the code. But I can't do that without the code

JansthcirlU•14mo ago

oh Bing chat can give you the code

hurikanOP•14mo ago

but it didn't 🙁

JansthcirlU•14mo ago

try asking it something along the lines of:

Can you make me a graph class in C# where the vertices represent coordinates with a name and the edges represent a connection between the vertices?

Can you make me a graph class in C# where the vertices represent coordinates with a name and the edges represent a connection between the vertices?

and let me know what code it gave you

hurikanOP•14mo ago

using System;
using System.Collections.Generic;

class Graph
{
    private Dictionary<string, List<string>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<string, List<string>>();
    }

    public void AddVertex(string vertexName, int xCoord, int yCoord)
    {
        string vertex = $"{xCoord},{yCoord} ({vertexName})";

        if (!adjacencyList.ContainsKey(vertex))
        {
            adjacencyList.Add(vertex, new List<string>());
        }
    }

    public void AddEdge(string vertex1Name, int vertex1XCoord, int vertex1YCoord, string vertex2Name, int vertex2XCoord, int vertex2YCoord)
    {
        string vertex1 = $"{vertex1XCoord},{vertex1YCoord} ({vertex1Name})";
        string vertex2 = $"{vertex2XCoord},{vertex2YCoord} ({vertex2Name})";

        if (!adjacencyList.ContainsKey(vertex1))
        {
            AddVertex(vertex1Name, vertex1XCoord, vertex1YCoord);
        }

        if (!adjacencyList.ContainsKey(vertex2))
        {
            AddVertex(vertex2Name, vertex2XCoord, vertex2YCoord);
        }

        adjacencyList[vertex1].Add(vertex2);
        adjacencyList[vertex2].Add(vertex1);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList.Keys)
        {
            Console.Write($"{vertex}: ");

            foreach (var neighbor in adjacencyList[vertex])
            {
                Console.Write($"{neighbor}, ");
            }

            Console.WriteLine();
        }
    }
}

using System;
using System.Collections.Generic;

class Graph
{
    private Dictionary<string, List<string>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<string, List<string>>();
    }

    public void AddVertex(string vertexName, int xCoord, int yCoord)
    {
        string vertex = $"{xCoord},{yCoord} ({vertexName})";

        if (!adjacencyList.ContainsKey(vertex))
        {
            adjacencyList.Add(vertex, new List<string>());
        }
    }

    public void AddEdge(string vertex1Name, int vertex1XCoord, int vertex1YCoord, string vertex2Name, int vertex2XCoord, int vertex2YCoord)
    {
        string vertex1 = $"{vertex1XCoord},{vertex1YCoord} ({vertex1Name})";
        string vertex2 = $"{vertex2XCoord},{vertex2YCoord} ({vertex2Name})";

        if (!adjacencyList.ContainsKey(vertex1))
        {
            AddVertex(vertex1Name, vertex1XCoord, vertex1YCoord);
        }

        if (!adjacencyList.ContainsKey(vertex2))
        {
            AddVertex(vertex2Name, vertex2XCoord, vertex2YCoord);
        }

        adjacencyList[vertex1].Add(vertex2);
        adjacencyList[vertex2].Add(vertex1);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList.Keys)
        {
            Console.Write($"{vertex}: ");

            foreach (var neighbor in adjacencyList[vertex])
            {
                Console.Write($"{neighbor}, ");
            }

            Console.WriteLine();
        }
    }
}

this is just the graph class?

JansthcirlU•14mo ago

that seems like a good start, I think

hurikanOP•14mo ago

ok

JansthcirlU•14mo ago

I would personally add a few more improvements, but I don't want to write the code myself, so try asking Bing to improve it:

I don't want the coordinates to be included in the string, but they should be part of the representation.

I don't want the coordinates to be included in the string, but they should be part of the representation.

hurikanOP•14mo ago

using System;
using System.Collections.Generic;

class Vertex
{
    public string Name { get; set; }
    public int XCoord { get; set; }
    public int YCoord { get; set; }

    public Vertex(string name, int xCoord, int yCoord)
    {
        Name = name;
        XCoord = xCoord;
        YCoord = yCoord;
    }

    public override string ToString()
    {
        return Name;
    }
}

class Graph
{
    private Dictionary<Vertex, List<Vertex>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<Vertex, List<Vertex>>();
    }

    public void AddVertex(Vertex vertex)
    {
        if (!adjacencyList.ContainsKey(vertex))
        {
            adjacencyList.Add(vertex, new List<Vertex>());
        }
    }

    public void AddEdge(Vertex vertex1, Vertex vertex2)
    {
        if (!adjacencyList.ContainsKey(vertex1))
        {
            AddVertex(vertex1);
        }

        if (!adjacencyList.ContainsKey(vertex2))
        {
            AddVertex(vertex2);
        }

        adjacencyList[vertex1].Add(vertex2);
        adjacencyList[vertex2].Add(vertex1);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList.Keys)
        {
            Console.Write($"{vertex}: ");

            foreach (var neighbor in adjacencyList[vertex])
            {
                Console.Write($"{neighbor}, ");
            }

            Console.WriteLine();
        }
    }
}

using System;
using System.Collections.Generic;

class Vertex
{
    public string Name { get; set; }
    public int XCoord { get; set; }
    public int YCoord { get; set; }

    public Vertex(string name, int xCoord, int yCoord)
    {
        Name = name;
        XCoord = xCoord;
        YCoord = yCoord;
    }

    public override string ToString()
    {
        return Name;
    }
}

class Graph
{
    private Dictionary<Vertex, List<Vertex>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<Vertex, List<Vertex>>();
    }

    public void AddVertex(Vertex vertex)
    {
        if (!adjacencyList.ContainsKey(vertex))
        {
            adjacencyList.Add(vertex, new List<Vertex>());
        }
    }

    public void AddEdge(Vertex vertex1, Vertex vertex2)
    {
        if (!adjacencyList.ContainsKey(vertex1))
        {
            AddVertex(vertex1);
        }

        if (!adjacencyList.ContainsKey(vertex2))
        {
            AddVertex(vertex2);
        }

        adjacencyList[vertex1].Add(vertex2);
        adjacencyList[vertex2].Add(vertex1);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList.Keys)
        {
            Console.Write($"{vertex}: ");

            foreach (var neighbor in adjacencyList[vertex])
            {
                Console.Write($"{neighbor}, ");
            }

            Console.WriteLine();
        }
    }
}

JansthcirlU•14mo ago

okay, great, so looking at that code, can you try to explain to me what it does? no need to be very detailed, just tell me what comes to mind

hurikanOP•14mo ago

So, there's some defining of class called Vertex, where it creates some variables like coordinates and name of the vertex then there is class Graph where is some adjacency list, that is probably the connecting between vertices then creating some edge and printing out vertex and it's neighbour sorry i really dont know

JansthcirlU•14mo ago

no worries does this ring a bell at all, like what you learned in maths class?

hurikanOP•14mo ago

well we did graphing in Math linear, quadratic, logarithm, sine, cosine, tangens, cotangens, etc.. but I don't really know how to connect this in programming

JansthcirlU•14mo ago

oooh I see graphs as in functions

hurikanOP•14mo ago

yes do you mean different graphs?

JansthcirlU•14mo ago

okay well, this is a different kind of graph, kind of unfortunate that they have the same name

hurikanOP•14mo ago

how are these graphs called?

JansthcirlU•14mo ago

they're called graphs, and there's a whole discipline of mathematics dedicated to them called 'graph theory' you'll probably need to learn about that a bit before you can understand how to solve this problem

hurikanOP•14mo ago

alright, I'm going to, I really want, but first I would also like to finish the code so I can use it in the future, can we?

JansthcirlU•14mo ago

well, I'm not very good at graph theory myself so I don't think I could help you get working code all the way I'm afraid but you could try asking Bing to make you an algorithm to check if a graph is planar based on that class it's made for you earlier

hurikanOP•14mo ago

@hypersensitive internet denizen oh now I'm starting to find out what graphs are I didn't even know there is this huge area in programming "Graph theory" I will look into that There are some courses and tutorials

JansthcirlU•14mo ago

yup, it started as a thing in maths but it's very useful for programming

hurikanOP•14mo ago

By the way the task we discussed here is from correspondence seminar in which I enrolled There is submission on 27th October I would like to give the code to that website to control, but I can't learn graph theory in 2 days Do you know how could I get the code? you probably don't want to, right?

JansthcirlU•14mo ago

uhh, I have no idea, personally, I'd just try Bing chat or ChatGPT for a while maybe you can learn the essentials of graph theory faster using those only the bits and pieces that you need

hurikanOP•14mo ago

I tried but I never got it to work

JansthcirlU•14mo ago

what did they give you? did you ask for an algorithm to check if a graph was planar?

hurikanOP•14mo ago

message.txt

JansthcirlU•14mo ago

did you try asking it to give you an algorithm that uses the graph class it generated for you?

hurikanOP•14mo ago

this is what it generated:

hurikanOP•14mo ago

message.txt

JansthcirlU•14mo ago

did you run it?

hurikanOP•14mo ago

yes, still doesn't work, always outputs "pujde to" even though it should output "ajajaj" pujde to = it 's gonna work ajajaj = oh well/ oops

hurikanOP•14mo ago

this is the right output

No description

hurikanOP•14mo ago

and this program outputs 4 times "pujde to"

JansthcirlU•14mo ago

I'm sorry I can't be of more help

hurikanOP•14mo ago

I understand, never mind

JansthcirlU•14mo ago

all I can say is try get creative in asking questions to ChatGPT maybe it can't solve your problem directly but it could solve parts of your problem I would personally try to ask it the following things: 1. create a ConnectorGraph graph class with the vertices and edges as described 2. create a ConnectorGraphBuilder class that builds all possible graphs given the input (your text files) 3. create a ConnectorGraphChecker class that contains a method to see if a ConnectorGraph is planar

hurikanOP•14mo ago

ok I have one last idea, I will send you the whole assignment translated and you can read through it just for a minute and try to navigate me, please

JansthcirlU•14mo ago

I can't promise you anything, but sure

hurikanOP•14mo ago

Task 1

Euclidean cabling

The darkened room had a very low ceiling, probably only two meters. But it was spacious. Through the piles of boxes and cables, I could see a wall somewhere in the distance, disappearing in a cloud of dust. Around the perimeter of the room were seagulls made of all the materials that hold their shape, and flashing lights from various sources. 12 volt bulbs peeked through the LEDs, and a little further away, the glow of tubes seemed to be coming out. The light of the indicator lights mingled with the glow of seven-segment displays, character LCDs, and character lamps. A CRT monitor stood in the center of the room with a blinking terminal cursor illuminating the dust swirling in the air. As I stood there in awe, I almost didn't register that the door had closed behind me. I was left alone. The darkness and dust engulfed me. The terminal read, "Don't worry, Frodo. The Warden is not evil. He just doesn't know what to do anymore. His power is waning and he can't handle the System anymore. He needs someone young, and he senses hope in you. Terrible things are happening in the System right now. Help me. [Y/n]" I pressed the Y key. "First we need to get the wiring in order. All the devices in the room need to be connected. It doesn't matter how you do it, but each device needs to be connected to one other. But to keep the cables tidy, you can only run them along the ground and they can't cross." I looked around the room. All the devices were around its perimeter, and each device had just one socket to connect it to another. Now I just had to figure out the cables. Fortunately, there were boxes full of them lying around the room. They just weren't in great shape. They had all sorts of terminals and looked like they'd seen the glory days of Fortran. Their insulation was cracked, leaky in many places, and the metal of the cables showed through the holes. But all the cables had one thing in common. They always had the same two terminals.

Input

The first line contains a natural number t (1≤t≤ 1000), which indicates the number of entries that follow. On the first line of each assignment there are three numbers separated by a space: h, w, n (1≤ h≤ 10000, 1≤ w≤ 10000, 1≤ n≤ 40000). The number h denotes the length of the room, w denotes the width of the room and n denotes the number of devices. This is followed by n rows of information about each device. Each line contains three spaces separated by y, z,c (a number, a numeral and a string of letters) (0 ≤ y ≤ h, 0 ≤ x ≤ w, 1 ≤ |c| ≤ 100). The numbers y and z together denote the location of the device in the room, where y indicates the coordinate relative to the length and æ relative to the width. The upper left corner corresponds to the coordinate (y, x) = (0,0) and the lower right corner corresponds to the coordinate (y, x) = (h, w). The coordinates are followed by a character string c of length |c|≤ 100 indicating the device connector (i.e. all device names have a maximum of 100 characters). This device can only be connected to one device of the same connector. You can rely on all devices being located only around the perimeter of the room. Thus, formally, for each device at position (y, z), at least one of the following four conditions: y = 0, x = 0, y = h, x = w. Further, you can rely on the fact that no two devices are in the same coordinates.

Output

Your task is to report to the output for each of the t assignments if the cables in the room can be connected in such a way that no two cables cross and all devices are connected to one of the devices of the same connector. If this is not possible, report to the output "ajajaj" (in english it means "oh no" or "oops") Input

2
2 3 4
0 1 DVI
0 2 JASKM
2 1 DISPLAYPORT
2 0 SATA
2 3 2
1 0 HDMI
2 1 HDMI

2
2 3 4
0 1 DVI
0 2 JASKM
2 1 DISPLAYPORT
2 0 SATA
2 3 2
1 0 HDMI
2 1 HDMI

Output ajajaj pujde to (in english this means "it will work", it's possible to connect the cables without crossing) 2nd Input

2
2 3 4
1 3 VGA
O O USB-A
0 1 VGA
2 0 USB-A
2 3 4
2 3 ETHERNET
1 0 ETHERNET
0 1 USB-C
2 2 USB-C

2
2 3 4
1 3 VGA
O O USB-A
0 1 VGA
2 0 USB-A
2 3 4
2 3 ETHERNET
1 0 ETHERNET
0 1 USB-C
2 2 USB-C

Output pujde to ajajaj

JansthcirlU•14mo ago

@hurikan any luck so far?

hurikanOP•14mo ago

no I'm lost

JansthcirlU•14mo ago

did you try asking these three questions? https://discord.com/channels/143867839282020352/1166752214438658171/1166829099558371368

MODiX•14mo ago

JansthcirlU

I would personally try to ask it the following things: 1. create a ConnectorGraph graph class with the vertices and edges as described 2. create a ConnectorGraphBuilder class that builds all possible graphs given the input (your text files) 3. create a ConnectorGraphChecker class that contains a method to see if a ConnectorGraph is planar

Quoted by

<@154274815610454017> from #Finding the right algorithm for this task 🤔 (click here)

React with ❌ to remove this embed.

Accord•14mo ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

We are a programming server aimed at coders discussing everything related to C# (CSharp) and .NET.

54KMembers

View on Discord

Want results from more Discord servers?

Add your server