import queue
from collections import deque


def BreadthFirstSearch(state, successor, isgoal):
    """accepts start state, Please do not change this function"""
    toDo = queue.Queue()
    toDo.put([state])
    explored = {state}
    while not toDo.empty():
        path = toDo.get()
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.put(path2)
    return "Error Path not found"


def DepthFirstSearch(state, successor, isgoal):
    """accepts start state, Please do not change this function"""
    toDo = deque()
    toDo.append([state])
    explored = {state}
    while toDo:
        path = toDo.pop()
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.append(path2)
    return "Error Path not found"


def A_StarSearch(state, successor, isgoal, h):
    """accepts start state, Please do not change this function"""
    toDo = [[state]]
    explored = {state}
    while toDo:
        toDo.sort(key=h)
        path = toDo.pop(0)
        current = path[-1]
        if isgoal(current):
            return path
        for next_state in successor(current):
            if next_state not in explored:
                explored.add(next_state)
                path2 = path + [next_state]
                toDo.append(path2)
    return "Error Path not found"