🦄 Moonlit Maze with Portals

Difficulty: Advanced Tags: graphs, bfs, grid, shortest-path, state-space Series: Algorithms I

Problem

In a mystical moonlit maze, magical portals allow instant teleportation between matching locations. Find the shortest path from Start to End while strategically using these one-time portals.

Given a 2D grid where: - 'S' = Start position - 'E' = End position - '.' = Empty walkable cell - '#' = Wall (impassable) - 'A'-'Z' = Portal letters (0-2 occurrences per letter)

Find the minimum number of steps to reach E from S. You can: - Move to adjacent cells (up, down, left, right) - costs 1 step - Teleport between matching portal letters - costs 1 step - Use each portal letter at most once (to prevent infinite loops)

Return -1 if reaching E is impossible.

Real-World Application

Portal-based pathfinding appears in: - Video games - teleportation mechanics, warp zones - Network routing - VPN tunnels, network shortcuts - Transportation systems - subway transfers, airport connections - State-space search - modeling complex transitions - Puzzle solvers - games with special moves or rules

Input

data = {
    'grid': List[str]  # 2D grid as list of strings
}

Output

int  # Minimum steps from S to E, or -1 if impossible

Constraints

• 1 ≤ rows, cols ≤ 200
• Exactly one 'S' and one 'E'
• Each portal letter A-Z appears 0, 1, or 2 times
• Each portal can teleport at most once

Examples

Example 1: Using Portal

Input:

S.#.
.A#.
.#.E
.A..

Output: 5

Explanation: - Path: S → down(1) → down(2) → right to A(3) → teleport to A(4) → right to E(5) - Total: 5 steps - Without portal: Would need to go around walls, taking more steps

Example 2: No Portal Needed

Input: SE

Output: 1

Explanation: - S and E are adjacent - Just move right: 1 step

Example 3: Impossible

Input: S#E

Output: -1

Explanation: - Wall blocks the only path - No portals available - Impossible to reach E

Example 4: Multiple Portals

Input:

S.A.
...B
B.A.
...E

Output: 3

Explanation: - Best path: S → down(1) → down(2) → down to E(3) - Portals not needed in this case - Direct path is shortest

What You'll Learn

• BFS for shortest path in grids
• State-space modeling (position + portal usage)
• Handling special transitions (teleportation)
• Preventing infinite loops in graph search

Why This Matters

This challenge combines: - Classic BFS pathfinding - State tracking beyond position - Complex neighbor generation - Real-world teleportation/shortcut mechanics

Starter Code

def challenge_function(data):
    """
    Find shortest path in grid with portals.

    Args:
        data: dict with key 'grid' - list of strings representing the maze

    Returns:
        int: minimum steps from S to E, or -1 if impossible
    """
    # Your implementation here
    pass