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.
The grid is something like 15 x 30, meaning that if properly done, a BFS takes close to NO time (you could do 100 BFSs per seconds if you wanted).
1 Like
pardouin is absolutely right. You should not look for algorithm improvement but you should check the correctness of your implementation. This is why I suggested to look at Red Blob games web site for a reference implementation.
1 Like
You guys are absolutely right. After two days, this morning. when I was thinking about algorithm in general, I realized there is a bit difference between no-cycle and with-cycle BFS. With cycle. when you put neighbor node on queue. it might already be here. This is it. With an extra “AND” clause, I passed.
Thank you guys for the quick feedback. The warmth is what draws me here.
1 Like
Hey all, check out the story I made within the error stream of my code. I had a lot of fun making it, and I hope you like it too. Follow the instructions in the comments at the top of the code. Here is how to get to my code.
Follow me (Type Wings_of_Safety in search and click follow), find my solution by going to Solve It->Results->Learn from the best coders-> then select “Language:Java” and “CodinGamers you follow” Copy my code into your IDE and run it. It will spit out a semi randomized story as Kirk searches through the maze. (Though only one storyline follows Kirk.)
Follow the instructions in the comments at the top of the code.
Anyway, let me know what you think. Also, if you have suggestions on how to make my code cleaner or more efficient let me know. I used A* and found the nearest path point that had a question mark next to it.
I finally got it. It wasnt clear to me from instructions. C is not the ultimate destination. You have to move to C first and then back to T. So the solution for first test case is 7xRIGHT 7xLEFT.
