Dark Labyrinth Dark Labyrinth

Do you remember the classic mission Open Labyrinth? Well, you once again find yourself inside a labyrinth, but the lights are out and you cannot see the full map. You have flashlight and know that all passages in the Labyrinth are directed along South-North and East-West lines. You don't yet know your position or the location of the exit. You must hurry as you cannot run forever.

This is a "multicall" mission and as such, your function will be called until you have solved the maze or run out of moves. For each iteration you see a part of the labyrinth in four directions (function input). You can see passages and where they have crossings and turns. If it’s in your range of vision, you’ll see the exit too. The visible zones are represented as a grid as a tuple of strings, where "X" is a wall, "." is a passage cell, "?" is unknown, "P" is player and "E" is the exit. Grids are represented as 2D rectangular arrays. The size is related to size of the visible zone.

For each iteration your function should return one or several actions as a string with directions. Actions are described as directions: "N" - North, "S" - South, "W" - West and "E" - East. For example: the string "NWS" describes a sequence of three moves. The walls are coated in a weird slime so you shouldn’t make a move that would have you walk into a wall. To make things interesting, you are limited to 250 moves (not iterations). You can use global variables between iterations.


For example on the image you can see the full labyrinth and that will be visible for player. And your function will receive:


Input: A visible part as a tuple of strings.

Output: An action or several actions as a string.



How it is used: This concept is pathfinding algorithm with search. It can be used to explore territory and make a map.

The labyrinth are surrounded by walls.
All passages are narrow (1 cell width)
3 < len(visible) ≤ 15
all(len(row) == len(visible[0]) for row in visible)