Hedge maze
Level: Advanced (score: 4)
Imagine you're trapped in a mysterious maze, much like the hedge mazes from Saltburn (poor Felix) or The Shining or Greek mythology. Just as for those unhappy fellows, the stakes for you are high - escape the maze or die grusomely (e.g., frozen, poisoned, or eaten).
The maze is like a puzzle, represented by a grid of cells, some of which are walls ('+') and others are open spaces ('.'). You begin at a specific cell -- the entrance -- and your goal is not just to navigate through the maze, but to escape it entirely.
You have limited movement options: you can go up, down, left, or right, but you can't pass through walls, and you can't step outside the maze, and you can't escape through the entrance. Your only hope is to find the closest exit - an empty cell located at the edge of the maze. That's your ticket to survival.
You must find the shortest path from the entrance to the nearest exit. If such a path exists, you need to know exactly how many steps it takes to reach safety.
Write a Python function that accepts two inputs...
- maze layout (a list of lists of strings. Each string is either a '+' (wall) or a '.' (open space)).
- entrance coordinates (a tuple of two integers, representing the row and column of the entrance cell).
...and returns the number of steps (as an integer) in the shortest path from the entrance to the nearest exit. If no such path exists, return -1.
Example 1
>>> from hedge_maze import hedge_maze
>>> maze = [
["+", "+", ".", "+"],
[".", ".", "." ,"+"],
["+", "+", "+", "."]
]
>>> entrance = (1, 2)
>>> hedge_maze(maze, entrance)
1
# Explanation: There are 3 exits in this maze at [1, 0], [0, 2], and [2, 3].
# Initially, you are at the entrance cell [1, 2].
# - You can reach [1, 0] by moving 2 steps left.
# - You can reach [0, 2] by moving 1 step up.
# It is impossible to reach [2, 3] from the entrance.
# Thus, the nearest exit is [0, 2], which is 1 step away.
Example 2
>>> from hedge_maze import hedge_maze
>>> maze = [
["+", "+", "+"],
["." ,"." ,"."],
["+", "+", "+"]
]
>>> entrance = (1, 0)
>>> hedge_maze(maze, entrance)
2
# Explanation: There is 1 exit in this maze at [1, 2].
# [1,0] does not count as an exit since it is the entrance cell.
# Initially, you are at the entrance cell [1, 0].
# - You can reach [1, 2] by moving 2 steps right.
# Thus, the nearest exit is [1, 2], which is 2 steps away.
Constraints:
- entrance will always be an empty cell ('.').
- You can't pass through walls, step outside the maze, or escape through the entrance.
Context
- The purpose of this bite is to explore the use of breadth-first search (BFS) to find the shortest path from the entrance to any edge of the maze (which is assumed to be the exit).
- BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, in this case the entrance to the maze) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
Tips
- There are different ways to solve this problem; one way is to use a "double-ended queue" from Python's collections module.
- Don't expect Jack to help you.
Keep calm and code in Python!