Como determinar os estados alcançáveis ​​no problema de 3 jarras de água?

Vamos identificar exclusivamente um estado de jarro como a quantidade de água em todos os 3 jarros com esta pequena estrutura de dados (uma matriz de 3 inteiros). Para este exercício, codificarei em C/C++, mas pode ser facilmente adaptado para qualquer linguagem de programação .

struct JugState
{
    int jugs[3];
};

Assim, por exemplo, se o primeiro jarro tiver 4 unidades de água, o segundo jarro tiver 5 e o terceiro jarro tiver 3. Então podemos ter um JugState acima de, {4,5,3}por exemplo.

Mas dado que os jarros têm uma capacidade fixa de 12, 8 e 5, respectivamente. Podemos facilmente ter uma representação inteira do estado do jarro. A configuração {4,5,3} acima pode ser facilmente representada com o número 453. Uma configuração de jarro {11,0,1}pode ser representada como 1101. Não precisa ser uma codificação decimal, mas facilita a depuração.

Podemos ter funções auxiliares que convertem de JugState para "índice de estado do jarro".

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};
}

Agora podemos definir uma função que move a água de um jarro para outro. Esta função está ciente das capacidades de 12,8 e 5 unidades de cada jarro. Toma como parâmetro o "índice de estado do jarro" inicial, e dois parâmetros para indicar de onde a água está sendo movida (por exemplo, 0,1,2 índices do JugState). Por exemplo, se você invocá-lo, moveWater(453, 0, 1)basicamente está dizendo "mova a água do primeiro jarro para o segundo jarro". Deve retornar neste caso, 183pois apenas 3 unidades do primeiro jarro podem ser despejadas no segundo.

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);
}

Agora podemos pensar neste problema como um gráfico. Dado qualquer estado como {4,5,3}(índice == 453) e queremos testar se é possível fazer a transição para {7,1,4}(índice == 714). Em qualquer estado, existem 6 transições válidas que podem ser feitas. (ou seja, mova a água de jug0->jug1, jug0->jug2, ..., jug2->jug0). Portanto, podemos apenas usar a setpara acompanhar quais índices de nó visitamos, para que não recursemos indefinidamente. A parte legal dessa travessia de árvore é que não precisamos construir uma árvore real.

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);
}

Agora vamos apresentar 2 funções auxiliares. Uma função para nos ajudar a construir esse conjunto inicial de 53 estados de jarros válidos com 12 unidades de água. Esta função está ciente dos limites de 12/8/5 nos jarros. Mas você pode passar qualquer valor do estado de destino que desejar.

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));
                }
            }
        }
    }
}

E uma função auxiliar para fazer uma representação em string do estado de um jarro:

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;
}

Agora temos o suficiente para codificar um teste para todas as 2.756 combinações de transições para as 12 unidades de configurações de água.

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;
}

Execute nosso código (aqui está um trecho)...

...
...
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}
...
...

Você pode obter a listagem completa aqui:

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