TAN Network puzzle discussion

Puzzles
#64

You could have seen that beforehand : just change the language in the solutions page.
At least that gave you some training in C :stuck_out_tongue:

#65

I did it with radians from start, tried to exchange latitude/longitude (just in case), but still getting the same result for 5th test as @slava_spamec when all other tests are passed.

1 Like
#66

ā€œEach line represents a one-directional routeā€ā€¦ I didnā€™t notice. Thank you so much!

BTW, I ported my C++ dijkstra to Python, because I wanted to parse the middle part using csv module.
Also my code uses cool earth-distance calculation (using acos).

1 Like
#67

Finally I passed 100%. I was stuck at validation #4 ā€œLarge Number of Stagesā€, then I realised it was the stupid mistake of not converting degrees to radians and that I swapped latitude/longitude around. :slight_smile:

So it was not a speed issue. My final solution used the A* algorithm, but my previous version of the code did far-from-optimal graph evaluations and would work too after fixing the above mistake.

#68

Hello everyone!

Iā€™m in a very strange situation: all tests pass, only one validator fails: ā€œSeveral stagesā€

Before correcting deg->rad, the ā€œLarge number of stagesā€ failed too (thanks NewboO).

Now, I would like to make sure itā€™s not a distance calculation issue. Here are the shortest distance I get for each test case, could someone tell me if these are correct, please?:

  • 1.497570
  • 0.335008
  • 0.000000
  • 2.302145
  • 13.362002
  • Impossible

If someone has any other idea or is experiencing the same situation, Iā€™m really interested.

Many thanks!

#69

Hi,

I pass all the tests and all the validators with my Python 3 code. Here are my testā€™s distances :

  • 1.4973071411893601
  • 0.3348154821405869
  • 0.0000000000000000
  • 2.3022053696674263
  • 13.362122315310147
  • IMPOSSIBLE

They are pretty close to yours. So the problem comes certainly from somewhere else. Try to time your code and see if it could be a time-out problem. Maybe you need to optimize your code or use another algorithm. The most popular algorithms for shortest path problem are Dijkstra or A*.

Good luck!

#70

I get:

1.4973071411888697
0.33481548214120577
0
2.3022053696676816
13.362122315309536
IMPOSSIBLE

My results are much closer to @bananaMixer than to you. I wonder if you might still have a slight calculation error somewhere and if perhaps the error is significant enough for one of the validators to be wrong.

  • danBhentschel
#71

Thank you all.

I replaced all floats by doubles and I get the same values as youā€¦ then itā€™s not a distance-calculation issue.

I checked for speed: it doesnā€™t exceed 30ms to complete any test. And it would be strange to pass ā€œLarge number of stagesā€ and not ā€œSeveral stagesā€, wouldnā€™t it?

Then my issue is probably elsewhere (maybe if two ways connect with the same number of moves, one of the two being shorter in distance). Anyway, thank you very much!

1 Like
#72

Hi again!

Iā€™m still working on my issue with ā€œSeveral stagesā€. I really donā€™t see where the problem might be: are names especially long? Are there special coordinates or special characters? Are UniqueID not always 4characters long?

Any help is welcome, thanks!

1 Like
#73

Hi there!
Do you have any suggestions, guys, how I can find the bug?
Iā€™ve implemented Dijkstra with PriorityQueue, so it seems to be fast enough for Java (approx 120ms in ā€œLarge number of stagesā€ for all steps - reading input, building maps and graph, finding shortest path).
It passes all the test cases, but fails in ā€œ5 stops, 2 routesā€. Iā€™ve double checked degees to radians conversion and order of longitudes and latitudes. It seems OK for me. So It sounds not quite easy to find bug without seeing input data.

P.S.: Oh, Iā€™ve just figured it out. I headed to bathroom after posting this message andā€¦ gotcha! Just like in the ā€œBack to the Futureā€ :slight_smile:

1 Like
#74

Thanks so much !
i was failing the ā€œLarge number of stagesā€ and could not understand why, i had the radians correctly figured out, the distance computation was correct.
The only thing i was missing for my A* to work was to correctly set the ā€˜gā€™ to 0 for the starting node.

#75

Hi Wingelin,
have you thought about the case when the current stop has no next stop (end of bus line) ?

#76

Hey slavaā€¦ literally exact same problem for me getting exact same output, using same language and algorithm, did you manage to fix this somehow?

#77

Thanks for the comments about converting to radians! I had everything correct except that. Thatā€™s pretty sneaky, but I suppose it is all there is you read it carefully.

#78

Same for me! thanks for ā€˜solutionā€™

#79

Is there any special case? I have rewritten code 10 times by now and always fail only last test case, i convert angles to radians and use dijkstra.

1 Like
#80

I pass every test case using Dijkstraā€™s algorithm, but only get 83% because of the ā€œ5 stops, 2 routesā€ validator. I think I either inadvertently hard coded something or am just missing something really subtle. Any suggestions would be greatly appreciated

1 Like
#81

Have you converted the angles in radians?

#82

Yes I have, using math.radians(x) in python.

#83

Possible problem: I make the graph so that each route is directed from A to B, but search for a path as if it is can go either way. Canā€™t believe I didnā€™t notice that before. Very easy fix. Now I get 100%

3 Likes