"""
分水：
有8升、5升、3升水桶各一个，开始只有8升水桶是满的，问如何分成2个4升水。
"""

import sys


def can_poor(state, x, y):
    """检查当前状态下，是否可以进行倒水操作
       可以倒水的条件：不能是同一个桶，源桶必须有水，目标桶必须未满
    """
    if x!=y and state[x]>0 and bullet_max[y] > state[y]:
        return True
    else:
        return False


def do_poor(state, x, y):
    """执行倒水操作
       返回操作后的状态
    """
    new_state = state[:]
    if x!=y and state[x]>0 and bullet_max[y] > state[y]:
        change = min(new_state[x], bullet_max[y]-new_state[y])
        new_state[x] -= change
        new_state[y] += change
    return new_state


def pour(bullet_list):
    """用递归法完成深度搜索"""
    global plancount
    cur_state = bullet_list[-1][:] # 当前状态
    for x in range(3):
        for y in range(3):
            # 用双重循环测试所有不同的倒水方法
            if can_poor(cur_state, x, y):
                new_state = do_poor(cur_state, x, y)
                if new_state not in check_list:
                    # 新的状态不能是以前出现过的
                    # 加入新的状态
                    check_list.append(new_state)
                    bullet_list.append(new_state)
                    act_list.append([x,y])

                    # 检查是否达到最终状态
                    if new_state == [4, 4, 0]:
                        plancount += 1
                        print("\n第{:d}方案, 共{:d}步".format(plancount, len(act_list)))
                        print("桶状态      操作")
                        for i in range(len(act_list)):
                            print(bullet_list[i], act_list[i][0]+1, '->', act_list[i][1]+1)
                        print(bullet_list[-1])
                    else:
                        pour(bullet_list)

                    # 恢复状态
                    check_list.pop()
                    bullet_list.pop()
                    act_list.pop()


if __name__ == '__main__':
    bullet_list = [] # 桶状态变化列表，保存从[8, 0, 0]到[4, 4, 0]的过程
    bullet_list.append([8, 0, 0])
    bullet_max = [8, 5, 3] # 三个桶的容量
    act_list = [] # 动作列表（源桶号，目标桶号）
    check_list = [] # 桶状态列表，保存已经出现的桶状态，以防止出现状态循环
    check_list.append([8, 0, 0])
    plancount = 0 # 方案数
    pour(bullet_list)