Feel free to send your feedback or ask for some help here!

# TAN Network puzzle discussion

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)

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?

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

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

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.

Thank you for a tip! Got 85% because of this.

But tests passing are super confusing.

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 `lat`

s and `lon`

s! That was my problemâ€¦

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.

I did not read properly working conditions.

â€śEach line represents a one-directional route running from the first identifier to the second.â€ť

one-directional â€¦

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.