from collections import deque


def bfs_gsa(graph, start, goal, trace=False):
    frontier = deque([start])
    explored = set()
    while frontier:
        path = frontier.popleft()
        state = path[-1]
        if state == goal:
            return path
        if state in explored:
            continue
        explored.add(state)
        paths = [path + child for child in graph[state]]
        frontier.extend(paths)
        if trace:
            print(f"{path} -> {list(frontier)}")
            print(f"explored: {sorted(explored)}\n")


practice = {
    "S": ["a", "d", "G"],
    "a": ["b"],
    "d": ["b", "e"],
    "b": ["c", "e"],
    "c": ["G"],
    "e": ["G"],
    "G": [],
}

print("solution:", bfs_gsa(practice, "S", "G", True))