Untitled

def dfs_recursive(problem: SearchProblem, state, direction_stack: util.Stack):
    
    if (problem.isGoalState(state) == 1):
        return True
    
    a = problem.getSuccessors(state)
    
    a.reverse()
    
    check = False
   
    for i in a:
        #print("burdayız")
        #print(i)
        if i[0] not in problem._visited:
            #print(i)
            direction_stack.push(i)
            d = dfs_recursive(problem, i[0], direction_stack)
            check = check or d
            if not d:
                direction_stack.pop()
    return check

def depthFirstSearch(problem: SearchProblem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:

    print("Start:", problem.getStartState())
    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
    print("Start's successors:", problem.getSuccessors(problem.getStartState()))
    """
    "*** YOUR CODE HERE ***"
    
    direction_stack = util.Stack()
    start_state = problem.getStartState()
    print(start_state)
    dfs_recursive(problem, start_state, direction_stack)

    direction_list = list()
    
    while (not direction_stack.isEmpty() ):
        v = direction_stack.pop()
        print(v)
        direction_list.append(v[1])
        
    direction_list.reverse()
    #print(direction_list)
    print(len(direction_list))
    return direction_list
    
    
    """
    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
    a = problem.getSuccessors(problem.getStartState())
    
    for i in a:
        
    
    b = a[0][0]
    c = problem.getSuccessors(b)
    print("Start:", problem.getStartState())
    
    print("Start's successors:", problem.getSuccessors(problem.getStartState()))
    print("2nd successors:", c)
    util.raiseNotDefined()
    """



def breadthFirstSearch(problem: SearchProblem):
    """Search the shallowest nodes in the search tree first."""
    "*** YOUR CODE HERE ***"
    
    start_state = problem.getStartState()
    Q = util.Queue()
    Q.push((start_state, []))
    
    while (not Q.isEmpty()):
        v = Q.pop()
        
        if (problem.isGoalState(v[0])):
            return v[1]
        
        else:
            neigh = problem.getSuccessors(v[0])
            for i in neigh:
                if i[0] not in problem._visited:
                    next_list = v[1].copy()
                    next_list.append(i[1])
                    Q.push((i[0],next_list))
            
    
def uniformCostSearch(problem: SearchProblem):
    """Search the node of least total cost first."""
    "*** YOUR CODE HERE ***"
    start_state = problem.getStartState()
    Q = util.PriorityQueue()
    Q.push((start_state, [], 0), 0)
    
    while (not Q.isEmpty()):
        v = Q.pop()
        
        if (problem.isGoalState(v[0])):
            return v[1]
        
        else:
            neigh = problem.getSuccessors(v[0])
            for i in neigh:
                if i[0] not in problem._visited:
                    next_list = v[1].copy()
                    next_list.append(i[1])
                    next_pr = v[2] + i[2]
                    Q.push((i[0],next_list, next_pr), next_pr)