2 Social Part - YMonnier/AdvAlgoLP GitHub Wiki

Social Part

Triwizard Tournament (TT)

One competition in the TT is to get out of a labyrinth as quickly as possible.

Your task as the tournament supervisor is:

• given the labyrinth map, initial (current) positions of the three competing wizards and their relative speeds (in corridors per minute) predict which of them will reach the exit first.
• Assume that the magical wands used in the play are capable of guiding the wizards to the exit along a shortest possible path.

Summary

0. Execution
1. Implementation

Execution

To execute the labyrinth:

• git clone [email protected]:YMonnier/AdvAlgoLP.git
• cd AdvAlgoLP/Assignment2/Social
• manage your graph into the Supervisor.py
• python Supervisor.py

Implementation

To find the shortest path between the source of wizard and the exit,

I use Breadth Frist Search Algorithm by making the pi table(predecessor)

Python

		pi = {}
		Q = Queue()
		
		# Init
		pi[positionWizard] = -1
		Q.put(positionWizard)
		labyrinth[positionWizard].visited = True

		# Breadth First Search Algorithm
		while not Q.empty():
			node = Q.get()
			for n in labyrinth[node].neighbors:
				if not labyrinth[n.name].visited:
					labyrinth[n.name].visited = True
					pi[n.name] = node
					Q.put(n.name)
		
		# Path from wizard positon to exit
		p = exit # exit position
		path = [p]
		while p != -1:
			p = pi[p]
			path.insert(0, p)
		path = path[2:]