import copy


def find_solution(front, closed, method):
    if goal_state(front[0]):
        print('_GOAL_FOUND_')
        print(front[0])

    elif not front:
        print('_NO_SOLUTION_FOUND_')

    elif front[0] in closed:
        new_front = copy.deepcopy(front)
        new_front.pop(0)
        find_solution(new_front, closed, method)

    else:
        closed.append(front[0])
        front_copy = copy.deepcopy(front)
        front_children = expand_front(front_copy, method)
        closed_copy = copy.deepcopy(closed)
        find_solution(front_children, closed_copy, method)


def find_children(state):

    children = []

    right_state = copy.deepcopy(state)
    child_right = move_right(right_state)

    left_state = copy.deepcopy(state)
    child_left = move_left(left_state)

    eat_state = copy.deepcopy(state)
    child_eat = eat(eat_state)

    if not child_eat == state:
        children.append(child_eat)

    if not child_left == state:
        children.append(child_left)

    if not child_right == state:
        children.append(child_right)

    return children


def make_front(state):
    return [state]


def can_move_left(state):
    print("Move left state is:")
    print(not state[0] == ['p'])
    return not state[0] == ['p']


def can_move_right(state):
    print("Move right state is:")
    print(not state[len(state) - 1] == ['p'])
    return not state[len(state) - 1] == ['p']


def expand_front(front, method):
    if method == 'DFS':
        if front:
            print("Front:")
            for i in range(len(front)):
                print(front[i])
            node = front.pop(0)
            for child in find_children(node):
                front.insert(0, child)

    elif method == 'BFS':
        if front:
            print("Front:")
            for i in range(len(front)):
                print(front[i])
            node = front.pop(0)
            for child in find_children(node):
                front.append(child)
    """
    elif method= = 'BestFS':
    else: "other methods to be added"
    """
    return front


def can_eat(state):
    for i in range(len(state)):
        print("Eat state is:")
        print(state[i] == ['p', 'f'])
        if state[i] == ['p', 'f']:
            return 1


def move_left(state):
    if can_move_left(state):
        for i in range(len(state)):
            if state[i] == ['p']:
                print("Move left state")
                print(state[i])
                state[i].pop()  # pop() when we move
                print("Remove pac-man")
                print(state[i])
                state[i-1].insert(0, 'p')  # insert() to where we move
                print("Insert the new pac-man")
                print(state[i-1])
                return state
    else:
        return state


def move_right(state):
    if can_move_right(state):
        for i in range(len(state)):
            if state[i] == ['p']:
                print("Move right state")
                print(state[i])
                state[i].pop()  # pop() when we move
                print("Remove pac-man")
                print(state[i])
                state[i+1].insert(0, 'p')  # insert(0, 'p') to where we move
                print("Insert the new pac-man")
                print(state[i - 1])
                return state
    else:
        return state


def eat(state):
    if can_eat(state):
        for i in range(len(state)):
            if state[i] == ['p', 'f']:
                state[i].pop()
                return state
    else:
        return state


def goal_state(state):
    print("Goal state length:")
    print(len(state))
    for i in range(len(state)):
        if state[i] == ['f']:
            return 0
    return 1


def main():
    initial_state = [['p', 'f'], ['f'], ['f'], []]
    method = "DFS"
    print('____BEGIN__SEARCHING____')
    find_solution(make_front(initial_state), [], method)


if __name__ == "__main__":
    main()