Feel free to send your feedback or ask some help here!
Test case n°6 is not the same in IDE and after sending the code. Thatâs not a big problem, but if my code works in the IDE and fails once sent, thatâs not easy to debug because the failing test case is not available in the IDEâŠ
2 Likes
None of them are the same, in any puzzle. It does make it harder to debug, but it is probably to avoid cheating: nothing would keep you from making a solution that only works for the tests and that you found âby handâ, if these were the same. (making something like "if I start on those coordinates, do âRIGHT-RIGHT-RIGHT-RIGHT-LEFT-LEFT-LEFT-LEFTâ)
2 Likes
Debugging this is a colossal #^$&@#$^$#. You need to give kirk less fuel. Sometimes the pathing messes up and he flips back and forth in place for 1200 turns and iâm just stuck there waiting for it to compile.
You can add a condition in the while(true) like âwhile(true && fuel >=0)â with a fuelâ; inside the loop.
and set the fuel you want before the loop. 300 for example (enough for most of the tests)
after 300 itérations, you will have a timeout exception. 
6 Likes
That guy really looks nothing like Kirk. At least give him the gold shirt!
7 Likes
What did you guys do, if you havenât found the control room yet? Simply giving a â?â as a target does not work, because maybe they are unreachable. I tried using valid random moves to find it, but thats no great solution (and it doesnt pass the tests). Any ideas?
Have you tried giving him the closest â?â as a target? Or the closest â?â ?
Hmm, how do I find it? I already have timing issues 
Using dijkstra or something would take way too long I guess.
I just used a BFS to find the nearest â?â when I didnât know where the goal was and âCâ and âTâ when the other conditions where appropriate. Hint: You may have to reveal the full map before activating the computer. If you donât you may not find the shortest path back depending on your move priorities.
1 Like
You can also use a recursive exploration algorithm, it uses more fuel though.
Mark where you are
For all 4 directions:
if it is possible to move (i.e. if itâs not a wall, and if itâs not the control room) and if itâs not marked
- move in that direction
- explore from the new position (recursive call).
- move in the opposite direction (i.e. go back).
That way you will always explore the whole map and come back to the point you landed.
All that youâll have to do next is to find the shortest path to the control room, and follow that path twice (BFS).
6 Likes
This might be the simplest answer. 
I definitly need to finish that puzzle when i got time.
When I first read the problem I said to myself - well, that shouldnât be too hard: just use D*(Lite) to navigate to the goal in unknown terrain and then back to start. But a few moments later I realized that just using D* is not enough here, at the minimum because there is no information about the goal node (thank you problem authors 
)
So the only realistic algorithms that came to my mind were these:
Full map discovery (based on the comment from Elliot)
- Discover the map by using recursion or greedy mapping where you always move to the closest unknown cell. You need to make sure not to step into the control room before discovering the whole map as you may not manage to come to start before the alarm goes off (this can be done by temporarily marking the control room as a wall)
- When the map is open, use any short-path algorithm to move to the control room and then the same algorithm to move to start
Pros:
- Only need 2 simple algorithms in sequential use
- No complex logic or conditionals
Cons:
- You need more fuel and the chance to run out of it is much larger (though this doesnât seem to be the case with the current test cases)
Partial map discovery
- As before, discover the map using recursion or greedy mapping. This time you need to stop when the target cell becomes visible (there may be a wall between your current position and the target cell)
- Use D* to navigate from the current location to the target cell considering unknown cells as free. Stop immediately before reaching the target cell - you donât want to get there unless you know there is a safe way back.
- Considering all unknown cells as walls, use D* (or other algorithm) to calculate the path from target to start. If the path is short enough then youâre done - just walk into the control room and then navigate back to start
- If the path is too long (which could happen if the undeterministic algorithm at step 1 didnât take you on the shortest path to the target) then use step 1 to discover the next unknown cell
- Repeat 3-5
Pros:
 - Uses less fuel. In most cases the solution can be found without fully discovering the map
Cons:
- Complex logic
- Usage of the more advanced D*(Lite) algorithm
Regardless of the algorithm, this problem may not always be solved because there are inputs for which the solution cannot be found by any algorithm or it can be found only by chance. Take this example (where the corner with C is not yet known):
. . #C
. ## .
. ## .
T . . .
If youâre given up to 11 fuel units or up to 5 moves to reach the start node after the alarm was triggered then there is no solution, no matter the algorithm.
If youâre given fuel for only 12-13 moves, this can only be achieved if you were lucky enough to start exploring the map by moving to the right (obviously by changing the map you may not be as lucky next time)
9 Likes
I donât understand the first test case? It says move in one direction⊠So i move right⊠nothing happens, I fail. Then I say, okay move right, and if you almost hit into the wall, move left⊠and so it continues. And still I fail. Whatâs the deal??
For that particular test case the solution is to move right until you get to the control room, then move left until you hit the teleport cell
Of course, left and right means left and right in the list of moves.
Hello, please use a monospace font for the Labyrinth made of ascii characters in the explanation
I did what you call âPartial Map Explorationâ but simpler, more specifically not using step2, I just BFS to nearest â?â untill I have a path from âCâ to âTâ that is less than the alarm, considering â?â as walls (because they are in the worst case).
3 Likes
This was a super fun challenge. I also used the approach that Agade used.
My game consisted of three stages.
STAGE 1 - EXPLORING:
Find the shortest path to the nearest â?â and move in that direction.
If the location of the control room is known, calculate the shortest path to it and the shortest path from the control room to the starting position. If the distance to the control room plus the distance to the starting position is greater than the amount of fuel available or if the distance from the control room to the starting position is greater than the alarm time, a shorter path must exist but is just not known yet. Keep exploring. If the control room and starting position can be reached within the fuel and alarm time constraints, go into STAGE 2.
STAGE 2 - GOING IN FOR THE KILL:
Calculate the shortest path to the control room and follow it. Once the control room is reached, go into STAGE 3.
STAGE 3 - HAULING ASS:
Calculate the shortest path to the starting position and follow it.
And it worked beautifully, first time, for all the test cases. Itâs a pity there werenât more test cases as I actually enjoyed watching Kirk go around the maze.
11 Likes
Hello,
Can you tell me what kind of method did you use to find the nearest node ?
Iâll try to implements the A* algorithm, is it a good idea ?
I think this algorithm can be used in the 3 stages of the game. Am I right ?
At the beginning I have tried the TrĂ©maux algorithm, but it doesânt seem to work in case of open environnements. Nevertheless itâs very powerfull in case of mazes with corridors of only one âunitâ width, i keep it in mind for the future.
Thank you for your answers