Dare2Solve
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:
The goal is to determine whether it is possible to measure exactly the target amount of water using the two jugs.
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
.
(curX, curY)
.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.
O(x * y)
to store the visited states in a hash set.
class Solution {
public:
pair<int, int> 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<string> operations = {"fill_x", "fill_y", "pour_x", "pour_y", "y_to_x", "x_to_y"};
queue<pair<int, int>> q;
unordered_set<string> 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<int, int> nextState = operateJug(operation, x, y, x1, y1);
q.push(nextState);
}
}
return false;
}
};
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
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<int[]> queue = new LinkedList<>();
Set<String> 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;
}
}
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;
};