TAN Network puzzle discussion

Puzzles
#104

Just did this one, it felt nice to work on real data.

I was a bit disappointed that when I comment out the heuristic part of my priority evaluation (hence, transforming A* into Dijkstra), it still passes all validators.

But I guess it’s complicated to find the good constraints so that A* works and not Dijkstra.

#105

Thanks man, got stuck on this for so long, did not know why it was not working in submitted test.
this solved it for me :slight_smile:

#106

Hello, May i ask you some help? I managed to resolve the 6-tests. But when i tried to process the submits problems ony three of them are resolved. I dont know why. Is there differences between tests and submit tests that i have to know? Thank you. Lionel

#107

How stupid am i. It is written in the subject. The formula is for “radian”, but the datas are in degrees. I managed 4 of the 6 submits-tests. Still not find why i dont’ manage to solve the 5 and 6 submit-tests although i managed to solve tje 1,2,3,4,5,6 tests and the 1,2,3,4 submits tests.

#109

Am I the only one here who had issues with the second test case? It seems like there are not enough input lines because I kept getting NoSuchElementException.

edit: Good thing there is hasNextLine().

#110

Not only you.
Looking at the test case i see a problem.

It tells 2405 links but only 2403 in the input.

Really strange … I solved it 5 years ago and there was no problem until now

#111

That’s weird. I don’t remember us changing anything about this puzzle. I’ll investigate.

#112

Yes, found the same issue and tried getting around this by changing the value of M if the given N and M matched the faulty testcase’s values. Little did I know, test 5 has the exact same values of N and M, which tripped me up for a couple minutes.

#113

We did modify a test a few months ago. It’s possible we did a mistake. I’ve opened a ticket for the devs.

1 Like
#114

The issue has been fixed.

2 Likes
#115

For those who are still having this error : I read the forum and tried many thing, before realizing I didn’t need to convert lat and lon to degrees but to radians… It is written black on white but I misread the text.

2 Likes
#116

maybe that’s the solution sought here, but it seems to me that applying first breadth in that way, doesn’t always produce the shortest path. In the graph below, for example, path A is shorter, but has more stops and the first stop has a longer distance. It seems to me that DPS would the best solution, but it times out on this graph in the game IDE.

image

1 Like
#117

never mind; total distance, not incremental distance … duh !

#118

This puzzle is intended to be solved with Dijkstra’s algorithm. You can also use A* with a reasonable heuristics.
BFS will fail, best first search will fail, it’s normal.

If you timeout with Dijkstra/A*, it might be that you don’t use the good data structure.
You’re supposed to use a priority queue (usually implemented as a heap) to get your min in O(log n).
If you use a simpler structure that gives min in O(n), it will probably timeout.

1 Like
#119

Thank you for the tip (conversion to radian). I had the same issue and it works now perfectly well!

#120

Hello. I’m using a Dijkstra algorithm with priority queue (with Python code). It passes all the test cases, but fails with validators 05 (5 stops, 2 routes) and 06 (route impossible). It might come from a timeout issue. How can I get the min in O(log n) instead of O(n) ?

#121

What priority queue do you use?
You can use the module heapq, it’s not perfect (no update, you have to heappush updated nodes and discard obsolete ones instead) but it does the job.

#122

My code couldn’t pass validator 05 (5 stops, 2 routes). Then, I changed this part :

LIAISONS = dict()

for _ in range(m):

    if p1 not in LIAISONS:
        LIAISONS[p1] = dict()

    LIAISONS[p1][p2] = calculate_distance(p1,p2)

by this (which is doing the exact same thing) :

from collections import defaultdict

def create_dict():
    return dict()

LIAISONS = defaultdict(create_dict)

for _ in range(m):
    LIAISONS[p1][p2] = calculate_distance(p1,p2)

And now, my code passes validator 05… So, do you think it was a timeout issue ?

#124

@pardouin :
Oh, I’ve just found what was wrong. That was not related to my priority queue.

#125

I just got 100%! =D

but only by reading through this thread… I did three mistakes, I could never recognize by myself:

  1. I used degrees not radians
  2. wrong order of the coordinates (longditute, latidute)/(latidute, longditude) (got almost every test in the ide though… very misleading I think)
  3. I used pythons PriorityQueue. switching to heapq did the job for the last test. I never thought it could make such a difference

Thank you guys

2 Likes