3个水桶等分8升水

[likebeta]

有三个容积分别是3升、5升和8升的水桶，其中容积为8升的水桶中装满了水，容积为3升和容积为5升的水桶是空的。三个水桶都没有体积刻度，现在需要将大水桶中的8升水等分成两份，每份都是4升水，附加条件是只能使用另外两个空水桶，不能借助其他辅助容器。

这个问题刚毕业校招的时候就遇到过， 当时是作为智力题的形式出现的。人脑运算很容易找到一种答案，但是答案不是唯一的，我们可以用穷举法来找出所有的解法。

分析

求解这个问题的本质就是对状态进行穷举搜索。状态搜索的结果通常是一颗状态树。根节点为初始状态，叶子节点是最终状态或者不可达的中间状态。最终的答案就是根节点到达叶子节点路径。状态转换是由各种倒水动作驱动的，我们只要对状态和动作抽象数学模型， 然后驱动状态不断变化，最终到达最终状态或者不可达中间态。

桶状态模型

我们可以把桶排列， 然后用数组抽象3个桶的状态。假设分别按照3升， 5升和8升放置，那么初始状态就是[0, 0, 8]，终止状态就是[0, 4, 4]。例如从2号桶(8升)倒入5升水到1号桶(5升), 状态将变为[0, 5, 3]。

倒水动作模型

倒水的动作驱动状态的变换。由于没有桶没有刻度，倒水的行为需要根据倒出桶(src)和倒入桶(dest)当前的储水量来确定。一个倒出动作需要3个属性来表示：倒入桶src,， 倒出桶dest和倒水量(water)。我们可以使用三元组来抽象倒水动作{src, dest, water}。

组合模型

桶状态是个静止状态， 经过倒水动作转换成另一个新的桶状态。我们将桶状态和倒水动作组合就可以表示完整的状态转换。

剪枝

我们可以使用双层循环枚举从一个状态可能发生的所有倒水动作。很明显，根据当前桶的状态很多动作是不可能发生的， 可以直接忽略此种状态转换分支。

深度优先搜索会遇到环路，我们需要在搜索的过程中做个状态记录， 当遇到重复状态的时候可以直接舍弃该分支， 从而通过剪枝达到快速收敛。

实现

#!/usr/bin/env python
# -*- coding=utf-8 -*-

# Author: likebeta <ixxoo.me@gmail.com>
# Create: 2016-08-01

import copy


class Bucket(object):
    def __init__(self, capacity, water=0):
        self.capacity = capacity
        self.water = water

    def __eq__(self, other):
        return self.capacity == other.capacity and self.water == other.water

    def __ne__(self, other):
        return not self.__eq__(other)

    def is_empty(self):
        return self.water == 0

    def is_full(self):
        return self.capacity == self.water

    def dump_in(self, water):
        assert self.water + water <= self.capacity
        self.water += water

    def dump_out(self, water):
        assert self.water >= water
        self.water -= water

    def __str__(self):
        return str(self.water)

    __repr__ = __str__


class Action(object):
    def __init__(self, src, dest, water):
        self.src = src
        self.dest = dest
        self.water = water


class State(object):
    def __init__(self, bucket_list, action):
        self.bucket_list = copy.deepcopy(bucket_list)
        self.action = copy.deepcopy(action)

    def do_dump(self):
        self.bucket_list[self.action.src].dump_out(self.action.water)
        self.bucket_list[self.action.dest].dump_in(self.action.water)

    def __eq__(self, other):
        for bt_now, bt_end in zip(self.bucket_list, other.bucket_list):
            if bt_now != bt_end:
                return False
        return True

    def __ne__(self, other):
        return not self.__eq__(other)


class Algorithm(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        assert len(start) == len(end)
        self.bucket_count = len(start)

    def search(self, stack=None):
        if stack is None:
            stack = [State(self.start, None)]
        curr = stack[-1]
        if self.is_finished(curr):
            self.print_result(stack)
            return
        for i in range(self.bucket_count):
            for j in range(self.bucket_count):
                self.do_action(stack, curr, i, j)

    def do_action(self, stack, current, i, j):
        new_state = self.dump_water(current.bucket_list, i, j)
        if new_state:
            if not self.is_processed_state(stack, new_state):
                stack.append(new_state)
                self.search(stack)
                stack.pop()

    def dump_water(self, bucket_list, i, j):
        if i != j:
            src, dest = bucket_list[i], bucket_list[j]
            if src.is_empty() or dest.is_full():
                return None
            water = dest.capacity - dest.water
            if water > src.water:
                water = src.water
            new_state = State(bucket_list, Action(i, j, water))
            new_state.do_dump()
            return new_state
        return None

    def is_finished(self, current):
        for bt_1, bt_2 in zip(self.end, current.bucket_list):
            if bt_1 != bt_2:
                return False
        return True

    def is_processed_state(self, stack, new_state):
        for one in stack:
            if one == new_state:
                return True
        return False

    def print_result(self, stack):
        print (u'需要%d步' % (len(stack) - 1)).encode('utf-8')
        for state in stack:
            if state.action:
                s = u'%d号倒入%d号%d升' % (state.action.src, state.action.dest, state.action.water)
            else:
                s = ''
            print (u'%s <=== %s' % (state.bucket_list, s)).encode('utf-8')
        print '\n'


if __name__ == '__main__':
    start = [Bucket(3), Bucket(5), Bucket(8, 8)]
    end = [Bucket(3), Bucket(5, 4), Bucket(8, 4)]
    alg = Algorithm(start, end)
    alg.search()

运行上面的程序， 可以看到一共有16种解法， 最快的方法需要7步。