[Community Puzzle] A-star exercise

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

Send your feedback or ask for help here!

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 :frowning:
At least simple test should be passed.

Does someone finished this puzzle ?
Please help.

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.

3 Likes

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 !

Hi, thanks for your puzzle. I would like to ask about Test case 4.
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 :slight_smile:
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.

:wave: Hi to all, and specially to @aCat (and @eulerscheZahl, @JBM & @Stilgart) for this good A* exercise :wink: !
→ As some others in this chat, i’d to study (and discover) again the A* search path fundamentals …

Thanks for this exercise :+1: !
:raised_hand:bye, have :sun_with_face: sun, :dark_sunglasses: fun and :keyboard: Codin’Games :wink: …

Hello, here all tests pass, but validators 2 & 3 fail (Small Graph B and Small Graph B’). Maybe some more tests can help figure out what’s wrong in my code?

I started as a gamer. So this site is perfect. The contests are mostly fun, my favorite is the recent one with the Fiverr collab(I like retro game aesthetic). Any advice on how to finish the current puzzle by A Cat? Thanks in advance

There should always be a forum topic on every puzzle on CodinGame, so you’re advised to find and read the previous discussion, which possibly includes some advice on solving the puzzle.

1 Like

Since those graphs are small, why don’t you try working it out by hand? Add debugging logging at various points to see where your code starts to deviate from what you got by hand.