[Community Puzzle] A-star exercise

https://www.codingame.com/training/medium/a-star-exercise

Created by @aCat,validated by @eulerscheZahl,@JBM and @Stilgart.
If you have any issues, feel free to ping them.

12 posts were merged into an existing topic: [Puzzle of the Week] A-Star Exercise

Hello there,

Concerning puzzle"A-Star exercise" Coding Games and Programming Challenges to Code Better :

Some validator pass here (01, 02, 03) â€¦ but I have probleme with 04, 05 and 06 for example.
For validator 06, Iâ€™m at current node 1 and Node 2 is attended, but there no path form 1 to 2 (or 2 to 1) ???

(validator 06) I output :
0 5
1 5
3 6
(which is the end because 3 is the goal node)
But expected value are :
0 5
1 5
2 5
3 6

I couldâ€™nt see my error, I think line â€ś2 5â€ť should be removed.

When I send my code, nothing pass
At least simple test should be passed.

Does someone finished this puzzle ?

You have to output all the nodes the algorithm goes through (in order) until reaching the goal, not only the path from the start to the goal. Not sure but this might be your problem here.

hello,
I got 100% in ide test but only 33% in submission.
Any clue about the differences between ide and submission test ?
thx

100% this time, bad update of shorter distance of nodes when browsing another path! nice puzzle !

The given solution is
0 15
3 14
1 16
2 16
5 15
4 16
6 16
7 18
But as far as I understand, node id-3 is not connected with node id-1. Did I miss anything?
Thanks!

You launch the exploration from the node with the lowest priority (usually the priority is: exact distance from start + rough distance to end).
The node doesnâ€™t have to be connected with the node of the previous exploration

2 Likes

How do I order the nodes in the output? It seems that it is ordered neither by node ID (IDs go from 0 to 3 to 1 in the below example) nor by the f value (it goes from 15 to 14 to 16 to 15 in the below example).

0 15
3 14
1 16
2 16
5 15
4 16
6 16
7 18

You need to output the nodes in the same order that your code moved through them.

Meaning that A* algorithm would move from node 0 to node 3 then to node 1 etc.

2 Likes

Hi Yatech, are you saying that the puzzle requires a very specific algorithm, and excludes our coming up with our own solution?

Well, yes. Itâ€™s literally called A* exercise
The implementation of A* is up to you, but it needs to be A*.

3 Likes

Hello,
I got 100% on the test cases but missing out on validators 4 and 6. Do you have any hints or custom cases for me to check my code? Iâ€™m a little bit confused what iâ€ťm missing :-/

Validator 4 is the same as Test 4 except for input line 2. You may generate random numbers for that line to test your code.
Validator 6 is very different from Test 6; I think you have to check whether your code handles the case of â€śsame f-valueâ€ť correctly based on the rule stated in the puzzle statement.

1 Like

Thank you very much for the answer. I will look into it again.

Hi to all, and specially to @aCat (and @eulerscheZahl, @JBM & @Stilgart) for this good A* exercise !
â†’ As some others in this chat, iâ€™d to study (and discover) again the A* search path fundamentals â€¦

Thanks for this exercise !
bye, have sun, fun and Codinâ€™Games â€¦