Cool puzzle, finally pass all the tests with BFS. 
I used A* which is a generalised Dijkstra. No problem, even in a slow language like Python.
BFS is sufficient to pass all tests.
Basically, here’s what I did:
Look for closest ‘?’ and proceed in that manner.
If ‘C’ is found try to go to ‘C’ (in case there’s no path, go to the ‘?’)
Once you’ve reached ‘C’ use BFS to reach ‘T’ fastest
I did this and did not pass all the tests because I did not always reveal the shortest path before I reached the control room (i.e. there were still question marks). Yet when I submitted I still got 100%. Lucky me.
Maybe I passed all tests because my order of directions
The idea for the game is quite nice, a variation of classic robotics exercise.
However, I did not like the way constraints and test cases are constructed (meaning, constraints are harsh but test cases are relaxed and don’t push constraints to the limit). It’s easy to construct a labyrinth that satisfies the constraints but can’t be reliably solved by any algorithm. You only open 5 ‘?’ at max per step. But max size of the field is 100x200 = 20000 cells. You only have fuel for 1200 steps, which means you can explore up to 6000 ‘?’ cells only. Ooops.
So, the constraints are misleading and for a while I thought that finding the control room requires some optimal strategy to sweep as many ‘?’ in one step as possible.
Another small thing: it’s not clear from the statement that control room may not be visible from the start. I was quite surprised that ‘C’ does not appear on the initial map.
1 Like
why i got timeout problems in case 3 7 8?
when i reach the control rooms in case 3 7 8, the program just crush. even the input provided by website is not correct, always miss the last row.pls help:tired_face:
here is my code
mod edit: don’t post full code, please
if already_found == 0 and already_arrival == 0:
path = shortest_path(kr,kc,map_,r,c,"?",["#"])
print(kr,kc,path,file = sys.stderr)
print(path[0])
elif already_found == 1 and already_arrival == 0:
path = shortest_path(kr,kc,map_,r,c,"C",["#","?"])
if path == None:
path = shortest_path(kr,kc,map_,r,c,"?",["#"])
print(kr,kc,path,file = sys.stderr)
print(path[0])
elif already_found == 1 and already_arrival == 1:
print(3,file = sys.stderr)
path = shortest_path(kr,kc,map_,r,c,"T",["#","?"])
print(kr,kc,path,file = sys.stderr)
print(path[0])I’m not a Python guy but it looks like there’s one combination of values you’re not handling… not sure if it’s a combination that can happen in real life but it’s worth checking.
Hey, can you explain that a bit deeper?
I actually have no idea to implement the “move in the opposite direction” case.
I have this so far:
def explore(x, y):
read_input()
x, y = kc, kr
if [x, y] not in explored:
explored.append([x, y])
print(explored, file=sys.stderr)
if is_free(x+1, y) and (x+1, y) not in explored:
print("RIGHT")
explore(x+1, y)
elif is_free(x-1, y) and (x-1, y) not in explored:
print("LEFT")
explore(x-1, y)
elif is_free(x, y+1) and (x, y+1) not in explored:
print("DOWN")
explore(x, y+1)
elif is_free(x, y-1) and (x, y-1) not in explored:
print("UP")
explore(x, y-1)
else:
move((x, y), explored.pop())Add a counter to break out of while loop, maybe start with 100 for first test case.
In Python 3, I get a random error where I only receive 14 input for row instead of 15. It blocks me on every test except the first one. I’m never reading an input outside of the pre-written code and it is the last line which is missing, not the first.
Hello
I think there is an issue with the detection of end of game when testing 
I suppose we could normally explore the maps with all the energy available, and only get KO if energy gets to 0 or command room is reached and returns isn’t made in time …
The energy is 1200,.but I get limited moves for all labyrinths before reaching the command room.
For 1 to 4, it’s OK because it’s the exact amount of moves to reach the command room and come back .
With the 5 to 8, the number of moves from the start are sometimes even not enough to reach the command room ?
For the 5 : I’ve only 105 moves (just enough to reach the command room).
For the 6 : only 60 moves.
For the 7 : only 34 moves !!!
And the 8 : only 41 !
Can you help me with this issue ?
A previous time, I’ve seen that the number of moves available was varying for one session to another for the same labyrinth test…
(I’ve submitted my “in progress solution” to see if there was a difference, but I don’t see a better % of resolution for the last labyrinths )
Thank you for your return !
ps : sorry for approximative english…
Hi
it is an historic puzzle of codingame and i played it in solo contest. so there should not be any issue
i have checked and have 1200 energy for exploration each time.
the only changing values (which are in inputs) are coordinates and the number of moves to come back to starting position.
Hi dwarfie
Thank you for the response.
After looking correctly, I’ve seen it was my fault
I will use for excuse that it was really really too hot these last days and I need to sleep…
I was simply making a move in a wall, so the number of steps was corresponding to the steps until Kirk smashed into a wall… I’ve killed him so much time, poor guy.
I will continue and make it work for at least 75% I think (50% for now, the “easy” part !) …
Sorry for my error !
Regards
1 Like
The second input example seems to have a problem.The start position of Kirk is not match the input. I can’t understand it.
The puzzle is really nice. But it is really hard to debug…
Would be better if some test cases were provided.
Very nice puzzle !
A simple BFS works. No graph class, no node class.
1 - find the closer ‘?’, go in that direction
2 - once ‘C’ is found, try to find the path between ‘C’ and ‘T’. If the path is not short enough repeat 1.
3 - once the path from ‘C’ to ‘T’ is ok, go to ‘C’ and then go back to ‘T’.
Much more simple than Don’t panic 2 in my opinion.
For debug I advice to visualize the ascii maze using
print(np.array2string(maze, formatter={'str_kind': lambda x: x}), file=sys.stderr)
it is much nicer 
2 Likes
can I ask about how to choose the direction when the same distance of different direction
If there are multiple unknown cells at the same distance, it doesn’t matter which one you choose. For example, you can just take the first one you find.
This puzzle needs more tests.
Solutions that do not cover all cases can be accepted as 100%. Mine did.