Putting all the pieces together we have pitcher_new_2_succint.py:
# pitcher_new_2_succint.py
import copy
class Pitcher:
def __init__(self, capacity, contents=0):
self.capacity = capacity
self.contents = contents
def empty(self):
self.contents = 0
def fill(self):
self.contents = self.capacity
def __str__(self): # debugging aid
return '%d/%d' % (self.contents, self.capacity)
def __eq__(self, other):
if type(self) == type(other):
return self.capacity == other.capacity \
and self.contents == other.contents
else:
return False
def is_full(self): # Convenience function to make code more readable.
return self.capacity == self.contents
def is_empty(self): # Convenience function to make code more readable.
return self.contents == 0
def pour(src, destn):
destn_space = destn.capacity - destn.contents
src_avail = src.contents
transfer = min(destn_space, src_avail)
# print 'Transferring', transfer, 'liters.'
destn.contents += transfer
src.contents -= transfer
def subset_x(lst, x):
''' return subset number x of the items in lst '''
subset = []
for i in range(len(lst)):
# Check to see if bit corresponding to item i is set in x.
if x & (2**i):
subset.append(lst[i])
return subset
def is_goal(state, goal):
''' Does any subset of pitchers in state contain the goal amount? '''
# Check each subset of state. There are 2**len(state) possible subsets.
for subset_num in range(1, 2**len(state)):
subset = subset_x(state, subset_num)
total = 0
for pitcher in subset:
total += pitcher.contents
if total == goal:
return True
return False
# A little debugging help:
def show_state_list(sl):
print '\nstate_list:'
for i in range(len(sl)):
print i, ':',
show_state(sl[i])
print
print
def show_state(s):
for p in s:
print p,
def solve_it(pitchers, goal):
'''Solve the problem of measuring goal litres of water
using the pitchers in the list pitchers.
'''
state_list = [pitchers] # See note 0 # Initialize the state list
tried_states = [] # Initialize tried_states
while True: # See note 1 #
# Is it time to give up?
# It is if there are no more states to try.
if len(state_list) == 0:
break
# If not, get the next state to try.
# Take it from the front of the list to do breadth-first traversal.
state = state_list.pop(0)
# Have we figured it out?
# We have if this state is a solution.
if is_goal(state, goal): # See note 2 #
break
# If we haven't, record that we are trying this state.
tried_states.append(state) # See note 3 #
#
# Grow tree downward from this state by
# trying every action for every pitcher in it.
#
# Emptying:
for i in range(len(state)): # See note 4 # For every pitcher (by index).
new_state = copy.deepcopy(state) # See note 4 #
# Give new_state[i] a more meaningful name
pitcher = new_state[i]
if not pitcher.is_empty():
pitcher.empty()
# If this isn't a state we've tried and it isn't already in
# state_list:
if new_state not in tried_states \
and new_state not in state_list: # See notes 5 and 6 #
state_list.append(new_state)
# Filling:
for i in range(len(state)):
new_state = copy.deepcopy(state)
pitcher = new_state[i]
if not pitcher.is_full():
pitcher.fill()
if new_state not in tried_states \
and new_state not in state_list:
state_list.append(new_state)
# Pouring:
# Try pouring from every pitcher into every other pitcher
# (so nested loops to try all combinations).
for src in range(len(state)): # index of source pitcher
for dest in range(len(state)): # index of destination pitcher
if src == dest: # Don't try to pour into ourself!
next # See note 6 #
new_state = copy.deepcopy(state)
# Assign more meaningful names:
(source, destination) = (new_state[src], new_state[dest])
if not source.is_empty() and not destination.is_full():
pour(source, destination)
if new_state not in tried_states \
and new_state not in state_list:
state_list.append(new_state)
# We end up here if it is solved, but also if it is unsolvable
if is_goal(state, goal):
print 'Figured it out!'
else:
print 'That\'s an impossible problem!'
if __name__ == '__main__':
# Test Pitcher class:
print 'Create pitchers 7:5 and 3:3'
a = Pitcher(7,5)
b = Pitcher(3,3)
print a
print b
print 'Try pouring into a full pitcher:'
pour(a,b)
print a
print b
print 'Try pouring from 3:3 into 7:5, should pour 2 litres:'
pour(b,a)
print a
print b
print 'Empty both pitchers:'
a.empty()
b.empty()
print a
print b
print
# Test Pitcher Problem solving function solve_it:
print 'Starting problems...'
# Test Problem 1: Measure 4 litres using 3 and 7 litre pitchers
goal = 4 # Set the goal
start = [Pitcher(3,0), Pitcher(7,0)] # Start with two empty pitchers
solve_it(start, goal)
# Test Problem 2: Measure 1 litre using 2, 5 and 10 litre pitchers
goal = 1
start = [Pitcher(2,0), Pitcher(5,0), Pitcher(10,0)]
solve_it(start, goal)
# Test Problem 3: Measure 2 litres using 3 and 7 litre pitchers
goal = 2
start = [Pitcher(3,0), Pitcher(7,0)]
solve_it(start, goal)
# Test Problem 4: Impossible problem
# Measure 1 litres using 5 and 10 litre pitchers
goal = 1
start = [Pitcher(5,0), Pitcher(10,0)]
solve_it(start, goal)
# Test Problem 5: Multi-pitcher solution
# Measure 10 litres using 3 and 7 litre pitchers
goal = 10
start = [Pitcher(3,0), Pitcher(7,0)]
solve_it(start, goal)
# Test Problem 6: Multi-pitcher solution
# Measure 12 litres using 2, 5 and 10 litre pitchers
goal = 12
start = [Pitcher(2,0), Pitcher(5,0), Pitcher(10,0)]
solve_it(start, goal)
print '...done.'