Jug problem - 3 jugs

Question

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

    noNewSolutionAdded = 1
    listPosition = listLength

    jugA_max = jugMax[0]
    jugB_max = jugMax[1]
    jugC_max = jugMax [2]

    jugA_state = jugState[0]
    jugB_state = jugState[1]
    jugC_state = jugState[2]

    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 

                noNewSolutionAdded = 0

            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 

                noNewSolutionAdded = 0

            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 

                noNewSolutionAdded = 0

            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 

                noNewSolutionAdded = 0

            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 

                noNewSolutionAdded = 0

            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 

                noNewSolutionAdded = 0

            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 

                    noNewSolutionAdded = 0

    #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 

                    noNewSolutionAdded = 0

    #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 

                    noNewSolutionAdded = 0

    #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 

                    noNewSolutionAdded = 0

    #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 

                    noNewSolutionAdded = 0

    #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 

                    noNewSolutionAdded = 0

    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
    #...states. Add this feature later 
    jugA_max = jugMax[0]
    jugB_max = jugMax[1]
    jugC_Max = jugMax[2]

    #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 ([0]) 
    list_index_steps.append ([1]) 
    list_index_steps.append ([2]) 
    list_index_steps.append ([3]) 
    list_index_steps.append ([4])
    list_index_steps.append ([5])  


    #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

Answer 1

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")

---

More advanced:

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:
    previousStates.add(new_state)
    # ... etc ...

---

General PEP-8 comments.

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 ([5])).

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 ... :
    noNewSolutionsAdded = 0

# ...

if noNewSolutionsAdded == 1  and  ...:

use:

solutions_added = False

# ...

if ...:
    solutions_added = True

# ...

if not solutions_added  and  ...: