# -*- coding: utf-8 -*-
"""
Created on Wed Feb  5 19:25:09 2020

@author: Ahsan Rahim
"""


#Graph to be AutoGenerated
graph={}



def validStates(node):
    valid=[];
    s=list(node);
    for i in range(len(s)):
        s=list(node);
        if(i+1<len(s) and s[i]<='B' and s[i+1]=='-'):
            s[i] , s[i+1] = s[i+1],  s[i];
            valid.append("".join(s))
        elif (i+2<len(s) and s[i]<='B' and s[i+2]=='-'):
            s[i] , s[i+2] = s[i+2],  s[i];
            valid.append("".join(s))
        elif (i-1>=0 and s[i]>='Y' and s[i-1]=='-'):
            s[i] , s[i-1] = s[i-1],  s[i];
            valid.append("".join(s))
        elif (i-2>=0 and s[i]>='Y' and s[i-2]=='-'):
            s[i] , s[i-2] = s[i-2],  s[i];    
            valid.append("".join(s))
    return valid
    

        
def addVertex( vertexName):
    graph[vertexName]=[]


def addEdge( v1 , v2):
    if v1 not in graph:
        addVertex(v1);
    if v2 not in graph:
        addVertex(v2);
        
    graph[v1].append(v2);
    



def GenerateGraph(node):
    valid = validStates(node);
    if valid!= []:
        for v in valid:
            addEdge(node, v);
            GenerateGraph(v);
        
        
# Driver Code to generate Graph        
GenerateGraph("AB-YZ");
print("Auto Generated Graph \n ")
print(graph);     
print('\n')   

        





visited = [] # Array to keep track of visited nodes.
found=False
def dfs(node , goal ):
    global found
    if node not in visited:
        print(node)
        visited.append(node)
        if(node==goal):
            found=True;
        else:
            for neighbour in graph[node]:
                if(found!= True):
                    dfs( neighbour , goal)


print("DFS Traversal to goal \n ");

dfs("AB-YZ" , "YZ-AB")

print('\n')            










visited = [] # Array to keep track of visited nodes.


#Shortest Path Using DFS
found = False
def dfs(node , goal , shortest ):
    global found
    if(node==goal):
        shortest.extend([goal])
        found=True
        return shortest

    if node not in visited:
        visited.append(node)
        shortest.extend([node])
    
    
        for neighbour in graph[node]:
            temp= dfs( neighbour , goal, [])
            if(found== True):
               shortest.extend(temp)
               return shortest
            
print("Shortest Path Using DFS \n")            
print(*dfs('AB-YZ' , 'YZ-AB' , [] ) , sep ='\n')
print('\n')





queue = []     #Initialize a queue

def bfs( node , goal):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s) 
    if( s== goal):
        break;
    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("BFS Traversal to goal \n")
bfs('AB-YZ' , 'YZ-AB')






#Hard Coded Graph, written but not used!
graph1= {

'AB-YZ': ['A-BYZ', '-BAYZ'],
'A-BYZ': ['-ABYZ' , 'AYB-Z'],
'-BAYZ' : [],
'-ABYZ' : [],
'AYB-Z' :['AY-BZ', 'AYBZ-'],
'AYBZ-' : ['AY-ZB'],
'AY-ZB' : ['AYZ-B' , '-YAZB'],
'AYZ-B' : [],
'-YAZB' : ['Y-AZB'],
'Y-AZB' : ['YZA-B'],
'YZA-B' : ['YZ-AB'],
'AY-BZ' : ['-YABZ' , 'AYZB-'],
'-YABZ' : ['Y-ABZ'],
'Y-ABZ' : [],
'AYZB-' : ['AYZ-B'],
'YZ-AB' : []

}
