Solve the jug problem for n jugs

Question

Apart from PEP8 issues which I will eventually get my head around, what do you think of my update to the 3 jugs jug problem (which now works for n number of jugs)

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

Original code: Jug problem - 3 jugs

from math import factorial
global list_previous_jug_states 
list_previous_jug_states = []
global list_running_count 
list_running_count = []
global list_running_index 
list_running_index  = []
global list_volumes 
list_volumes = []
global list_jug_max
list_jug_max = []

class CreateJugs:
    #Create a new jug instance
    def __init__ (self,jug_name,jug_max):
        self.name = jug_name
        self.max = jug_max

        list_jug_max.append(self)

    @property
    def jug_max (self):
        return self.max


def set_fill_states (number_jugs, jug_max):
    #Create a list of binary starting states (e.g: 0,0,0,0....1,1,1,0 where 1 = MAX and 0 = empty)
    global list_binary_states
    list_binary_states = []
    for i in range (1<<number_jugs):
        binary_state =bin(i)[2:]
        binary_state ='0'*(number_jugs-len(binary_state))+binary_state
        list_binary_states.append(binary_state)
    list_binary_states = list_binary_states[0:len(list_binary_states)-1]

    #Create lists to hold previous states, running count for each jug, running index of previous positions
    #Running count: if start position is (binary): 1,1,0 that = 2
    #Running count: start 0,0,1 = 1



    #Sort list by number of 1s
    new_list = []
    for x in range (number_jugs):
        for item in list_binary_states:
            if item.count('1') ==  x:
                new_list.append(item)
                list_running_count.append(x)
    #Copy list back to origina function
    list_binary_states = new_list[:]

    #Now print all possible starting oreintations 
    for n in range (len(list_binary_states)):
        jug_binary_state = list_binary_states[int(n)]
        jug_state = []
        for x in range (number_jugs):
            if int(jug_binary_state[x]) == 1: 
                jug_state.append(list_jug_max[x].max)
            else:
                jug_state.append (0)
        list_previous_jug_states.append(jug_state)
        list_running_index.append([n])

def make_moves (jug_state,
                running_total, running_index,
                target_volume, number_jugs):
    for from_jug in range (number_jugs):
        from_jug_max = list_jug_max[from_jug].jug_max
        from_jug_state = jug_state[from_jug]

        for to_jug in range (number_jugs):
            if to_jug == from_jug: continue  

            to_jug_max = list_jug_max[to_jug].jug_max
            to_jug_state = jug_state[to_jug]

            #Empty from_jug, ignore to_jug
            new_jug_state = jug_state [:]
            new_jug_state[from_jug] = 0
            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index) 
            #Fill from_jug, ignore to_jug
            new_jug_state = jug_state [:]
            new_jug_state[from_jug] = from_jug_max
            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index) 

            #Move as much from from_jug to to_jug
            if to_jug_state == to_jug_max: continue
            if from_jug_state == 0: continue
            if from_jug_state < (to_jug_max-to_jug_state):
                new_jug_state = jug_state [:]
                new_jug_state[from_jug] = 0
                new_jug_state[to_jug] = to_jug_state + from_jug_state
            else:
                amount_transfer = to_jug_max - to_jug_state
                new_jug_state = jug_state [:]
                new_jug_state[from_jug] = from_jug_state - amount_transfer
                new_jug_state[to_jug] = to_jug_state + amount_transfer

            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index)            

            if any (jug == target_volume for jug in new_jug_state):
                print ("Target reached in ", running_total + 1, "steps")
                for item in running_index:
                    print (list_previous_jug_states[item])
                print (new_jug_state)
                return True            


    return False, 0

if __name__ == "__main__":
    number_jugs = int(input("Please enter the number of jugs you have: "))
    #Set jug volumes
    for i in range (number_jugs):
        jug_volume = int(input(f"Please enter the volume of jug {i+1}: "))
        list_volumes.append(jug_volume)
    #Set target volume
    target_volume = int(input("Please enter the target volume: "))
    #Sort jugs in size order
    list_volumes.sort(reverse=True)
    #Create object instances
    for i in range (number_jugs):
        jug_name = "Jug" + str(i+1)
        CreateJugs (jug_name, list_volumes[i])
    # set_fill_states(number_jugs) #Set the fill states
    set_fill_states(number_jugs,list_volumes)
    #Continue iterating through jug_previous_state
    for item in list_previous_jug_states:
        jug_state = item

        index = list_previous_jug_states.index(item)
        running_total = list_running_count [index]
        running_index = list_running_index [index]
        is_destination = make_moves (jug_state,
                                    running_total, 
                                    running_index, 
                                    target_volume,
                                    number_jugs)

        if is_destination == True:
            print ("=====")
            break

