Challenge:
You are a programmer tasked with helping a lost explorer navigate their way out of a dense jungle. The explorer has a map with landmarks marked by letters (A, B, C, etc.). However, the map lacks directions or distances between these landmarks. The explorer can only move north, south, east, or west.
Your mission:
Write a program that takes the following input:
- A starting position (e.g., “B”)
- A target position (e.g., “F”)
- A dictionary containing the available moves from each landmark (e.g., {“A”: [“north”, “east”], “B”: [“south”, “west”]})
Your program should output:
- A list of directions (north, south, east, west) that guide the explorer from the starting position to the target position.
Bonus:
- If there are multiple paths, find the shortest path.
def navigate_jungle(start, target, map_data):
"""
This function takes a starting position, target position, and a dictionary of valid moves
and returns a list of directions to reach the target.
"""
# Initialize variables
visited = set() # Keep track of visited landmarks
queue = [(start, [])] # Queue to store possible paths
while queue:
# Get the next node from the queue
current_position, path = queue.pop(0)
visited.add(current_position)
# Check if we reached the target
if current_position == target:
return path
# Explore valid moves from the current position
for move in map_data[current_position]:
new_position = move
new_path = path + [move]
# Check if the new position is unvisited
if new_position not in visited:
queue.append((new_position, new_path))
# No path found
return None
# Example usage
map_data = {
"A": ["north", "east"],
"B": ["south", "west"],
"C": ["north", "east"],
"D": ["south", "west"],
"E": ["north"],
"F": ["south"],
}
start_position = "B"
target_position = "F"
path = navigate_jungle(start_position, target_position, map_data)
if path:
print("Directions:", path)
else:
print("No path found!")
This is a basic example, and you can modify it to handle additional features like:
- Implementing a backtracking algorithm to find the shortest path.
- Handling obstacles or one-way paths in the map.
- Visualizing the exploration process on a map.
OUTPUT:
Directions: [‘south’, ‘west’]