# Jug problem - 3 jugs

I have solved the jug problem with 3 jugs:

For jugs size A, B and C find the minimum number of steps to reach D, where D < max (A,B,C)

My Python 3 code is below. I am wondering if there are other ways, faster ways or more efficiency ways to compute the answer.

"""
Solving the "how many moves to get solution d for jugs size a, ,b, c
"""

"""Function make move"""
#Create list of visited solutions
listPrevSolutions = []
#Create correspnding list of number of steps to reach solution
listTotalSteps = []

list_index_steps = []

def MoveWater (jugMax,
jugState,
targetVol,
runningTotal,
previousSteps,
listLength):
global list_index_steps

listPosition = listLength

jugA_max = jugMax
jugB_max = jugMax
jugC_max = jugMax 

jugA_state = jugState
jugB_state = jugState
jugC_state = jugState

if jugA_state == targetVol or jugB_state == targetVol or jugC_state == targetVol:
print ("Target achieved in 1 step. Fill up a jug")
return True

#Move 1: move from A into B (if room) AND (if not state doesn't exist)
if jugA_state !=0:
if jugB_state < jugB_max:
#Empty A into B if room
if jugB_state + jugA_state <= jugB_max:
new_jugA_state, new_jugB_state = 0, jugB_state + jugA_state
else: #Empty as much of A into B
new_jugA_state, new_jugB_state = (jugA_state - (jugB_max-jugB_state)), jugB_max

