Fox Goose Corn - Revision history

ThePlaz: teacher's solved version

2008-07-14T18:37:49Z

teacher's solved version

ThePlaz: my try

2008-07-14T18:37:06Z

my try

ThePlaz: given version

2008-07-14T18:36:31Z

given version

New page

<nowiki>
name = ["farmer","fox","goose","corn"]

def goal(s): # checks whether s=[0,0,0,0]
for i in s:
if i==1:
return False
return True

def first(list):
return list[0]

def rest(list):
return list[1:]

def printState(state):
print "Left Bank:"
for i in range(len(state)):
if state[i] == 1:
print name[i]
print "==="
print "Right Bank:"
for i in range(len(state)):
if state[i] == 0:
print name[i]

def printRule(rule):
if rule[0]==1:
direction = "left"
else:
direction = "right"
occupants = ""
for i in range(1,4):
if rule[i]==rule[0]: # find item moving along with farmer
occupants += name[i]
if occupants=="":
occupants = "no passengers"
print "Farmer brings boat to %s bank with %s" %(direction,occupants)

def preCondition(state,rule):
temp = applyRule(state,rule)
for i in temp:
if i<0 or i>1: # illegal state produced; can't apply rule
return False
return not feast(temp) # legal state produced, but is there a feast?

def applyRule(state,rule):
result = range(len(state))
for i in range(len(state)):
result[i] = state[i] + rule[i]
return result

def feast(s): #returns True if s represents a "feasting" state
if s[0]==1 and s[1]==0 and s[2]==0:
return True
if s[0]==1 and s[2]==0 and s[3]==0:
return True
if s[0]==0 and s[1]==1 and s[2]==1:
return True
if s[0]==0 and s[2]==1 and s[3]==1:
return True

return False

def applicableRules(s):
print "Applicable Rules for state %s" %s
ar = []
for r in allRules:
"Trying rule %s" %r
if preCondition(s,r):
ar += r
return ar

def backtrack(statelist):
# Need to write this!

allStates = [[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0],
[1,0,1,1],[1,0,1,0],[1,0,0,1],[1,0,0,0],
[0,1,1,1],[0,1,1,0],[0,1,0,1],[0,1,0,0],
[0,0,1,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]

allRules = [[-1,0,0,0],[-1,-1,0,0],[-1,0,-1,0],[-1,0,0,-1],
[ 1,0,0,0],[ 1, 1,0,0],[ 1,0, 1,0],[ 1,0,0, 1]]

state = [1,1,1,1]
rule = [-1,0,-1,0]
initialState = state
MAX_DEPTH = 10

newstate = applyRule(state,rule)

print newstate

print "--------"

for i in newstate:
print i

print "--------"

for s in allStates:
print feast(s)

for s in allStates:
for r in allRules:
if preCondition(s,r):
print "Can apply %s to %s . Feast=%s" %(r,s,feast(applyRule(s,r)))
else:
print "Can't apply %s to %s . Feast=%s" %(r,s,feast(applyRule(s,r)))

print "---------------"
print "first(allrules)"
print "---------------"
print first(allrules)

print "---------------"
print "rest(allrules)"
print "---------------"
print rest(allrules)

def member(x,L):
for i in L:
if i==x:
return True
return False

print "---------------"
print "member(allrules[5],allrules)"
print "---------------"
print member(allrules[5],allrules)

print "---------------"
print "member(t,allrules) where t=allrules[5]"
print "---------------"
t = allrules[5]
print member(t,allrules)

print "---------------"
print "member(u,allrules) where u=[-1,0,0,-1]"
print "---------------"
u=[-1,0,0,-1]
print member(u,allrules)

print "---------------"
print "member(state[0],allrules)"
print "---------------"
print member(state[0],allrules)

print "---------------"
print "rule interpreter"
print "---------------"
for r in allRules:
print r
printRule(r)

print "---------------"
print "applicable rules"
print "---------------"
print applicableRules(initialState)

statelist = [ initialState ]
print "statelist=%s" %statelist

path = backtrack(statelist)
print path

</nowiki>

@@ Line 12: / Line 12: @@
 def rest(list):
-     return list[1:] #returns everything but the 1st one
+     return list[1:]
 def printState(state):
@@ Line 46: / Line 46: @@
 def applyRule(state,rule):
      result = range(len(state))
      for i in range(len(state)):
          result[i] = state[i] + rule[i]
@@ Line 65: / Line 65: @@
 def applicableRules(s):
      ar = []
      for r in allRules:
          if preCondition(s,r):
              ar.append(r)
      return ar
-def backtrack(stateList):
+def backtrack(statelist):
-     print "State!!!!!!!!!!!"
+     state = first(statelist)
-    print str(stateList)
+     print "in backtrack, state=%s" %state
-     state = first(stateList)
      if goal(state):
-         return stateList
+         print "GOAL!!!"
-     '''if feast(state):
+        return []  # goal reached, return empty list
-         return "Failure" #dead end'''
+     if len(statelist)>MAX_DEPTH:
-     if state == rest(stateList): #if state is a member of rest(statelist)
+         return "Failure"  # depth bound exceeded
-         return "Failure"
+     if member(state,rest(statelist)):
-     moves = applicableRules(state) #all possible moves from state, runs precondition
+     Moves = applicableRules(state)
-     for m in moves:
+    print "Applicable Rules for state %s : %s" %(state,Moves)
-         nextState = applyRule(state, m) #precondition has already run
+     for r in Moves:
-         newStateList = stateList.insert(0,nextState) #add nextState to the front of list
+         print "Trying rule %s" %r
-         path = backtrack (newStateList)
+        newState = applyRule(state,r)
-         if path != "Failure":
+        print "newState: %s" %newState
              return path
-     return "Failure" #all moves resulted in failure
 allStates = [[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0],
@@ Line 176: / Line 186: @@
 print "applicable rules"
 print "---------------"
 print applicableRules(initialState)
 statelist = [ initialState ]
@@ Line 188: / Line 194: @@
 path = backtrack(statelist)
 print path
 </nowiki>