Water Jug Problem in Python

In this tutorial, we will learn how to solve the two-water jug problem in Python.

PROBLEM STATEMENT:

You are given two jugs with their capacities(in litres). Your task is to determine a series of pouring operations to measure a specific target amount of water.

GIVEN:

1. There is unlimited water available.
2. There is no marking on the jugs.
3. Both the jugs are empty in the initial stage.

OPERATIONS AVAILABLE:

1. Empty a jug completely.
2. Fill a jug completely.
3. Pour water from one jug to another jug.

APPROACH:

• Check whether the target is not exceeding the capacity of jugs.
  • Check if the target is a multiple of the greatest common divisor(GCD) of both the jug capacities.
    • Apply our algorithm.
  • Print -> This problem is not solvable with given inputs.
• Print -> This problem is not solvable with given inputs.

ALGORITHM:

1. Initially, both the jugs are empty.
2. Check if Jug1 is empty, then fill Jug1 with it’s maximum capacity.
3. Check if Jug2 is full, then empty jug2.
4. Pour the minimum of (Jug2_max_capacity – jug2_cuurent_water , jug1) from Jug1 to Jug2.
5. Repeat step 2-4 until either one of the jug water levels matches the target quantity.

PYTHON CODE:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def display_state(jug1, jug2):
    print(f"{'JUG 1: ':>11}{jug1:<6} | {'JUG 2: ':>12}{jug2}")

def pour_water(jug1, jug2, capacity1, capacity2):
    pour_amount = min(jug1, capacity2 - jug2)
    jug1 -= pour_amount
    jug2 += pour_amount
    return jug1, jug2

def water_jug_solution(capacity1, capacity2, target_amount):
    jug1 = 0
    jug2 = 0
    print(f"Jug 1 Capacity: {capacity1} | Jug 2 Capacity: {capacity2}")
    
    while jug1 != target_amount and jug2 != target_amount:
        if jug1 == 0:
            jug1 = capacity1
        elif jug2 == capacity2:
            jug2 = 0
        else:
            jug1, jug2 = pour_water(jug1, jug2, capacity1, capacity2)
        display_state(jug1, jug2)

first_jug = int(input("Enter the capacity of the first jug: "))
second_jug = int(input("Enter the capacity of the second jug: "))
target_amount = int(input("Enter the target liters of water: "))

if target_amount < first_jug or target_amount < second_jug:
    if target_amount % gcd(first_jug, second_jug) == 0:
        water_jug_solution(first_jug, second_jug, target_amount)
    else:
        print("This is not possible....")
else:
    print("This is not possible....")

OUTPUT:

Enter the capacity of the first jug: 5
Enter the capacity of the second jug: 8
Enter the target liters of water: 7

Jug 1 Capacity: 5 | Jug 2 Capacity: 8
    JUG 1: 5      |      JUG 2: 0
    JUG 1: 0      |      JUG 2: 5
    JUG 1: 5      |      JUG 2: 5
    JUG 1: 2      |      JUG 2: 8
    JUG 1: 2      |      JUG 2: 0
    JUG 1: 0      |      JUG 2: 2
    JUG 1: 5      |      JUG 2: 2
    JUG 1: 0      |      JUG 2: 7

We’ve successfully tackled the Water Jug problem in Python, simplifying the solution for better understanding. I hope you found the process enjoyable!