如何确定3个水壶问题中的可达状态？

让我们用这个小数据结构（一个由 3 个整数组成的数组）将水罐状态唯一地标识为所有 3 个水罐中的水量。对于本练习，我将使用 C/C++ 进行编码，但它可以轻松移植到任何编程语言。

struct JugState
{
    int jugs[3];
};

例如，如果第一个水罐有 4 个单位的水，第二个水罐有 5 个单位的水，第三个水罐有 3 个单位的水。那么我们可以有一个上面的 JugState {4,5,3}。

但考虑到水罐的固定容量分别为 12、8 和 5。我们可以轻松地得到壶状态的整数表示。上面的 {4,5,3} 配置可以很容易地用数字表示453。的壶配置{11,0,1}可以表示为1101。它不一定是十进制编码，但它使调试更容易。

我们可以拥有从 JugState 转换为“jug 状态索引”的辅助函数。

int getIndexFromJugState(const JugState& jugState)
{
    return jugState.jugs[0] * 100 + jugState.jugs[1] * 10 + jugState.jugs[2];
}

JugState getJugStateFromIndex(int index)
{
    int jug2 = index % 10;
    index = index / 10;

    int jug1 = index % 10;
    index = index / 10;

    int jug0 = index;
    return { jug0, jug1, jug2};
}

现在我们可以定义一个函数，将水从一个罐子转移到另一个罐子。此函数了解每个水壶的 12、8 和 5 单位容量。它采用初始“壶状态索引”和两个参数来指示水从何处移动（例如壶状态的0、1、2索引）作为参数。例如，如果您调用它，moveWater(453, 0, 1)基本上就是说“将第一个罐中的水转移到第二个罐中”。在这种情况下它应该返回，183因为第一个罐中只能倒入 3 个单位到第二个罐中。

int moveWater(int index, int srcJug, int dstJug)
{
    if (srcJug == dstJug)
    {
        return index;
    }

    JugState js = getJugStateFromIndex(index);

    // how much water is in the source jug
    int sourceAmount = js.jugs[srcJug];

    // how much water is in the destination jug
    int dstAmount = js.jugs[dstJug];

    // how much more water can the destination jug take
    int maxTransfer = (dstJug == 0) ? 12 : ((dstJug == 1) ? 8 : 5) - dstAmount;

    // how much to actually move
    int transfer = (sourceAmount >= maxTransfer) ? maxTransfer : sourceAmount;

    js.jugs[srcJug] -= transfer;
    js.jugs[dstJug] += transfer;

    return getIndexFromJugState(js);
}

现在我们可以把这个问题看成一个图。给定任何状态，例如{4,5,3}(index == 453)，我们想要测试是否可以转换到{7,1,4}(index == 714)。在任何给定状态下，可以进行 6 种有效转换。（即从 jug0->jug1、jug0->jug2、...、jug2->jug0 移水）。因此，我们可以使用 aset来跟踪我们访问过的节点索引，这样我们就不会无限递归。这种树遍历的最酷的部分是我们不需要构建一棵实际的树。

bool canTransitionExist(int startIndex, int endIndex, unordered_set<int>& visited)
{
    if (startIndex == endIndex)
    {
        return true;
    }

    // visit the start state
    visited.insert(startIndex);

    // there's 6 possible candidate states to transition to
    int candidates[6];
    candidates[0] = moveWater(startIndex, 0, 1);
    candidates[1] = moveWater(startIndex, 0, 2);
    candidates[2] = moveWater(startIndex, 1, 0);
    candidates[3] = moveWater(startIndex, 1, 2);
    candidates[4] = moveWater(startIndex, 2, 0);
    candidates[5] = moveWater(startIndex, 2, 1);

    // let's try visiting each one of these if we haven't visited before
    for (int i = 0; i < 6; i++)
    {
        // don't visit nodes we've seen before
        if (visited.count(candidates[i]) == 0)
        {
            bool result = canTransitionExist(candidates[i], endIndex, visited);
            if (result)
            {
                return true;
            }
        }
    }
    return false;
}

bool canTransitionExist(int startIndex, int endIndex)
{
    std::unordered_set<int> visited;
    return canTransitionExist(startIndex, endIndex, visited);
}

现在我们来介绍2个辅助函数。一个函数可以帮助我们用 12 个单位的水建立 53 个有效水罐状态的初始集合。此功能了解罐子的 12/8/5 限制。但您可以将任何您想要的目标状态量传递给它。

void getValidJugStates(int targetAmount, vector<int>& validStates)
{
    for (int i = 0; i <= 12; i++)
    {
        for (int j = 0; j <= 8; j++)
        {
            for (int k = 0; k <= 5; k++)
            {
                if ((i + j + k) == targetAmount)
                {
                    JugState js = { i,j,k };
                    validStates.push_back(getIndexFromJugState(js));
                }
            }
        }
    }
}

以及一个辅助函数，用于制作水罐状态的字符串表示形式：

std::string getStringFromIndex(int index)
{
    auto js = getJugStateFromIndex(index);
    std::string s = "{";
    s += std::to_string(js.jugs[0]) + "," + std::to_string(js.jugs[1]) +  "," + std::to_string(js.jugs[2]);
    s += "}";
    return s;
}

现在我们有足够的代码来编写 12 个水配置单元的所有 2756 种转换组合的测试。

int main()
{
    vector<int> validStates;

    const int capacityAmount = 12;
    getValidJugStates(capacityAmount, validStates);

    std::cout << "there are: " << validStates.size() << " initial starting states of jugs with " << capacityAmount << " units total\n";

    size_t testIndex = 0;

    for (size_t i = 0; i < validStates.size(); i++)
    {
        for (size_t j = 0; j < validStates.size(); j++)
        {
            if (i == j)
            {
                continue;
            }

            int start = validStates[i];
            int end = validStates[j];

            bool success = canTransitionExist(start, end);

            std::cout << "Test number " << testIndex << ": ";
            testIndex++;

            if (success)
            {
                std::cout << "valid path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
            else
            {
                std::cout << "there is not a path from " << getStringFromIndex(start) << " to " << getStringFromIndex(end) << endl;
            }
        }
    }

    return 0;
}

运行我们的代码（这是一个片段）...

...
...
Test number 1968: there is not a path from {7,5,0} to {9,2,1}
Test number 1969: valid path from {7,5,0} to {9,3,0}
Test number 1970: valid path from {7,5,0} to {10,0,2}
Test number 1971: there is not a path from {7,5,0} to {10,1,1}
Test number 1972: valid path from {7,5,0} to {10,2,0}
Test number 1973: valid path from {7,5,0} to {11,0,1}
Test number 1974: valid path from {7,5,0} to {11,1,0}
Test number 1975: valid path from {7,5,0} to {12,0,0}
Test number 1976: valid path from {8,0,4} to {0,7,5}
Test number 1977: valid path from {8,0,4} to {0,8,4}
Test number 1978: valid path from {8,0,4} to {1,6,5}
Test number 1979: there is not a path from {8,0,4} to {1,7,4}
Test number 1980: valid path from {8,0,4} to {1,8,3}
Test number 1981: valid path from {8,0,4} to {2,5,5}
Test number 1982: there is not a path from {8,0,4} to {2,6,4}
Test number 1983: there is not a path from {8,0,4} to {2,7,3}
...
...

您可以在此处获取完整列表：

https://github.com/jselbie/ Threejugproblem/blob/main/main.cpp