TAN Network puzzle discussion

If you don’t want to use A*, you can also use dijkstra with a priority queue instead of computing the minimum, it works for the “large number of stages” test.

Hello,

I have the same problem as many, can someone who found the right solution provide the total distance he/she has found?

I ve found 13.551408331759312 for the solution taking in consideration the fact that stations have the same name.

When I check the solution of slava_spamec (which is also mie) I have 13.424056863059045

If you end up with the same road as slava_spamec, then my answer to his post is also valid to you.

To say it another way, the fact you have the same solution means you used a breadth-first search instead of Dijkstra’s algorithm. Though they’re pretty similar, Dijkstra’s needs a sorted queue because a path can be shorter even if it means going through more nodes. In a case where all distances between nodes are the same then a BFS is equivalent, but as soon as distances are different (as in this puzzle) a BFS doesn’t work anymore.

Passed all the tests in IDE.
Passed all the final tests except the last one : “Chemin impossible”

Cannot figure why.

Solved. I didn’t handled a case where a stop is a dead-end, ie a node you can reach but never leave . Don’t forget the graph is oriented !

I use Dijkstra, my queue IS sorted by distance and I get slava_spamec’s answer for the fifth test.
I already coded Dijkstra with the same code and it worked before.
I reread my distance function, of course I converted degrees in radians…

Then you can send me your code if you like, I could try to help you fix your issue.

Edit: To anyone interested as it was the issue here, and as already said in this topic: stop name is not unique whereas unique identifier is. This means you must not use the stop name as a key in your map/dictionary/whatever-it-is-called-in-your-language because 2 stops with the same name doesn’t have the same position nor the same links.

1 Like

Thank you.

How unlikely is that: My program passed all the tests in the IDE, but failed 5 out of 6 in the final valuation. I have absolutely no idea what the problem could be. Is there any way to get some feedback why the final tests failed?

PS: Now, it works. It seems that my old parser was too rigid for the input. Does anybody know whether the input does exactly match the specification from the description?

Take care to COMM -> COMM :o

Oh man, thank you so much! Was passing all of the IDE tests and then failed large # one in validation. Fixing now. Weird how it works for everything else.

i did A*! but not in C++

Tests in IDE pass but validation test “Large number of stages” is failed for me.

And I don’t have any hint whether it is performance or some liminal case.

If number of stations in IDE test and validation test differs significantly then it is not fair I think.

Read NewboO’s message: “stop name is not unique”.

really:

StopArea:HFNA,“Haute Foret”,47.23351996,-1.55542776,1,
and
StopArea:HFVE,“Haute Foret”,47.16828563,-1.46559936,1,

StopArea:BAIR,“Bel Air”,47.22556650,-1.55947121,1,
and
StopArea:BZIN,“Bel Air”,47.26678881,-1.48951130,1,

StopArea:HMVE,“8 Mai”,47.17268755,-1.47234134,1,
and
StopArea:MAI8,“8 Mai”,47.18909416,-1.55117093,1,

I’m in the same situation. I pass all validations in the actual question, but fail the large number and the 5 stops 2 routes.
Is there any way we can see what the input’s for those tests are?

Read NewboO’s message: “stop name is not unique”.

I don’t use the stop name for anything other than the final print. I use the ID (first param) for all references.

Maybe your algo is too slow.

I use Dijkstra’s, and I’d have hard time saying its too slow for those, but passes all the samples. Especially given one that it doesn’t pass seems to indicate its only 5 nodes big. I’m wondering if maybe there is some input variation, that I don’t parse correctly that is not represented in the samples…