new_jugC_state = jugC_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 2: move from A into C (if room) AND (if not state doesn't exist)
if jugA_state !=0:
if jugC_state < jugC_max:
#Empty A into C if room
if jugC_state + jugA_state <= jugC_max:
new_jugA_state, new_jugC_state = 0, jugC_state+ jugA_state
else: #Empty as much of A into C
new_jugA_state, new_jugC_state = (jugA_state - (jugC_max-jugC_state)), jugC_max

new_jugB_state = jugB_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 3: move from B into A (if room) AND (if not state doesn't exist)
if jugB_state !=0:
if jugA_state < jugA_max:
#Empty B into A if room
if jugA_state + jugB_state <= jugA_max:
new_jugB_state, new_jugA_state = 0, jugA_state + jugB_state
else: #Empty as much of B into A
totalToMove = jugA_max - jugA_state
new_jugA_state, new_jugB_state = jugA_max, jugB_state - totalToMove

new_jugC_state = jugC_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 4: move from B into C (if room) AND (if not state doesn't exist)
if jugB_state !=0:
if jugC_state < jugC_max:
#Empty B into C if room
if jugC_state + jugB_state <= jugC_max:
new_jugB_state, new_jugC_state = 0, jugC_state + jugB_state
else: #Empty as much of B into C
new_jugB_state, new_jugC_state = (jugB_state - jugC_max), jugC_max

new_jugA_state = jugA_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 5: move from C into B (if room) AND (if not state doesn't exist)
if jugC_state !=0:
if jugB_state < jugB_max:
#Empty C into B if room
if jugC_state + jugB_state <= jugB_max:
new_jugC_state, new_jugB_state = 0, jugB_state + jugC_state
else: #Empty as much of C into B
totalToMove = jugB_max - jugB_state
new_jugB_state, new_jugC_state = jugB_max, jugC_state - totalToMove

new_jugA_state = jugA_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 6: move from C into A (if room) AND (if not state doesn't exist)
if jugC_state !=0:
if jugA_state < jugA_max:
#Empty C into A if room
if jugA_state + jugC_state <= jugA_max:
new_jugC_state, new_jugA_state = 0, jugA_state + jugC_state
else: #Empty as much of C into A
totalToMove = jugA_max - jugA_state
new_jugA_state, new_jugC_state = jugA_max, jugC_state - totalToMove

new_jugB_state = jugB_state
if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
print (targetVol,"ml reached in", runningTotal+1,"steps")
print_Steps_Taken(previousSteps + [listPosition-1])
return True

#Move 7 - Empty A
if jugA_state != 0:
if jugB_state != 0 or jugC_state !=0:
if [0,jugB_state,jugC_state] not in listPrevSolutions:
listPrevSolutions.append([0,jugB_state,jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

#Move 8 - Empty B
if jugB_state != 0:
if jugA_state != 0 or jugC_state !=0:
if [jugA_state,0,jugC_state] not in listPrevSolutions:
listPrevSolutions.append([jugA_state,0,jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

#Move 9 - Empty C
if jugC_state != 0:
if jugB_state != 0 or jugA_state !=0:
if [jugA_state,jugB_state,0] not in listPrevSolutions:
listPrevSolutions.append([jugA_state,jugB_state,0])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

#Move 10 - Fill A
if jugA_state!=jugA_max:
if jugB_state != jugB_max or jugC_state!=jugC_max:
if [jugA_max,jugB_state,jugC_state] not in listPrevSolutions:
listPrevSolutions.append([jugA_max,jugB_state,jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

#Move 11 - Fill B
if jugB_state!=jugB_max:
if jugA_state!=jugA_max or jugC_state!=jugC_max:
if [jugA_state,jugB_max,jugC_state] not in listPrevSolutions:
listPrevSolutions.append([jugA_state,jugB_max,jugC_state])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

#Move 12 - Fill C
if jugC_state!=jugC_max:
if jugA_state != jugA_max or jugB_state!=jugB_max:
if [jugA_state,jugB_state,jugC_max] not in listPrevSolutions:
listPrevSolutions.append([jugA_state,jugB_state,jugC_max])
listTotalSteps.append(runningTotal+1)
list_index_steps.append(previousSteps + [listPosition])
listPosition +=1

if noNewSolutionAdded == 1 and listPrevSolutions.index(jugState) == len(listPrevSolutions) - 1:
print ("No new possible solutions")
return True

return False

def print_Steps_Taken(previousSteps):
for index in previousSteps:
print (listPrevSolutions[index])

def setjugVolumes():
#Set jug sizes (a,b,c) and target volume (d)
a = int(input("Please enter volume of largest jug: "))
b = int(input("Please enter volume of second largest jug: "))
c = int(input("Please enter volume of third largest jug: "))
jugsMax = [a,b,c]
targetVol = int(input("Please enter target volume: "))
return jugsMax, targetVol

def possibleStartStates():
#Set jug states
# (full, empty, empty), (full, full empty),
#(empty, full, empty), (empty, full, full),
#(empty, empty, full) ,(full, empty, full),
startStates = [
[5,0,0], [5,3,0],
[0,3,0], [0, 3,1],
[0,0,1], [5,0,1]]
return startStates

if __name__ == "__main__":
jugMax, targetVol = setjugVolumes()
#Get all possible start states - add featur later and run for loop for ALL possible
jugA_max = jugMax
jugB_max = jugMax
jugC_Max = jugMax

#Add first state to list with runningTotal
listPrevSolutions.append([jugA_max, 0,0])
listTotalSteps.append(1)

listPrevSolutions.append([0, jugB_max,0])
listTotalSteps.append(1)

listPrevSolutions.append([0, 0,jugC_Max])
listTotalSteps.append(1)

listPrevSolutions.append([jugA_max, jugB_max,0])
listTotalSteps.append(2)

listPrevSolutions.append([jugA_max, 0,jugC_Max])
listTotalSteps.append(2)

listPrevSolutions.append([0, jugB_max,jugC_Max])
listTotalSteps.append(2)

list_index_steps.append ()
list_index_steps.append ()
list_index_steps.append ()
list_index_steps.append ()
list_index_steps.append ()
list_index_steps.append ()

#Now run the function

counter = 0
for item in listPrevSolutions:
jugState = item
runningTotal = listTotalSteps[counter]
previousSteps = list_index_steps[counter]
listLength = len(listPrevSolutions)
x = MoveWater(jugMax,
jugState,
targetVol,
runningTotal,
previousSteps,
listLength)
counter +=1
if x == True:
break


Follow-up question: Solve the jug problem for n jugs

You’ve got too much code.

Not too much code to review - we can review a lot of code. You’ve written too much code for this problem. You’ve enumerated all the possible states, and hard coded variable names for all the possible states and constraints. You’ve got jugA_state, jugB_state and jugC_state for the current volumes of the 3 jugs and jugA_max, jugB_max and jugC_max (and sometimes jugC_Max!) for the capacities of the 3 jugs. If you have to solve a 4 jug problem, your amount of code is going to skyrocket. Never mind a 5 jug problem!

Instead, you should number the jugs 0, 1 and 2, and used indexing for the capacities and current volumes. You can use a tuple for the capacities, since it is fixed for the duration of the problem.

capacities = (5, 3, 1)
volumes = [5, 0, 0]


Moving water from one jug into any other jug can be done by one function:

def pour(from:int, to:int, volumes:list, capacities:tuple) -> list:
transfer = min(volumes[from], capacities[to] - volumes[to])
if transfer > 0:
volumes = volumes[:]        # Copy the current state (volumes)
volumes[from] -= transfer
volumes[to] += transfer
return volumes              # Return the new state (volumes)
return None


Pouring from each jug to every other jug is a simple double iteration:

for from in range(num_jugs):
for to in range(num_jugs):
if from != to:
new_volumes = pour(from, to, volumes, capacities)
if new_volumes:
# Valid pour - next, check if this is a new state, record move, etc.


The “empty a jug” and “fill a jug” moves are simpler; only a single iteration is required.

Checking if any jug has reached the target volume is easy. Just use the any() function with a generator expression:

if any(volume == target_volume for volume in volumes):
print("Target volume reached")


Testing if a new state is contained within a list of already visited states. You are using [...] in listPreviousSolutions. Instead of testing for containment in a list, which is an $$\O(N)\$$ search, you could use containment in a set, which is an $$\O(1)\$$ lookup. But since your states are themselves lists, which are mutable, you must first convert them into a tuple, which is immutable, and so is hashable which is required for sets.

previousStates = set()

#...

new_state = ...
new_state = tuple(new_state)
if new_state not in previousStates:
# ... etc ...


Use consistent naming. You’ve used mixedCase for some variables (targetVol), snake_case for others (list_index_steps), and even a combination of the two (jugA_max). snake_case is recommended by the PEP-8 standard.

Similar for function names. You’ve use CamelCase (MoveWater) , mixedCase (possibleStartStates) and a mashup of mixedCase and snake_case (print_Steps_Taken). You’ve also inconsistently capitalized when using mixedCase (setjugVolumes ... the j should have been capitalized). Again, be consistent. I believe PEP-8 recommends mixedCase for function names.

Spaces. Put a space around operators, like != and +=. Put a space after commas in lists and function calls. Do not put a space before the ( in function calls (list_index_steps.append ()).

Use a checker like pylint to validate your code against the PEP-8 standards, checking for these and other coding guidelines.

Don’t use an integer to represent a boolean state, and avoid negations in variable names. So instead of:

noNewSolutionsAdded = 1

# ...

if ... :

# ...

if noNewSolutionsAdded == 1  and  ...:


use:

solutions_added = False

# ...

if ...:

• Really good answer! But PEP-8 recommends snake_case for function and variable names. ☺️