Water Jug Problem

from collections import deque

# Function to apply rules and generate new states

def generate_states(current, j1, j2):

    x, y = current

    states = []

    # Rule 1: Fill jug 1

    states.append((j1, y))

    # Rule 2: Fill jug 2

    states.append((x, j2))

    # Rule 3: Empty jug 1

    states.append((0, y))

    # Rule 4: Empty jug 2

    states.append((x, 0))

    # Rule 5: Transfer all water from jug 1 to jug 2

    if x + y <= j2:

        states.append((0, x + y))

    else:

        states.append((x - (j2 - y), j2))

    # Rule 6: Transfer all water from jug 2 to jug 1

    if x + y <= j1:

        states.append((x + y, 0))

    else:

        states.append((j1, y - (j1 - x)))

    return states

# BFS to solve the water jug problem

def solve_water_jug(j1, j2, goal):

    initial_state = (0, 0)

    visited = set()

    queue = deque([(initial_state, [])])  # Each element is (state, path)

    while queue:

        (current_state, path) = queue.popleft()

        x, y = current_state

        # Check if the goal is reached

        if x == goal or y == goal:

            return path + [current_state]

        # Skip already visited states

        if current_state in visited:

            continue

        visited.add(current_state)

        # Generate new states and add them to the queue

        for new_state in generate_states(current_state, j1, j2):

            if new_state not in visited:

                queue.append((new_state, path + [current_state]))

    return None  # If no solution is found

# Input capacity of jugs and goal

j1 = int(input("Capacity of jug 1: "))

j2 = int(input("Capacity of jug 2: "))

goal = int(input("Amount of water to be measured: "))

# Solve the problem

solution = solve_water_jug(j1, j2, goal)

# Print the solution path

if solution:

    print("Solution found:")

    for step in solution:

        print(f"Jug 1: {step[0]} liters, Jug 2: {step[1]} liters")

    print(f"Goal achieved: {solution[-1]}")

else:

    print("No solution exists.")