Answer 1

Global variables

You never need to execute global variable_name in the global scope; variables created in the global scope are automatically global variables. So the following statements should all be removed:

global list_previous_jug_states 
global list_running_count 
global list_running_index 
global list_volumes 
global list_jug_max

JSYK: You rarely need global variable_name inside of functions. If a function references a variable that it has not created, and that variable exists in the global scope, that variable is automatically brought into the function scope. It is only necessary when you want to create (variable_name = ...) or modify (variable_name += 10) a global variable inside a function scope. Note that modifying an object (ie, dictionary, list, etc) held in a global variable is not modifying the global variable itself, so variable_name[x] = y would not require global variable_name.

---

class CreateJugs

This class is ill-named. A class is (usually) an item ... a noun such as a person, place or thing. It is rarely an action. "Create" is an action. Functions do things (actions), so you could have def create_jug():, but class CreateJugs is calling something which should be a thing by a name that describes an action.

Moreover, a class is an object ... singular. It shouldn't have a plural name.

A better name for the class might be simply Jug.

max is a built-in function name in Python. You should avoid using it as the name of a class member (self.max).

If you want a property of a jug, you must already have a jug object, so repeating jug_ in the property name is redundant. In the following statement, you are using jug 4 times. Would it be any less clear to remove jug_ from the property name? Or would it actually be clearer, because it is shorter and more concise?

to_jug_max = list_jug_max[to_jug].jug_max

Base on the above points, I would instead write:

class Jug:

    def __init__(self, name, capacity):
        self._name = name
        self._capacity = capacity

        list_jug_max.append(self)

    @property
    def capacity(self):
        return self._capacity

But the only places where Jug objects are used, are the following statements:

jug_state.append(list_jug_max[x].max)
from_jug_max = list_jug_max[from_jug].jug_max
to_jug_max = list_jug_max[to_jug].jug_max

You are only ever using the Jug objects to access a single property: the jug's capacity. (Worse, you are doing so inconsistently ... sometimes directly getting the .max member, other times accessing the .jug_max property!)

Since the jugs are created using the values in list_volumes, you could completely remove the class and list_jug_max, and replace the above statements with:

jug_state.append(list_volumes[x])
from_jug_max = list_volumes[from_jug]
to_jug_max = list_volumes[to_jug]

---

set_fill_states

The variable list_binary_states is only used in the function set_fill_states. Why make it global?

---

You are using '0' * (number_jugs - len(binary_state)) + binary_state to pad a string with leading 0's. There is a built-in function which does this:

binary_state = binary_state.rjust(number_jugs, '0')

Without the need for getting the length of binary_state separately, you can now convert the number into binary, remove the prefix, and add the padding in one statement:

binary_state = bin(i)[2:].rjust(number_jugs, '0')

Or, using format strings for formatting a number as binary, without a prefix, in a certain field width, with leading zeros:

binary_state = f"{i:0{number_jugs}b}"

---

Why:

list_binary_states = list_binary_states[0:len(list_binary_states)-1]

Shouldn't starting with all the jugs filled be a valid possibility?

If you want to remove the last item of a list, you can simply use a slice that ends one element before the end of the list:

list_binary_states = list_binary_states[:-1]

---

Python comes with a lot of built-in capability. That includes sorting.

You've implemented a selection sort (\$O(N^2)\$), where you search for items by counting the number of '1' characters in a N character string, making this sort into a \$O(N^3)\$ complexity. Ouch!

list_binary_states.sort(key=lambda item: item.count('1'))

Done in 1 statement, in \$O(N \log N)\$ time.

---

for n in range (len(list_binary_states)):
    # ...
    list_running_index.append([n])

This is simply:

list_running_index = list(range(len(list_binary_states)))

Without that, the loop becomes ...

for n in range (len(list_binary_states)):
    jug_binary_state = list_binary_states[int(n)]
    # ...

... with no other references to n (which was alway an integer, so there was never a need to evaluate int(n)). Since you are only using n to index into list_binary_states, which is what you are looping over, you can replace this loop with:

for jug_binary_state in list_binary_states:
    # ...

---

    jug_state = []
    for x in range (number_jugs):
        if int(jug_binary_state[x]) == 1: 
            jug_state.append(list_jug_max[x].max)
        else:
            jug_state.append (0)

