from collections import deque
actions = {
    "walk": lambda state: (state[0] + (1 if state[2] == "right" else -1)),
    "turn": lambda state: ("left" if state[2] == "right" else "right"),
    "push_box": lambda state: (state[0] + (1 if state[2] == "right" else -1)) if state[0] == state[1] else state[1],
    "climb_box": lambda state: "on_box" if state[0] == state[1] else state[2],
    "grab_banana": lambda state: "success" if state[2] == "on_box" else state
}
def monkey_banana_bfs(start):
    queue = deque([(start, [])])
    visited = set()
    while queue:
        state, path = queue.popleft()
        if state == "success":
            return path
        if state in visited:
            continue
        visited.add(state)
        for action, move in actions.items():
            if action == "walk":
                new_monkey_pos = move(state)
                new_state = (new_monkey_pos, state[1], state[2])
            elif action == "turn":
                new_direction = move(state)
                new_state = (state[0], state[1], new_direction)
            elif action == "push_box":
                new_box_pos = move(state)
                new_state = (state[0], new_box_pos, state[2])
            elif action == "climb_box":
                new_position = move(state)
                new_state = (state[0], state[1], new_position)
            elif action == "grab_banana":
                new_state = move(state)
            if new_state not in visited:
                queue.append((new_state, path + [action]))
    return "No solution"
start_state = (0, 2, "left")  # (Monkey at 0, Box at 2, Facing left)
solution = monkey_banana_bfs(start_state)
print("Solution path:", solution)