Problem
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
Solution
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(N2)), where you search for items by counting the number of '1' characters in a N character string, making this sort into a O(N3) complexity. Ouch!
list_binary_states.sort(key=lambda item: item.count('1'))
Done in 1 statement, in O(NlogN) 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”.