It’s impossible to create an algorithm that finds a good path in any partially hidden graph.
I think the validators are good as they are, allowing you to try different heuristics.
Great puzzle. Unfortunately it is now being rendered useless by insidious timeouts. I can’t even start calculating a path to explore before a timeout is hit. Using C++, nothing fancy or stupid. Codingame need to take a look and fix whatever is broken!
I just checked my python solution, it still works fine, so a C++ solution should have way enough time.
Maybe you do something overcomplicated, basically there’s a first exploration phase when you have to chose your direction carefully, you can try several sorting methods and see what works fine.
Once you discover the target, you can use a better heuristic, as you know exactly where to go.
And once a full path that goes to the target and goes back to the starting point is discovered, check with a BFS that you have enough fuel, if it’s ok take that path, else explore a bit more.
1 Like
I reran my old c# code for this puzzle and it’s still passing all the tests without any timeout.
Problem in test case 3, please give me the ability to send the image error
You are free to post image here by using the dedicated button if needed…
there might be some default posting restrictions for new accounts. Anyway, @Khoi1603 feel free to copy paste the error message as text or explain the issue you’re encountering and what you’ve tried so far
Great puzzle!!! 
Thank you!!!
1 Like
I triggered the alarm to early on validator no. 6. I changed the bfs order from horizontal to vertical first and got 100%. Feels like i cheated, but i’m too lazy to fix my messy code 
- BFS to ‘?’
- if no ‘?’ found BFS to ‘C’
- if ‘T’ already hit (after no more ‘?’ available) BFS to ‘T’
Don’t forget, that you can cross ‘T’, ‘C’ and ‘.’
@VizGhar, @MCvin, I wonder how to implement “BFS to ‘?’” / “find the closer ‘?’, go in that direction”. I’m probably too dumb to grasp this idea.
So I use a simple DFS (as suggested by @RobHue in his comment) instead for maze exploration, which does maybe the same job in the end? And I use BFS (within explored area) only to calculate the shortest paths after ‘C’ gets found. All tests passed.
With DFS it’s not guaranteed to find shortest path. BFS applied to pathfinding ~= Dijkstra ~= Flood Fill
BFS:
- create queue / FIFO (Java = Queue / LinkedList) and put current position into it
-
while stack is not empty
- get item from queue
- check neighborhood (neighbor is ‘?’ = return success; neighbor is ‘.’ add neighbor to queue)
- update board properly so you won’t visit same place twice and you can always tell what action u used at starting position in order to get here
- if you have reached this point you haven’t found any ‘?’ -> you can’t reach any ?
You will most likely struggle a little bit. Maybe resolve more medium puzzles and come back here later? It was necessity for me. And don’t forget to debug print updated board so that you can see what is happening.
3 Likes
@VizGhar, thank you, sir, I think I can see it now! The piece of the puzzle I missed was that you do the BFS to find the path to the nearest neighbor of ‘?’ (and then go there). Although I already have full points for this puzzle, I guess I will come back and rewrite it, and hopefully enjoy a shorter & more efficient code.
Another way to do a BFS is by using 2 lists, current and next.
Initially, current contains only your starting node.
While current is not empty, do these steps:
empty next,
fill next with the unvisited neighboors of all nodes in current,
current = next.
2 Likes
@pardouin, yes, definitely. I’m actually using this variant right now. I think it is a bit longer than using a FIFO queue, OTOH it makes tracking the distance from root easy (and good readers already know when checking this distance is necessary ).
OK, so I did come back and did the rewrite to “pure BFS” (or “repeated + nested BFS-s”, to be exact), while trying 3 different variations of it. For those interested, here is a table that compares number of total steps necessary to complete the last levels. (Total computational time is not measured, therefore ignored.):
Algorithm
Level DFS+BFS BFS_A BFS_B BFS_C
6 312 248 248 134
7 492 262 262 262
8 348 264 264 264
The “DFS+BFS” is the original implementation as described in my 1st comment in here.
The “BFS_*” variants differ in the time when we search for the shortest path from C to T:
- A … whenever our next BFS gets to C (might be a bit confusing / random, right?)
- B … after there is no ‘?’ left (as suggested in comments above; the shortest path from C to T is guaranteed afterwards)
- C … after every move to the next cell neighboring ‘?’
YMMV, of course… Directions tested in this order: RIGHT, DOWN, LEFT, UP.
I hope I got it right. And yes, the code is a little bit leaner now (compared to DFS+BFS).
After I fully explored the maze, I was stuck on the BFS on test 3, 7, 8. All timeouts. Yes, I’m using Python. Any ideas?
The maze is quite small and Python is plenty fast enough for one BFS per cycle. I would look for a bug (more specifically an infinite loop) in the BFS. For instance, check that you do not explore more cells than there are in the maze. Another possibility is that you are not exploring the maze properly and you do not find the exit which makes your program bomb. You may want to check your implementation against one provided by https://www.redblobgames.com (the best site I have ever seen for explaining path finding algorithms)
1 Like
In a recent thread about a floodfill problem, a user got similar timeouts, it was not an infinite loop but he wasn’t marking the ‘already explored’ nodes early enough, leading to several explorations from the same node.
It must be something like that.
Thank you for your reply.
Sorry, I think I didn’t explain myself well enough. I use DFS to fully explore the maze, and return to entry( which means already traverse the whole tree). Then because of the timing bomb, BFS is needed for shortest path from entry to control room. That’s where I stuck on 3, 7, 8. After I read this forum, it appears this is the supposed solution, which means the problem is Python couldn’t generate BFS of that size fast enough. What I was wondering is if there is any way to speed up?
(actually I’ve already tried a few tricks myself, including keeping track of the route hoping to find shortest path without BFS - which turns fruitless, and a bi-direction BFS which I’m still debugging)
An awful amount of time was spent on this puzzle. Is this just me or anyone else feels the pain of using a slow language?
Thank you guys again for the quick response.