Feel free to send your feedback or ask for some help here!
Did anyone solve this with a-star (and checking if a node was already visited by a better path) in C++ ? I pass all the IDE tests but in evaluation I don’t pass the "Large number of stages " one and the impossible one (that last one would be normal since I only check if the start and destination are connected to at least one node). I tried iterative deepening a-star to, but not any more luck. So I’d just like to know if it is possible to solve it with a-star and my implementation of it is worth improving, or if it is way insufficient and I need to find a better algorithm (maybe memory-bounded a* (even though I don’t think memory is the issue) or a two-ways search, or recursive best-first search, but I thought a* was a better algorithm)
1 Like
Hey there! I tried to solve this problem with dijkstra’s algorithm in Java. I pass all tests in the IDE except the “Large number of stages”. My implementation finds solution which is different from the proposed for this test.
My solution has 28 stops and the proposed one - 39.
Here is my solution :
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
Gaston Veil
Republique
Pirmil
Pont-Rousseau - Martyrs
8 Mai
Baliniere
Melies
Croix de Reze
Moulin a l’Huile
Jaguere
Jules Valles
Les Ailes
Galheur
Is the problem is in my code, which probably make an error when calculate the minimal distance, or this is the proposed test result which is bad?
2 Likes
You’re probably not doing Dijkstra’s algorithm the right way.
Usually, puzzles on CodinGame use graphs where every vertices have the same weight so a simple breadth first search with a queue gives you the right result. However, Dijkstra’s algorithm actually say you have to take the closest unvisited node so in a case where vertices have different weights, your queue must always be sorted by distance. Otherwise, you’re visiting some nodes too soon because there could be a shorter path with more nodes than the one you took with the breadth first search.
Anyway, I got the same issue as @lilian_cartellier: I pass the “Large number of stages” test in IDE but fail it during validation and I don’t know why…
Edit: My bad, I forgot to convert degrees to radians… Though I’m now surprised everything else works with wrong distances 
32 Likes
I just made a A* in C++ that pass all the tests so you can keep improving your code ^^
Ok, thank you ! I’m starting to run out of improvements ideas though, but I suppose I can come up with a good path size beyond which you must stop searching ^^
Wow thank you NewboO for the degrees/radians tip!
I did the same mistake and was starting to get mad 
3 Likes
Is this puzzle broken or is it only me? I’m getting no output(every test fails, even with straightforward writing out.txt from puzzle statement) and when i chose language i get empty IDE.
Big edit: Whoops I was a fool, the puzzle is working even if it’s true that there is empty code in the IDE and that there is no color syntax.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string START;
getline(cin, START);
cerr<<START<<endl;
return 0;
}
With that exemple, it do print output.
Edit: problem solved.
Hi,
Should be fixed now.
1 Like
Thank you for a tip! Got 85% because of this.
But tests passing are super confusing.
1 Like
Your distance computation is likely wrong. I had the same problem (and found the same solution as you did), but after fixing the distance computation everything worked.
Check your lats and lons! That was my problem…
1 Like
Hi!
When solving found an error as previous colleagues.
Error in the problem “Large number of stages”
A more detailed analysis showed a more optimal way.
In response CodeGame the path:
"Einstein
Rene Cassin
Chene des Anglais
La Coulee
Bertrand
Route de la Chapelle
Bout des Paves
Vallee
Pont du Cens
Foret
La Close
Berlioz
Rennes - Longchamp
Americains
Rond-Point de Rennes
Le Goffic
Bruneau
Bel Air
St-Stanislas
Talensac
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 "
Where is the way:
"Commerce
Hotel Dieu
Aime Delrue
Vincent Gache
Wattignies
Mangin
Pirmil "
Optimally pass:
"Commerce
Pirmil "
Resulted in calculation and map points. http://joxi.ru/gmv7y5kh0k0z2a
I can not right do calculation? But on the map can be seen that the shorter way - directly.
You can’t do Commerce -> Pirmil, because this link simply doesn’t exist. It seems you missed the fact this is a directed graph so even if Pirmil -> Commerce do exist, it doesn’t mean the other way do too.
12 Likes
I did not read properly working conditions.
“Each line represents a one-directional route running from the first identifier to the second.”
one-directional …
6 Likes
My “Large Number of Stages” is passing in the IDE but failing during validation. I have no idea what the error is. Any suggestions?
I have the same problem, with the “Large Number of Stages.”
There are many strange things in the input file for this test. For instance the Pirmil -> Commerce link exists but seems improbable when you actually look at the map. I found currently a total of three strange links by sheer luck:
-- StopArea:PIRM StopArea:COMM
-- StopArea:LILA StopArea:PTON
-- StopArea:RPBL StopArea:PIRM
Maybe it’s possible that the large test is biased by such shortcuts?
I’ve got the same problem. No idea what’s going on… I’m fairly sure that my implementation is correct. And I don’t think the solution is too slow either.
Edit: Well, thanks to another post, I checked my distance function and it turns out I didn’t convert the latitude/longitude to radians properly. I copied the distance function from the Defibrillators puzzle, but in my solution for that puzzle the conversion happened somewhere else.
I have a similar issue to most other commenters. The IDE tests report no issue even if I treat lattitude and logitude as cartesian coordinates. At the same time I get failure on the fourth test / 85% when I calculate the distance in this way. If I switch to radians and computing in the prescribed formula I fail the last test (84%) - again only on verification.
auto x = (long_b - long_a) * cos((lat_a + lat_b) / 2);
auto y = lat_b - lat_a;
return sqrt(x * x + y * y) * 6371;Pffftt… input is in degrees, calculation given is in radians… and that matters only in the submitted test results?? Mean, just mean.
4 Likes