3 JUG Problem Easy Python Code – The Three Water Jug Puzzle
These are the steps to approach this problem
- We have a capacity of jugs as 12,8 and 5
- Filling water in 12-liter jugA and keeping the other two empty
- The 12 liters are divided into 8 and 4 liters and 4 liters are poured into the jug B
- Now, the first jug A has 8 liters remaining
- The 8-liter water is further divided into 3 and 5 liter
- 3 liter is remaining in jug A and 5 is poured into the jug C having 5 liters as capacity
- Now, we pour 4 liters from jug C to the jug B
- Now the jug B is full
- Jug A has 3 liters and Jug C has 1 liter
- Water from Jug B (8 liters) is poured into Jug A making it 11 liters
- Water from Jug C is poured into Jug B
- 5 Litres from Jug A are poured into Jug C
- 6 liters are remaining in Jug A
- Now, the 5 liters from Jug C are poured into Jug B having only 1 liter and making it 6 liters
So, finally, we have Jug A having 6 liters and Jug B having 6 liters
PYTHON Code of 3 Water Jug Problem
capacity = (12,8,5)
x = capacity[0]
y = capacity[1]
z = capacity[2]
# to mark visited states
memory = {}
# store solution path
ans = []
def get_all_states(state):
# Let the 3 jugs be called a,b,c
a = state[0]
b = state[1]
c = state[2]
if(a==6 and b==6):
ans.append(state)
return True
# if current state is already visited earlier
if((a,b,c) in memory):
return False
memory[(a,b,c)] = 1
#empty jug a
if(a>0):
#empty a into b
if(a+b<=y):
if( get_all_states((0,a+b,c)) ):
ans.append(state)
return True
else:
if( get_all_states((a-(y-b), y, c)) ):
ans.append(state)
return True
#empty a into c
if(a+c<=z):
if( get_all_states((0,b,a+c)) ):
ans.append(state)
return True
else:
if( get_all_states((a-(z-c), b, z)) ):
ans.append(state)
return True
#empty jug b
if(b>0):
#empty b into a
if(a+b<=x):
if( get_all_states((a+b, 0, c)) ):
ans.append(state)
return True
else:
if( get_all_states((x, b-(x-a), c)) ):
ans.append(state)
return True
#empty b into c
if(b+c<=z):
if( get_all_states((a, 0, b+c)) ):
ans.append(state)
return True
else:
if( get_all_states((a, b-(z-c), z)) ):
ans.append(state)
return True
#empty jug c
if(c>0):
#empty c into a
if(a+c<=x):
if( get_all_states((a+c, b, 0)) ):
ans.append(state)
return True
else:
if( get_all_states((x, b, c-(x-a))) ):
ans.append(state)
return True
#empty c into b
if(b+c<=y):
if( get_all_states((a, b+c, 0)) ):
ans.append(state)
return True
else:
if( get_all_states((a, y, c-(y-b))) ):
ans.append(state)
return True
return False
initial_state = (12,0,0)
print("Starting work...\n")
get_all_states(initial_state)
ans.reverse()
for i in ans:
print(i) Output
- (12, 0, 0)
- (4, 8, 0)
- (0, 8, 4)
- (8, 0, 4)
- (8, 4, 0)
- (3, 4, 5)
- (3, 8, 1)
- (11, 0, 1)
- (11, 1, 0)
- (6, 1, 5)
- (6, 6, 0)
There are many problems dealing with different capacities.
Checkout: 2 JUG Problem with python code