The Labyrinth - Puzzle discussion


#1

Feel free to send your feedback or ask some help here!


#2

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…


#3

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”)


#4

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.


#5

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. :wink:


#6

That guy really looks nothing like Kirk. At least give him the gold shirt!


#7

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?


#8

Have you tried giving him the closest ‘?’ as a target? Or the closest ‘?’ ?


#9

Hmm, how do I find it? I already have timing issues :stuck_out_tongue: Using dijkstra or something would take way too long I guess.


#10

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.


#11

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

  1. move in that direction
  2. explore from the new position (recursive call).
  3. 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).


#12

This might be the simplest answer. :slight_smile: I definitly need to finish that puzzle when i got time.


#13

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 :smile:)
So the only realistic algorithms that came to my mind were these:

Full map discovery (based on the comment from Elliot)

  1. 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)
  2. 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

  1. 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)
  2. 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.
  3. 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
  4. 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
  5. 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)


#14

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??


#15

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


#16

Of course, left and right means left and right in the list of moves.


#17

Hello, please use a monospace font for the Labyrinth made of ascii characters in the explanation :slight_smile:


#18

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).


#19

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.


#20

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