I recognise that you've probably got the gist from other answers, but it was a fun question and I felt like doing a little Python coding. This is my object-oriented approach. Indentation defines scope.
Graph Representation
The graph can easily be stored as a key, value dictionary where the key is the room id, and the value is an array of the rooms it leads to.
map = {
1:[5, 2],
2:[1, 3, 5],
3:[2, 4],
4:[3, 5, 6],
5:[2, 4, 1],
6:[4]
}
Agent Interface
First we should think about what information the agent should be able to learn from the environment, and the operations it should be able to perform. This will simplify thinking about the algorithm.
In this case the agent should be able to query the environment for the id of the room it is in, it should be able to get a count of the doors in the room it is in (note this is not the id's of the rooms the doors lead to!) and he should be able to move through a door by specifying a door index. Anything else an agent knows has to be figured out by the agent itself.
class AgentInterface(object):
def __init__(self, map, starting_room):
self.map = map
self.current_room = starting_room
def get_door_count(self):
return len(self.map[self.current_room])
def go_through_door(self, door):
result = self.current_room = self.map[self.current_room][door]
return result
Agent Knowledge
When the agent first enters the map it only knows the amount of doors in the room, and the id of the room it's currently in. I needed to create a structure that would store information the agent had learned such as which doors it had not been through, and where the doors lead to that is had been through.
This class represents the information about a single room. I chose to store the unvisited doors as a set and the visited doors as a dictionary, where the key is the door id and the value is the id of the room it leads to.
class RoomKnowledge(object):
def __init__(self, unvisited_door_count):
self.unvisited_doors = set(range(unvisited_door_count))
self.visited_doors = {}
Agent algorithm
Each time the agent enters a room it searches its knowledge
dictionary for information on the room. If there are no entries for
this room then it creates a new RoomKnowledge and adds this to it's
knowledge dictionary.
It checks to see if the current room is the target room, if so then
it returns.
If there are doors in this room we haven't visited, we go through the
door and store where it lead to. We then continue the loop.
If there weren't any unvisited doors, we backtrack through the rooms
we have visited to find one with unvisited doors.
The Agent class inherits from the AgentInterface class.
class Agent(AgentInterface):
def find_exit(self, exit_room_id):
knowledge = { }
room_history = [] # For display purposes only
history_stack = [] # Used when we need to backtrack if we've visited all the doors in the room
while True:
room_knowledge = knowledge.setdefault(self.current_room, RoomKnowledge(self.get_door_count()))
room_history.append(self.current_room)
if self.current_room==exit_room_id:
return room_history
if len(room_knowledge.unvisited_doors)==0:
# I have destination room id. I need door id:
door = find_key(room_knowledge.visited_doors, history_stack.pop())
self.go_through_door(door)
else:
history_stack.append(self.current_room)
# Enter the first unopened door:
opened_door = room_knowledge.unvisited_doors.pop()
room_knowledge.visited_doors[opened_door]=self.go_through_door(opened_door)
Supporting functions
I had to write a function that would find a key in a dictionary given a value, since when backtracking we know the id of the room we are trying to get to, but not which door to use to get to it.
def find_key(dictionary, value):
for key in dictionary:
if dictionary[key]==value:
return key
Testing
I tested all combinations of start/end position in the map given above. For each combination it prints out the visited rooms.
for start in range(1, 7):
for exit in range(1, 7):
print("start room: %d target room: %d"%(start,exit))
james_bond = Agent(map, start)
print(james_bond.find_exit(exit))
Notes
The backtracking isn't very efficient - in the worst case scenario it could go through every room to get to an adjacent room, but backtracking is fairly rare - in the above tests it only backtracks three times. I've avoided putting exception handling in to keep the code concise. Any comments on my Python appreciated :)
