[go: up one dir, main page]
Scribd
Upload
22 views3 pages

Water Jug Problem

The document presents a Python implementation of the Water Jug Problem using a breadth-first search (BFS) algorithm. It defines functions to find a solution path for filling two jugs to reach a target amount of water and to print the steps taken to achieve this. The main function interacts with the user to input jug capacities and the target amount, then displays the solution or indicates if no solution is possible.

Uploaded by

gayatri250904
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
22 views3 pages

Water Jug Problem

The document presents a Python implementation of the Water Jug Problem using a breadth-first search (BFS) algorithm. It defines functions to find a solution path for filling two jugs to reach a target amount of water and to print the steps taken to achieve this. The main function interacts with the user to input jug capacities and the target amount, then displays the solution or indicates if no solution is possible.

Uploaded by

gayatri250904
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Water Jug Problem

from collections import deque

def water_jug_bfs(c1, c2, target):

visited = set()

queue = deque([((0, 0), [])])

while queue:

(j1, j2), path = queue.popleft()

if (j1, j2) in visited:

continue

visited.add((j1, j2))

path = path + [(j1, j2)]

if j1 == target or j2 == target:

return path

moves = [

(c1, j2), # Fill Jug 1

(j1, c2), # Fill Jug 2

(0, j2), # Empty Jug 1

(j1, 0), # Empty Jug 2

(j1 - min(j1, c2 - j2), j2 + min(j1, c2 - j2)), # Jug1 → Jug2

(j1 + min(j2, c1 - j1), j2 - min(j2, c1 - j1)) # Jug2 → Jug1


]

for state in moves:

if state not in visited:

queue.append((state, path))

return None

def print_steps(path, target):

print(f"\nStep 0: {path[0]} (Start)")

for i in range(1, len(path)):

prev, curr = path[i-1], path[i]

action = ""

if curr[0] > prev[0] and curr[1] == prev[1]:

action = "Fill Jug 1"

elif curr[1] > prev[1] and curr[0] == prev[0]:

action = "Fill Jug 2"

elif curr[0] < prev[0] and curr[1] == prev[1]:

action = "Empty Jug 1"

elif curr[1] < prev[1] and curr[0] == prev[0]:

action = "Empty Jug 2"

elif curr[0] < prev[0] and curr[1] > prev[1]:

action = "Pour Jug 1 → Jug 2"

elif curr[1] < prev[1] and curr[0] > prev[0]:

action = "Pour Jug 2 → Jug 1"

if curr[0] == target or curr[1] == target:

action += f" (Target {target} liters reached)"

print(f"Step {i}: {curr}\n Action: {action}")

def main():

print("Water Jug Problem Solver\n------------------------")

c1 = int(input("Jug 1 capacity: "))


c2 = int(input("Jug 2 capacity: "))

target = int(input("Target amount: "))

result = water_jug_bfs(c1, c2, target)

if result:

print("\nSolution found!")

print_steps(result, target)

else:

print("\nNo solution possible.")

if _name_ == "_main_":

main()

OUTPUT :

You might also like