Now, jug_binary_state is a string of length number_jugs. So we can loop over the characters of the string, instead of over the number of jugs. list_volumes is a list (of length number_jugs) of the maximum volume of each jug. We just need to zip the characters and the volumes together, to construct the jug_state.

    jug_state = []
    for ch, volume in zip(jug_binary_state, list_volumes):
        if ch == '1':
            jug_state.append(volume)
        else:
            jug_state.append(0)

Or, using list comprehension:

    jug_state = [ volume if ch == '1' else 0
                  for ch, volume in zip(jug_binary_state, list_volumes) ]

---

make_moves

for from_jug in range (number_jugs):
    for to_jug in range (number_jugs):
        if to_jug == from_jug: continue  
        #Empty from_jug, ignore to_jug
        #Fill from_jug, ignore to_jug
        #Move as much from from_jug to to_jug

For each from_jug, you loop over each possible to_jug, and then ignore the to_jug for the "Empty" and "Fill" possible moves. But you are still evaluating the new state for these moves for every to_jug, only to discarding the duplicate states. Why? That is a lot of extra work.

How about moving the "Empty" and "Fill" steps out of the inner loop?

for from_jug in range (number_jugs):
    #Empty from_jug
    #Fill from_jug
    for to_jug in range (number_jugs):
        if to_jug == from_jug: continue  
        #Move as much from from_jug to to_jug

---

Move common steps out of if statements. Here, you are always create new_jug_state the same way:

        if from_jug_state < (to_jug_max-to_jug_state):
            new_jug_state = jug_state [:]
            #...
        else:
            new_jug_state = jug_state [:]
            #...

And if transfer_amount is set to from_jug_state, the last two statements of the else clause would do what the last two statements of the "then" clause would do:

        if ...:
            # ...
            new_jug_state[from_jug] = 0
            new_jug_state[to_jug] = to_jug_state + from_jug_state
        else:
            # ...
            new_jug_state[from_jug] = from_jug_state - amount_transfer
            new_jug_state[to_jug] = to_jug_state + amount_transfer

So you can simplify this to:

        if ...:
            # ...
            transfer_amount = from_jug_state
        else:
            # ...
        new_jug_state[from_jug] = from_jug_state - amount_transfer
        new_jug_state[to_jug] = to_jug_state + amount_transfer

---

What does make_moves() return? A boolean or a tuple?

return True

return False, 0

Always return the same kind of thing from a function. If the function returns a boolean, only return a boolean. If the function returns a tuple of values, always return a tuple of values. Don't change what it returned; the caller won't know what to expect, so won't know how to interpret the results without going to heroic efforts. The tuple False, 0 is truthy value (not a falsy value) because the tuple contains more than 0 values!

---

Use functions! make_moves() is a long function. It has easy-to-make sub-functions, like fill_a_jug(), empty_a_jug(), pour_between_jugs(), which will help a reader of the code understand what the function does at a high level without being bogged down with lower level details, and the reader can look at the sub-functions separately for the lower-level details.

---

Don't modify lists while you iterate over them

for item in list_previous_jug_states:

    make_moves(...) # Appends to list_previous_jug_states

While it can be made to work, you've had to use global variables, maintain other lists (list_running_count, list_running_index) to determine how many steps were required to reach the current step, and where a given step came from.

Consider an alternate strategy:

visited = { state: None for state in initial_states }
current_states = initial_states
steps = 0

while not solved:

    new_states = []

    for state in current_states:
        for new_state in valid_moves(state):
            if new_state not in visited:
                visited[new_state] = current_state
                new_states.append(new_state)

    current_states = new_states
    steps += 1

Here, I'm looping over all of the current_state values, and building up a new list of new_states, for the next step. When all the new states that are reachable from all of the current states have been determined, that list of new states replaces the current_states, and the process repeats for the next step.

The visited dictionary keeps track of the previous state that the current state was reached from. Once a solution has been found, simply trace the path back to the initial state (None) to determine the shortest solution path.

Like mentioned in my previous answer, you will need to use a tuple for the states, to allow them to be used as a key in the visited dictionary.

---

This "N-Jug" problem can be simplified (as in, less code) into an "N+1 Jug" problem, with just the "Pour from Jug A to Jug B" moves. Simply create one additional jug with a capacity equal to the sum of all other jug capacities, and initialize it with a volume equal to its capacity less the volume initially contained in the remaining jugs. With this extra jug called "Jug 0", the "Fill Jug A" move becomes "Pour from Jug 0 to Jug A", and the "Empty Jug A" move becomes "Pour from Jug A to Jug 0".