[Community Puzzle] The lost files

Puzzles
#1

https://www.codingame.com/training/medium/the-lost-files

Send your feedback or ask for help here!

Created by @Fluxor,validated by @JBM,@Sceurpien and @TheDarkByte.
If you have any issues, feel free to ping them.

#2

I would have set this one to hard (I know, personal opinion) because if you tackle it without prior graph knowledge it can become quite complex. Nice puzzle otherwise, thanks :+1:

2 Likes
#3

Cool Problem.

#4

So from the description I am assuming the graph’s are planar, however no test cases besides the first one seems to follow Euler’s rule. So how do you calculate the number of faces the graph has without using Eulers rule?

1 Like
#5

I do not want to spoil more here, but I can tell all graphs are planar.
There must be something you are doing wrong (which is probably related to how you handle the oceans…).
And just FYI this problem is solvable without using the rule you mention: comp0zr came up with an elegant BFS/DFS solution to count the faces.

2 Likes
#6

Remember that Euler is for single planes. Consider how continents act as planes, and what the rule actually is counting when you use it.

#7

So I’m able to solve 75% but the last one times out. I think I am using a solution that is probably not great.

I know it has to do with the way I determine how many continents there are. I iterate through the node number list and try find paths to all points. I suppose BFS is more optimal in how it computes paths?

#8

I did solve successfully the puzzle (once I did read the few comment in this discussion, which gave me an clue) and I was willing to compare my solution with other people solution, unfortunately I did write it in swift and nobody did solve the puzzle in swift. I can eventually translate my code in another language ( java or C or C++) which will enable me to access to the code used for this solution,I am just wondering which language was the more used to solve the puzzle …? so that I am sure I will have access to the solution ( especially I’d like to see the BFS/DFS solution that @Fluxor did comment
)

#9

If you look at the solutions page you can see who / how many shared for languages you haven’t used, just not open them to see the actual code.

1 Like
#10

Ooops I did miss this menu
Thanks

#11

Hello, thanks to the help of the comments I learn out about the euler formula. I applied the DFS algorithm to find out the number of connected components and count how many vertices and edges each connected component has. For each connected component I applied the euler formula, subtracting 1 from the result, because the formula counts the external area as a face.

#12

I feel like I missed something here. My solution doesn’t do anything very complex at all, certainly not what I would consider BFS or DFS. I don’t want to give too much away but did anyone else find an alternate solution that is really easy (basically sorting into lists)?

#13

There are two parts in this problem, connected components and number of faces.
I guess you talk about the connected components.

I don’t know, you have to traverse your graph somehow, usually you launch a traversal, BFS or DFS from every non visited vertex, you count how many explorations you actually did and that’s it.
A DFS is something really simple so maybe you do a DFS without realizing.

I don’t know exactly what you sort and how but I suppose you have to iterate on your list at some point and it might just be equivalent to launching traversals in your graph.

There are other methods to find connected components on the fly with union-find (it’s basically building a forest) but it’s not needed here.

1 Like
#14

Why does one need DFS/BFS to calculate the number of connections ? And how does one applies the euler formula for each connected component ??? Sometimes it sucks not to be able to learn from the solutions already present (((

#15

Interesting way to get introduced to graphs. I don’t deal with them much, and I ended up doing a brute force approach.

#16

DFS/BFS is used to detect the connected components.
Once you get this, you have to gather the vertices and the edges for each component, then apply the Euler formula : Vertices_count - Edges_count + Faces_count = 2 if you take into account the outside polygon else 1.

1 Like