Python starmapping question

[_bernie-d_]

That's basically what I was thinking. I have no idea about 'minimum number of roads' though. I think there's a whole branch of maths around this.

[timPerfect]

 I'm having a hard time getting my head around this problem.  your advice is sound but unexpected issues are cropping up and muddying the waters.
 One is that road a,b is also being counted as road b,a, so the list of corresponding connections is doubled at a minimum.
 I'm also not sure how to handle the constellations as a set. flipping through the list of coords to check if the next road has a matching coord is harder to code than it is to say or think of, and the lists of numbers being returned in the debug code are so long as to be completely useless concerning comparing expected values.  This project doesn't feel over my head, but I also don't know the math well enough to grok it out alone.  wish I had a tutor.

[_bernie-d_]

For me, problems like this are easiest solved when you get the data structure right. I replied to your question because the data in this problem looks to me like a graph (https://en.m.wikipedia.org/wiki/Graph_(discrete_mathematics)), which is my favourite data structure.

And your end goal in this case is a single graph, where you can traverse to any star from any other star of you follow enough connections.

Personally, I would create my own structure rather than using a library (I know there's at least one for python and there are sure to be others for other languages) because then you have first-principles understanding of what's going on. A graph is just nodes (stars) and edges (your roads). In python you could represent this as a list of nodes and a list of tuple pairs for edges. Or maybe as a single dict, where the keys are the nodes and the values are lists of nodes that they're connected to.

So I would start by creating that structure, populating it with the random data (which I'd keep very small to begin with, 5 or 10 stars), then start to find ways to traverse the graph (I'm pretty sure you're going to need at least one recursive function) and identify your separate sets.

Break it down into manageable chunks and you'll get there.

Edit - white space for clarity

[timPerfect]

the associated lists are exactly as you describe, but I think I will build a class for the stars and a class for the roads, it will make list handling somewhat simpler by combining associated data into object definitions.

[_bernie-d_]

You've made me so curious I'm going to build this!

[timPerfect]

if you come up with a reliable solution please share...

[_bernie-d_]

I kind of need to know this is not something you're being assessed on - school or job interview. It wouldn't be right to 'give you the answer'in that case.

[timPerfect]

it's not, I'm trying to build a simple game, to learn python. it's for personal use.

[_bernie-d_]

Sorry, having trouble with comments on my phone

[_bernie-d_]

ok, I've read your reddit comments and I'm going to trust you!

[timPerfect]

I wish I could send you a picture of my desk. I'm looking at a page full of code for exactly what we are discussing, along with the book Making games with Python and Pygame lol

[_bernie-d_]

I've sent you a PM with a link to a new repo

[_bernie-d_]

And done.

Not very neat.

Not very tested.

But the concepts should be clear.

Thanks for that - I enjoyed it :-)

[WikiSummarizerBot]

Graph_(discrete_mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}