I had the same issue as slava_spamec, getting the same path in test 5, and the issue was that I was sorting my queue using my “best_distances” dict on the id of the candidate nodes, instead of the actual distance of the paths…
Funny thing is all the other tests pass using a random distance…
For those who will pass by here, who have done a Dijkstra and the result is as follows for test #5 (Large number of stages):
Distance: 13.4046721009
Einstein
Geraudiere
Petite Censive
Riviere
Recteur Schmitt
Ecole Centrale - Audencia
Facultes
Morrhonniere
Michelet
St-Felix
Motte Rouge
St-Mihiel
50 Otages
Place du Cirque
Commerce
Hotel Dieu
Aime Delrue
Vincent Gache
Wattignies
Mangin
Pirmil
Pont-Rousseau - Martyrs
8 Mai
Baliniere
Melies
Croix de Reze
Moulin a l’Huile
Jaguere
Jules Valles
Les Ailes
Galheur
Maybe you made the same stupid mistake as I did: treating distances everywhere in “double” except at one place in “int”.
The distance I find now is 13.3621223153 and everything passes.
Hi Everyone. I am at a loss. I pass all the visible test cases but fail the hidden Large number of Stages.
I am using A* and it seems to be working. Any suggestions. I feel that my distance calculations might not be correct. Does anyone have an example of how far two specific locations to test that specific function?
Have you read through the discussion above? Some have the same problem as yours and others have suggested possible fixes.
Me have same results
//DEBUG//
current_stop: "Einstein", neighbour: "Rene Cassin", priority: 412.45595266186575
current_stop: "Einstein", neighbour: "Geraudiere", priority: 390.244116046771
///logic cur_distance + haversine distance + Euclidean distance///
priority = current_distance + current_stop.caldistance(neighbour) + heuristic(neighbour, end)
[mod edit: please do not post full code on the forum]
but I can’t find the solution of This ERROR
Segmentation fault.
at Answer.c. function findval (station=0x7ffffff75ea5 “TILL Durand”, inform=0x7ffffff75ea0, trig=0) on line 142
at Answer.c. function main () on line 55
How do you think of this Code and How can I solve it?
Hello and happy new year !
I failed on fifth test, I obtain (I use dijkstra)
EINS to GALH
Total Nodes: 1019
Shortest path: /EINS/GERA/PCSI/RVRE/RTSC/ECSU/FDLE/PPFA/MORH/FTDO/LJOS/RREN/CSMP/LSYY/FFAU/POIT/VIAR/JJNA/BRTA/COMM/RPBL/PIRM/PROU/MAI8/BALI/MELI/XREZ/MHUI/JGUE/JVAL/LAIL/GALH
Path length: 32
All nodes connected (1, yes / 0, no): 1, Total dist: 13.1778
Wanted path: /EINS/RCAS/CDAN/LCLE/BTRA/RCPE/BDPA/VALL/PDCE/FRET/LCSE/BLZZ/RLON/AMER/RREN/LGOF/BRUN/BAIR/SSTA/TLSA/OTAG/CRQU/COMM/HODI/ADEL/VGAC/WATT/MGIN/PIRM/PROU/MAI8/BALI/MELI/XREZ/MHUI/JGUE/JVAL/LAIL/GALH
Path length: 39
All nodes connected (1, yes / 0, no): 1, Total dist: 13.2044
To calculate dist I use
auto calcDist = [&](const float& lat, const float& lon){
auto x = (lon - _lon) * std::cos((lat + _lat)/2.f);
auto y = lat - _lat;
return std::hypot(x, y) * 6371.f;
};
Anyone can help me please ?
Resolved:
Ok I found it
Node(string id, string name, float lat, float lon)
:_id(std::move(id)),
_name(std::move(name)),
_lat(degToRad(lat)),
_lon(degToRad(lat)){ <= was here
}
Hello.
I passed all the test and all the validators except the 4th (“Large number of stages”).
I do convert from degrees to radians and i use a Dijkstra’s algorithm.
I can’t find out if i don’t find the good answer or if i’m too slow to find it.
Has someone an idea ?
Thank you.
I don’t know what the input to that validator is, but if you want, you may send me your code in private message and I’ll try to see if I can spot any issues in it.
Thanks for pointing that out. I forgot to convert degree to radian too.
MGIN → MGIN too. Maybe there are more.
I like this puzzle except of this thing.
Hello after 4 years, I saw that no one has answered your comment (but I saw that you are still visiting this forum - Oct 20, 2024 5:29 pm) what could be the reason for the incorrect answer. I got the same answer, but all the hints in this topic did not help me (how I hate reading hints / forums if I can not solve the puzzle and this is the first time in 107 solved puzzles I decided to look at the forum because I was sure that I was finding the distance correctly, and not a single comment in this topic helped me, because I did everything correctly initially, but I opened the wiki to read about Dijkstra because I do not use it in the form in which it is described on the wiki, I rewrote my solution under the algorithm that is on the wiki, and it did not help me either).
And my problem was how I reconstructed the path: starting from the end, among the nodes that lead to the current node, I looked for a node with the minimum weight and so on until the beginning of the path.
The solution to this problem is to store in the current node information about the previous node with the minimum path to the current node (as in the Dijkstra algorithm).
But it is important to note that the length of the path to the last node in the 5th test is 13.362122315310147 (this value is already encountered in this topic), but your length is 0.06 more, which may mean that the algorithm for finding the shortest path is not working correctly or there is a problem in the calculation and the accuracy is lost somewhere.
P.S. People smarter than me, tell me why finding the incoming node with the minimum cost does not find the correct path?
Thanks for the hint!
Hard to plunge again into debugging this problem, months later, but maybe your post will help me.
For the 5th test I have:
Distance from StopArea:EINS to StopArea:GALH: 13.362122315310147
Which seems to be the same as you mention, and yet I get:
Failure
Found: Geraudiere
Expected: Rene Cassin