365. Water and Jug Problem

Description

The problem involves using two jugs with capacities x and y to measure exactly a given target amount of water. You can perform the following operations on the jugs:

1. Fill one of the jugs completely.
2. Empty one of the jugs.
3. Pour water from one jug into another until one jug is empty or the other is full.

The goal is to determine whether it is possible to measure exactly the target amount of water using the two jugs.

Intuition

The problem boils down to determining if we can reach the target amount of water by performing a series of allowed operations. The operations effectively manipulate the state of water in each jug. By treating this as a graph traversal problem, we can systematically explore all possible states of the two jugs. The key observation is that this problem can be reduced to a greatest common divisor (GCD) problem in some cases, and we can check if the target is a multiple of the GCD of x and y.

Approach

1. Use a breadth-first search (BFS) algorithm to explore all possible states of the jugs.
2. Represent the amount of water in each jug as a state (curX, curY).
3. For each state, apply the allowed operations (filling, emptying, pouring between jugs) to generate new states.
4. Keep track of visited states to avoid cycles.
5. If we reach a state where either jug contains exactly the target amount of water, return true.
6. If all states are explored without reaching the target, return false.

Complexity

Time Complexity:

O(x * y), where x and y are the capacities of the two jugs. This is because, in the worst case, we might explore every possible state of the two jugs.

Space Complexity:

O(x * y) to store the visited states in a hash set.

Code

C++

class Solution {
public:
    pair operateJug(string action, int maxX, int maxY, int curX, int curY) {
        if (action == "fill_x") return {maxX, curY};
        if (action == "fill_y") return {curX, maxY};
        if (action == "pour_x") return {0, curY};
        if (action == "pour_y") return {curX, 0};
        if (action == "x_to_y") return {max(curX - min(maxY - curY, maxX), 0), min(curX + curY, maxY)};
        if (action == "y_to_x") return {min(curX + curY, maxX), max(curY - min(maxX - curX, maxY), 0)};
        return {0, 0};
    }

    bool canMeasureWater(int x, int y, int target) {
        if (x + y == target || x == target || y == target) {
            return true;
        }

        vector operations = {"fill_x", "fill_y", "pour_x", "pour_y", "y_to_x", "x_to_y"};
        queue> q;
        unordered_set visited;
        q.push({0, 0});

        while (!q.empty()) {
            auto [x1, y1] = q.front();
            q.pop();
            string key = to_string(x1) + "-" + to_string(y1);

            if (visited.count(key)) {
                continue;
            }

            if (x1 == target || y1 == target || x1 + y1 == target) {
                return true;
            }

            visited.insert(key);

            for (const auto& operation : operations) {
                pair nextState = operateJug(operation, x, y, x1, y1);
                q.push(nextState);
            }
        }
        return false;
    }
};

Python

class Solution:
    def operate_jug(self, action, maxX, maxY, curX, curY):
        if action == "fill_x":
            return maxX, curY
        elif action == "fill_y":
            return curX, maxY
        elif action == "pour_x":
            return 0, curY
        elif action == "pour_y":
            return curX, 0
        elif action == "x_to_y":
            return max(curX - min(maxY - curY, maxX), 0), min(curX + curY, maxY)
        elif action == "y_to_x":
            return min(curX + curY, maxX), max(curY - min(maxX - curX, maxY), 0)
        return 0, 0

    def canMeasureWater(self, x, y, target):
        if x + y == target or x == target or y == target:
            return True

        operations = ["fill_x", "fill_y", "pour_x", "pour_y", "y_to_x", "x_to_y"]
        queue = deque([(0, 0)])
        visited = set()

        while queue:
            x1, y1 = queue.popleft()

            if (x1, y1) in visited:
                continue

            if x1 == target or y1 == target or x1 + y1 == target:
                return True

            visited.add((x1, y1))

            for operation in operations:
                next_state = self.operate_jug(operation, x, y, x1, y1)
                queue.append(next_state)

        return False

Java

class Solution {
    public int[] operateJug(String action, int maxX, int maxY, int curX, int curY) {
        switch (action) {
            case "fill_x":
                return new int[] {maxX, curY};
            case "fill_y":
                return new int[] {curX, maxY};
            case "pour_x":
                return new int[] {0, curY};
            case "pour_y":
                return new int[] {curX, 0};
            case "x_to_y":
                return new int[] {Math.max(curX - Math.min(maxY - curY, maxX), 0), Math.min(curX + curY, maxY)};
            case "y_to_x":
                return new int[] {Math.min(curX + curY, maxX), Math.max(curY - Math.min(maxX - curX, maxY), 0)};
        }
        return new int[] {0, 0};
    }

    public boolean canMeasureWater(int x, int y, int target) {
        if (x + y == target || x == target || y == target) {
            return true;
        }

        String[] operations = {"fill_x", "fill_y", "pour_x", "pour_y", "y_to_x", "x_to_y"};
        Queue queue = new LinkedList<>();
        Set visited = new HashSet<>();

        queue.offer(new int[] {0, 0});

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int x1 = state[0], y1 = state[1];

            String currentState = x1 + "-" + y1;
            if (visited.contains(currentState)) {
                continue;
            }

            if (x1 == target || y1 == target || x1 + y1 == target) {
                return true;
            }

            visited.add(currentState);

            for (String operation : operations) {
                int[] next = operateJug(operation, x, y, x1, y1);
                queue.offer(next);
            }
        }

        return false;
    }
}

JavaScript

const operateJug = ({
    action,
    maxX,
    maxY,
    curX,
    curY,
}) => {
    switch (action) {
        case "fill_x":
            return [maxX, curY];
        case "fill_y":
            return [curX, maxY];
        case "pour_x":
            return [0, curY];
        case "pour_y":
            return [curX, 0];
        case "x_to_y":
            return [
                Math.max(curX - Math.min(maxY - curY, maxX), 0),
                Math.min(curX + curY, maxY)
            ];
        case "y_to_x":
            return [
                Math.min(curX + curY, maxX),
                Math.max(curY - Math.min(maxX - curX, maxY), 0)
            ]
    }

    return [0, 0];
}

var canMeasureWater = function (x, y, target) {

    if (x + y === target || x === target || y === target) {
        return true;
    }

    const operations = [
        "fill_x",
        "fill_y",
        "pour_x",
        "pour_y",
        "y_to_x",
        "x_to_y",
    ]

    const queue = [[0, 0]];
    const visited = {};
    while (queue.length > 0) {
        const [x1, y1] = queue.shift();
        console.log(visited);
        console.log(x1, y1);
        console.log(queue.length);
        if (visited[`${x1}-${y1}`]) {
            continue;
        }

        if (x1 === target || y1 === target || x1 + y1 === target) {
            return true
        }


        visited[`${x1}-${y1}`] = 1;


        queue.push(...operations.map((operation) => operateJug({
            action: operation,
            curX: x1,
            curY: y1,
            maxX: x,
            maxY: y,
        })));
    }

    return false;
};