"""
When I read the specs for this project I immediately spotted a graph
theory problem, where the dungeon is the graph and each room within 
the dungeon is a node.  At that point I felt I had two choices: code 
it all out or use an existing/established library for graphs.  Since
this is not homework and in the "real world" reinventing the wheel is
frowned upon, I went with the Networkx Python library.

I created a Dungeon class that has attributes of an identity matrix 
and start/end rooms.  The class consists of a constructor and methods
for setting start/end nodes, validating the dungeon for a 3 node cycles,
validating the dungeon for rooms that have more than 6 adjacent rooms, 
and solving the escape route out of the dungeon.

Checking for the maximum number of adjacent rooms was a matter of 
examining each row of the identify matrix.

To check for 3 node cycles, the cycle_basis method from the Networkx
method was used.  Any resulting cycle that had 3 nodes was flagged.

The escape route was computed by using Dijkstra's algorithm, which 
was part of the Networkx library as well.  Since the adjacency matrix
supplied are even weights, it works out the same, but if the Dungeon
Master wanted to make rooms larger, and reflect those weights within
the adjacency matrix, the flexibility is there
Time complexity:  O(V^2), V = number of nodes/verticies/rooms
Space complexity: O(E*log E + V), where E = edges/paths, 
                  V = number of nodes/verticies/rooms

The test program tests various matricies that will yield a successful
exit of the dungeon and those that will fail due to not being up 
to the dungeon code.  The output results are:


Dungeon Created
Dungeon Created
Dungeon Created
Dungeon Created
Dungeon Has To Have At Least Two Rooms
Error: 3 Node Cycle
Invalid Dungeon
[0, 1, 2]
Too Many Adjacent Rooms
Invalid Dungeon
[0, 4, 5, 6, 7]

"""

import networkx as nx
import numpy as np


""" maximum adjacent nodes  """
CONST_MAX_PATHS = 6
""" minimum cycle """
CONST_MIN_CYCLE = 3

class Dungeon:
    """  Holds the graph """
    layout=[]  
    """ start node """
    start=0  
    """ end node """
    end=0  
    
    """ Constructor """
    def __init__(self,idMat):  
        try:
            if len(idMat) >= 2:
                self.layout=nx.from_numpy_matrix(idMat, create_using=nx.Graph()) 
                print "Dungeon Created"
            else:
                print "Dungeon Has To Have At Least Two Rooms"
        except:
            print "Invalid Dungeon Matrix"

    """ sets the start node/room """
    def setStart(self,s):  
        self.start =s
 
    """sets the end node/room """
    def setEnd(self,e):   
        self.end =e
    
    """  makes sure room does not have more than 6 adjacent nodes """
    def validateRoomCount(self):   
        for x in range(0, len(self.layout)):
            if len(self.layout[x]) > CONST_MAX_PATHS:
                print "Too Many Adjacent Rooms"
                return False
        return True
    
    """  makes sure room does not have 3 node cycles """
    def validateCycle(self):
        arr = nx.cycle_basis(self.layout)
        for row in arr:
            if len(row)==CONST_MIN_CYCLE:
                print "Error: 3 Node Cycle"
                return False
        return True
        
    """ prints the path to exit dungeon """
    def getOut(self):
        print nx.dijkstra_path(self.layout, self.start, self.end)

"""
Matrix A: used to test the case that a graph where 
A adjacent to B, B adjacent to C, and C adjacent to A 
is not allowed
"""

A = np.array([[0, 1, 1],
              [1, 0, 1],
              [1, 1, 0]])
              
    

"""
Matrix B: a valid matrix with no 3 node cycles
"""    
B = np.array([[0, 1, 0],
              [1, 0, 1],
              [0, 1, 0]])


"""
Matrix C: used to test the case that a graph containing a 
node with more than 6 adjacent nodes is not valid
""" 
C = np.array([[0,1,0,0,0,0,0,1],
              [1,0,1,0,0,0,0,0],
              [0,1,0,1,0,0,0,0],
              [0,0,1,0,1,0,0,0],
              [0,0,0,1,0,1,0,0],
              [0,0,0,0,1,0,1,0],
              [0,1,1,1,1,1,1,1],
              [1,0,0,0,0,0,1,0]
              ])
"""
Matrix D: valid matrix
"""     
    
D = np.array([[0,1,0,0,1,0,0,0],
              [1,0,1,0,0,0,0,0],
              [0,1,0,1,0,0,0,0],
              [0,0,1,0,1,0,0,0],
              [1,0,0,1,0,1,0,0],
              [0,0,0,0,1,0,1,0],
              [0,0,0,0,0,1,0,1],
              [0,0,0,0,0,0,1,0]
              ])

"""
Matrix E: Invalid 1 room matrix
"""     
    
E = np.array([[0]])

testCase1 = Dungeon(A)
testCase2 = Dungeon(B)
testCase3 = Dungeon(C)
testCase4 = Dungeon(D)
testCase5 = Dungeon(E)

"""
Setting start and end rooms/nodes
"""  
testCase1.setStart(0)
testCase2.setStart(0)
testCase3.setStart(0)
testCase4.setStart(0)

testCase1.setEnd(2)
testCase2.setEnd(2)
testCase3.setEnd(7)
testCase4.setEnd(7)

"""
Attempting to solve each dungeon
"""  


if testCase1.validateCycle()==True and testCase1.validateRoomCount()==True:
    testCase1.getOut()
else:
    print "Invalid Dungeon"

if testCase2.validateCycle()==True and testCase2.validateRoomCount()==True:
    testCase2.getOut()
else:
    print "Invalid Dungeon"    
    
if testCase3.validateRoomCount()==True and testCase3.validateCycle()==True:
    testCase3.getOut()
else:
    print "Invalid Dungeon"   
    
if testCase4.validateRoomCount()==True and testCase4.validateCycle()==True:
    testCase4.getOut()
else:
    print "Invalid Dungeon"  

import pip
installed_packages = pip.get_installed_distributions()
installed_packages_list = sorted(["%s==%s" % (i.key, i.version)
     for i in installed_packages])
print(installed_packages_list)