from queue_code import Queue
from canoeNode import Node

def search(start,goal):
    #initialize the frontier using the initial state of the problem
    frontier = Queue()
    startNode = Node(start,None,None) #Since this is the start it doesn't have a parent or a move
    frontier.enqueue(startNode)
    
    #initialize the explored set to be empty
    explored = []
    
    #loop do
    while True:
        #if the frontier is empty
        if frontier.is_empty(): 
            #return failure
            print("Failure.  Empty Frontier")
            return None 
        
        #choose a leaf node and remove it from the frontier
        currentNode = frontier.dequeue()
        
        #if the node contains a goal state
        if currentNode.getValue()==goal:
            #return the corresponding solution
            path = []
            while currentNode.getMove()!=None:
                path.insert(0,currentNode.getMove())
                currentNode = findParentNode(explored,currentNode)
            #print("explored",len(explored))
            #print("frontier",frontier.size())
            return path
        
        #add the node to the explored set
        explored.append(currentNode)
        
        #expand the chosen node
        expansion = generateChildren(currentNode)

        
        #foreach resulting node in the expansion if not in  the explored set, add to the frontier
        for child in expansion:
            if not (alreadyExplored(explored,child)):
                frontier.enqueue(child)
        
                
                
def findParentNode(exSet,node):
    lookingFor = node.getParent()
    for others in exSet:
        if others.getValue()==lookingFor:
            return others
    print("There is an error.  This shouldn't ever happen")
    return None

def generateChildren(current):
    children = []
    
    currentState = current.getValue()
    currentNumbers = []
    for index in range(3):
        currentNumbers.append(int(currentState[index]))
    
    moves = ["One Analyst","One Hacker","Two Analysts","Two Hackers","One of Each"]
    overMath = [(-1,0,-1), (0,-1,-1),    (-2,0,-1),     (0,-2,-1),    (-1,-1,-1)]
    backMath = [(1,0,1),   (0,1,1),      (2,0,1),       (0,2,1),      (1,1,1)]
    
    if currentNumbers[2]==1:
        math = overMath
    else:
        math = backMath
    for index in range(5):
        childVal = []
        childString = ""
        for x in range(3):
            childVal.append(currentNumbers[x]+math[index][x])
            childString += str(childVal[x])
        #print("expanded to ",childString)
        if isLegal(childVal):
            children.append(Node(childString,currentState,moves[index]))
                            
    return children
                            
def isLegal(childVal):
    thisSideAnalysts = childVal[0]
    otherSideAnalysts = 3 - childVal[0]
    thisSideHackers = childVal[1]
    otherSideHackers = 3 - childVal[1]
    
    #Did we try to move more than we had?
    if thisSideAnalysts<0 or thisSideAnalysts>3 or thisSideHackers<0 or thisSideHackers>3:
        return False
    #Are there more hackers than non-zero analysts on this side
    if thisSideAnalysts>0 and thisSideHackers>thisSideAnalysts:
        #print("failure this side")
        return False
    
    #Are there more hackers than non-zero analysts on the other side
    if otherSideAnalysts>0 and otherSideHackers>otherSideAnalysts:
        #print("failure other side")
        return False
    #print("all good")
    return True
    
    
def alreadyExplored(exp,child):
    for node in exp:
        if node.getValue()==child.getValue():
            return True
    return False



res = search("331","000")
print(res)