Treasure Hunt in a Maze

Treasure Hunt in a Maze

December 14, 2023

medium

graph, BFS

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.")