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)$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(N3)$O({N}^{3})$ complexity. Ouch!

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

Done in 1 statement, in O(NlogN)$O(N\mathrm{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”.