# Treasure Hunt in a Maze

##### December 14, 2023

## Problem #

Scenario: You are a treasure hunter exploring a maze filled with rooms and tunnels. The maze is represented as a graph, where nodes are rooms and edges are tunnels connecting them. Some rooms contain treasure chests, and some may have locked doors requiring specific keys. You can only move through unlocked doors and have a limited carrying capacity for keys.

Your Task: Design an algorithm to find the shortest path from the entrance to the room containing the main treasure, collecting all necessary keys along the way.

## Solution #

```
from collections import deque
class Room:
def __init__(self, id, is_treasure=False):
self.id = id
self.is_treasure = is_treasure
self.neighbors = []
self.keys = set()
class Maze:
def __init__(self, rooms):
self.rooms = {room.id: room for room in rooms}
def find_shortest_path(self, start_id, treasure_id, max_keys):
queue = deque([(start_id, set())])
visited = set()
shortest_path = None
while queue:
current_room, current_keys = queue.popleft()
visited.add(current_room)
if current_room == treasure_id:
shortest_path = (current_room, current_keys)
break
for neighbor in self.rooms[current_room].neighbors:
if neighbor not in visited:
needed_key = self.rooms[neighbor].keys - current_keys
if len(needed_key) <= max_keys:
new_keys = current_keys | needed_key
queue.append((neighbor, new_keys))
if shortest_path:
path_rooms = [self.rooms[room_id] for room_id, _ in shortest_path[1:]]
path_rooms.reverse()
return path_rooms, len(shortest_path[1])
else:
return None, -1
# Example usage
rooms = [
Room(1, True),
Room(2),
Room(3),
Room(4),
Room(5),
Room(6, True),
]
maze = Maze(rooms)
# Connect rooms with edges
rooms[0].neighbors.append(rooms[1])
rooms[1].neighbors.append(rooms[2])
rooms[1].neighbors.append(rooms[3])
rooms[2].neighbors.append(rooms[4])
rooms[2].keys.add("red_key")
rooms[3].neighbors.append(rooms[5])
rooms[3].keys.add("blue_key")
rooms[5].neighbors.append(rooms[0])
rooms[5].keys.add("green_key")
start_id, treasure_id = 0, 5
max_keys = 2
shortest_path, keys_used = maze.find_shortest_path(start_id, treasure_id, max_keys)
if shortest_path:
print(f"Shortest path to treasure: {shortest_path}")
print(f"Keys used: {keys_used}")
else:
print("Treasure cannot be reached with given constraints.")
```