二つのコップの問題をPythonで解いてみた

import copy

def main():
    cup_capacities = [3, 5]
    target = 1

    print("問題", cup_capacities, target)
    steps = solve_cup(cup_capacities, target)
    print("正解", steps)
    print("️手順再現")
    show_steps([0, 0], cup_capacities, steps)

def solve_cup(cup_capacities, target):
    moves = [
        "left_spill",
        "right_spill",
        "left_pour",
        "right_pour",
        "left_right",
        "right_left",
    ]
    state = [0, 0]
    states = [state]
    states_done = [state]
    steps = {}
    steps[str(state)] = []
    for i in range(20):
        states_new = []
        for state in states:
            if len(steps[str(state)]) < i:
                continue
            for step in moves:
                state_next = transition_state(state, cup_capacities, step)
                if state_next == []:
                    continue
                if not state_next in states_done:
                    steps[str(state_next)] = steps[str(state)][:]
                    steps[str(state_next)].append(step)
                    states_new.append(state_next)
                else:
                    pass
                if state_next[0] == target or state_next[1] == target:
                    return steps[str(state_next)]
        states_done += states_new
        states = states_new

def transition_state(state_previous, cup_capacities, step):
    state = copy.deepcopy(state_previous)
    if step == "left_spill":
        state[0] = 0
    elif step == "right_spill":
        state[1] = 0
    elif step == "left_pour":
        state[0] = cup_capacities[0]
    elif step == "right_pour":
        state[1] = cup_capacities[1]
    elif step == "left_right":
        if state[0] + state[1] > cup_capacities[1]:
            state[0] = state[0] + state[1] - cup_capacities[1]
            state[1] = cup_capacities[1]
        else:
            state[1] = state[0] + state[1]
            state[0] = 0
    elif step == "right_left":
        if state[0] + state[1] > cup_capacities[0]:
            state[1] = state[1] + state[0] - cup_capacities[0]
            state[0] = cup_capacities[0]
        else:
            state[0] = state[0] + state[1]
            state[1] = 0
    return state

def show_steps(state_from, cup_capacities, steps):
    state = copy.deepcopy(state_from)
    print("初期状態", state)
    for step in steps:
        print("移動", step)
        state = transition_state(state, cup_capacities, step)
        print("状態", state)
    print("回数", len(steps))

if __name__ == "__main__":
    main()