Water JUG
from collections import deque def water_jug_problem(capacity_x, capacity_y, target): # Initialize the starting state (0, 0) initial_state = (0, 0) # Create a set to keep track of visited states visited = set() # Create a queue for Breadth-First Search queue = deque() queue.append(initial_state) while queue: current_state = queue.popleft() # If the target amount is reached, return the solution if current_state[0] == target or current_state[1] == target: return current_state x, y = current_state # Fill jug X if x < capacity_x: fill_x = (capacity_x, y) if fill_x not in visited: queue.append(fill_x) visited.add(fill_x) # Fill jug Y if y < capacity_y: fill_y = (x, capacity_y) if fill_y not in visited: queue.append(fill_y) visited.add(fill_y) # Pour water from jug X to jug Y if x > 0 and y < capacity_y: pour_x_to_y = (max(0, x - (capacity_y - y)), min(y + x, capacity_y)) if pour_x_to_y not in visited: queue.append(pour_x_to_y) visited.add(pour_x_to