Don’t bother with A*. A good old breadth-first search does the trick, in all phases of the algorithm, with variations (e.g. what cells are considered safe, whether you compute the distance as well as the path).
3 Likes
Hi all. It seems to me that even if Kirk take the shortest path go come back to start, the 6th validation test (after sending the result) fail because the alarm is raised to early
Hum ok I think I know what happend. My return path is not the real shortest. There should be a difference of 2 or 3 by taking another way … The fact is that I cannot take this shortest path since I didn’t discovered it before finding the command room (bad luck) … 
Is it necessary to explore the whole maze to be sure to know the best return path and pass the validators ??? (or just have some luck)
1 Like
Yes my code explore all the map before touching the goal. Example : https://www.codingame.com/replay/solo/65908884
I finally passed the validators, just by switching in one function of my code (called GetPossibleNextPoints) so when choosing the better next position for moving, “up” and “down” are choosen before “left” and “right”. Now the mass is explored by another way (upper part first), and the discovered return path is the shortest one according to the validator configuration.
before the change : https://www.codingame.com/replay/solo/65917202
after the change : https://www.codingame.com/replay/solo/65917057
1 Like
That doesn’t sound like the right way to do it. Your code would probably fail if the last puzzle was just turned 90 degrees.
Your previous algorithm sounds much better. All you had to do to make it work was counting the distance from the Control room to the Teleport (with a simple BFS, as explained above) and keep exploring until you find a satisfying return path.
a simple BFS, what is this?
nevermind.forget it ^^
I passed 100% and the strategy is the same 3 stage format as Deefstes.
When I first submitted, one of the validation tests did not pass and I realised it was a L/R mirror of the IDE test case. What I did was to reverse the direction of my for loops, from (0 <= i < C) to (C > i >= 0), so I could troubleshoot the problem in the IDE.
1 Like
Hi there,
I’m trying to follow the same steps, but when I tried to use a basic BSP for exploring, I always get a timeout and I don’t know if this may be caused because my algorithm is not right or because I’m spending lot of time updating the grid or accessing info… Anybody has hit this issue??
I’m thinking about the time updating the grid because in the example 3 (empty grid) I only have 25 steps before the program told me that I have exceed the time…which doesn’t seems like a waste of time…
Thanks!
man, i completely coded up a right hand rule maze traversal… it works great, but no way to solve the long ones or the ones that with cycles. guess ill code up that A* after all!
If the problem had a lower time resolution or a larger field this search breadth-first could be a bad choice, even not need it is always good to optimize …
I’m just writing this to point out the differences between BFS and DFS here. To avoid confusions in using them.
Using BFS would mean that the robot or character in this case would have to teleport around on the map on each node he put in his queue.
The solution to this is actually a DFS where the character searches a path in a direction until it reaches some dead end and go back to the last branch point in the labyrinth… etc
Otherwhise in the case of BFS it would consume to much fuel to go back to the last unvisited node again.
See http://bryukh.com/labyrinth-algorithms/ for more information
5 Likes
After i sumbit my code everything works except #2, i always can calculate my way back except for this one, so there has to be kind of an issue. it only works if i dont calculate my way back, instead i have to use the path i too to get to the key
you can do it be rearranging the order so you have to check like this: right,left,down,up(or up,down)
Have folks been able to get Dijkstra’s to work in C/C++? I can’t be sure if I just need to optimize my code or if it’s the wrong approach.
I coded it in my pocket calculator, it’s a basic Dijkstra algo that should work in every language as is.
Thanks nicola1, In the meantime I gave BFS a shot and was able to complete… not sure how I could optimize Dijkstra more. Maybe a task for later on …
I can’t complete the last test, it timeouts on move 17.
I am using A* to calculate paths, only considering known ‘.’, ‘T’ and ‘C’ as valid pathways.
This is what I do:
- Look for the closest ‘?’
- Check if I have a valid path to it
- If so, keep moving towards it until it stops being a ‘?’.
- If not, look for the next-closest ‘?’
- Repeat that.
When I find the ‘C’ block, I keep checking if I have a valid path to it, and a path from it to ‘T’ that can be taken in the alarm time. If so, go to ‘C’ and go home.´
This works on all the others, spending a lot less than the 1200 fuel available, except on the last test. Kirk goes to (x, y) = (7, 11), which is a dead-end tunnel, with lots of ‘?’ around that can’t be accessed yet. The available ‘?’ require going back from the tunnel and go the other way, which means they’re quite far away. And so, the program gets a timeout while checking the closest ‘?’.
Does anyone have tips on this? I figure I either need to optimize the pathfinding function, so I can check more paths in the same time (which I’m not sure how to do), or implement some kind of logic to not check the path for a ‘?’ if there’s no path to a neighbouring ‘?’, but I’m not quite getting it to work.
Edit: Just submited, and apparently the exact same thing happens on the 2 last validators
Call me crazy but I have the same problems as many with the validators. So I reimplemented the validator. Took me a couple of hours.
Debugging right now.
Found it.