A general state space search algorithm is implemented in search.py. Go through this and try to understand it. An example of how to implement a particular search problem using the state space code is shown in pitcher.py. Note in particular how the PitcherState class works in conjunction with the Search class. Using the PitcherState class as a model, write a Simpsons class that implements a solution to the following slightly modified problem from an episode of the Simpsons called Gone Maggie Gone from 2009. Homer Simpson has to move his daughter Maggie, his dog Santa's Little Helper, and a jar of medical marijuana that looks like candy across a river. He can only take one item in his boat at a time. He can't leave Maggie alone with the medical marijuana (or she will eat it) and he can't leave Santa's Little Helper alone with Maggie (because the dog will pester the girl). Formulate the actions for this problem and implement them. Be careful to ensure that illegal states are flagged correctly. ### File pitcher.py ### Implements the water pitcher puzzle for state space search from search import * class PitcherState(ProblemState): def __init__(self, q3, q4): self.q3 = q3 self.q4 = q4 def __str__(self): """ Required method for use with the Search class. Returns a string representation of the state. """ return "("+str(self.q3)+","+str(self.q4)+")" def illegal(self): """ Required method for use with the Search class. Tests whether the state is illegal. """ if self.q3 < 0 or self.q4 < 0: return 1 if self.q3 > 3 or self.q4 > 4: return 1 return 0 def equals(self, state): """ Required method for use with the Search class. Determines whether the state instance and the given state are equal. """ return self.q3==state.q3 and self.q4==state.q4 def fillq3(self): return PitcherState(3, self.q4) def fillq4(self): return PitcherState(self.q3, 4) def drainq3(self): return PitcherState(0, self.q4) def drainq4(self): return PitcherState(self.q3, 0) def pourq3Toq4(self): capacity = 4 - self.q4 if self.q3 > capacity: return PitcherState(self.q3-capacity, 4) else: return PitcherState(0, self.q4 + self.q3) def pourq4Toq3(self): capacity = 3 - self.q3 if self.q4 > capacity: return PitcherState(3, self.q4-capacity) else: return PitcherState(self.q3 + self.q4, 0) def operatorNames(self): """ Required method for use with the Search class. Returns a list of the operator names in the same order as the applyOperators method. """ return ["fillq3", "fillq4", "drainq3", "drainq4", "pourq3Toq4", "pourq4Toq3"] def applyOperators(self): """ Required method for use with the Search class. Returns a list of possible successors to the current state, some of which may be illegal. """ return [self.fillq3(), self.fillq4(), self.drainq3(), self.drainq4(), self.pourq3Toq4(), self.pourq4Toq3()] Search(PitcherState(0,0), PitcherState(0,2))
A general state space search
Homer Simpson has to move his daughter Maggie, his dog Santa's Little Helper, and a jar of medical marijuana that looks like candy across a river. He can only take one item in his boat at a time. He can't leave Maggie alone with the medical marijuana (or she will eat it) and he can't leave Santa's Little Helper alone with Maggie (because the dog will pester the girl). Formulate the actions for this problem and implement them. Be careful to ensure that illegal states are flagged correctly.
### File pitcher.py
### Implements the water pitcher puzzle for state space search
from search import *
class PitcherState(ProblemState):
def __init__(self, q3, q4):
self.q3 = q3
self.q4 = q4
def __str__(self):
"""
Required method for use with the Search class.
Returns a string representation of the state.
"""
return "("+str(self.q3)+","+str(self.q4)+")"
def illegal(self):
"""
Required method for use with the Search class.
Tests whether the state is illegal.
"""
if self.q3 < 0 or self.q4 < 0: return 1
if self.q3 > 3 or self.q4 > 4: return 1
return 0
def equals(self, state):
"""
Required method for use with the Search class.
Determines whether the state instance and the given
state are equal.
"""
return self.q3==state.q3 and self.q4==state.q4
def fillq3(self):
return PitcherState(3, self.q4)
def fillq4(self):
return PitcherState(self.q3, 4)
def drainq3(self):
return PitcherState(0, self.q4)
def drainq4(self):
return PitcherState(self.q3, 0)
def pourq3Toq4(self):
capacity = 4 - self.q4
if self.q3 > capacity:
return PitcherState(self.q3-capacity, 4)
else:
return PitcherState(0, self.q4 + self.q3)
def pourq4Toq3(self):
capacity = 3 - self.q3
if self.q4 > capacity:
return PitcherState(3, self.q4-capacity)
else:
return PitcherState(self.q3 + self.q4, 0)
def operatorNames(self):
"""
Required method for use with the Search class.
Returns a list of the operator names in the
same order as the applyOperators method.
"""
return ["fillq3", "fillq4", "drainq3", "drainq4",
"pourq3Toq4", "pourq4Toq3"]
def applyOperators(self):
"""
Required method for use with the Search class.
Returns a list of possible successors to the current
state, some of which may be illegal.
"""
return [self.fillq3(), self.fillq4(),
self.drainq3(), self.drainq4(),
self.pourq3Toq4(), self.pourq4Toq3()]
Search(PitcherState(0,0), PitcherState(0,2))
Step by step
Solved in 3 steps
