My post was precisely about the fact that I got all the tests right, but only failed 2 validators (which I can’t see or debug…). Anyway, I finally found out that I needed to prevent “start” from being picked again, and this solved B and B’ 
You can start by reading the Goal section of the puzzle, there is a Wikipedia link to the A* algorithm which is of a great help at solving this puzzle
1 Like
Hello 
I’ve tried to understand the wikipedia page about the problem, but I have a little problem.
I don’t really understand what is the objective of the “openSet”. If we only give it the start how do we verify : “current := the node in openSet having the lowest fScore[] value”, the first time that it will go in the “while” loop, current will just be the start ?
Also, if we do this : “openSet.Remove(current)”, isn’t now the openSet empty ?
Thanks !
You remove “current” from the openSet, so it is empty at the first iteration, but from “current” you compute other things to put in your openSet.
You saw my published solution, so this is the equivalent :
d=qu.top(); // current := the node in openSet having the lowest fScore[] value
qu.pop(); // openSet.Remove(current)
The openSet is my priority_queue. You can see that for each node connected to current, I do a “qu.push”.
For example on this graph :
(forget about BFS/DFS and the orders below)
You start with “A” in your openSet.
First iteration, you work on “A”, you remove “A” from the openSet. The openSet is empty, but you add B, C and D in the openSet.
Second iteration, say you work on “C” because it has the lowest fScore. You remove “C” from the openset, the openSet contains B and D, and you add E and F.
Third iteration, your openSet contains B, D, E, F. Etc…
Indeed, the first time you enter the while loop, current will just be the start. You are also correct that we remove it so openSet is empty. But then, we populate it with openSet.add(neighbor) (on some conditions), before looping again.
Hello, just solved it. I have one comment regarding the example test cases - I missed a test that will cause a timeout when the priority queue is not properly used.
I don’t know if it is possible on codingame, but I would appreciate feedback when submitting saying what was the error - just a general info like: “timeout” or “wrong answer” - then it would be easier to know what is a general problem with a solution.
Interesting…for test case 4, using a C# PriorityQueue for my open list was resulting in node 6 being evaluated before node 4, meaning node 4 never got evaluated since the algorithm finds node 7 (the destination) attached to node 6. I was able to get the desired output, by using a regular List instead.