Difference between revisions of "Fox Goose Corn"
From ThePlaz.com
(given version) |
(teacher's solved version) |
||
(One intermediate revision by one user not shown) | |||
Line 46: | Line 46: | ||
def applyRule(state,rule): | def applyRule(state,rule): | ||
+ | print "ApplyRule: state=%s , rule=%s" %(state,rule) | ||
result = range(len(state)) | result = range(len(state)) | ||
for i in range(len(state)): | for i in range(len(state)): | ||
Line 64: | Line 65: | ||
def applicableRules(s): | def applicableRules(s): | ||
− | |||
ar = [] | ar = [] | ||
for r in allRules: | for r in allRules: | ||
− | |||
if preCondition(s,r): | if preCondition(s,r): | ||
− | ar | + | ar.append(r) |
return ar | return ar | ||
def backtrack(statelist): | def backtrack(statelist): | ||
− | + | state = first(statelist) | |
+ | print "in backtrack, state=%s" %state | ||
+ | if goal(state): | ||
+ | print "GOAL!!!" | ||
+ | return [] # goal reached, return empty list | ||
+ | if len(statelist)>MAX_DEPTH: | ||
+ | return "Failure" # depth bound exceeded | ||
+ | if member(state,rest(statelist)): | ||
+ | return "Failure" # cycle detected | ||
+ | |||
+ | Moves = applicableRules(state) | ||
+ | print "Applicable Rules for state %s : %s" %(state,Moves) | ||
+ | for r in Moves: | ||
+ | print "Trying rule %s" %r | ||
+ | newState = applyRule(state,r) | ||
+ | print "newState: %s" %newState | ||
+ | newStateList = statelist | ||
+ | newStateList.insert(0,newState) | ||
+ | print "newStateList: %s" %newStateList | ||
+ | path = backtrack(newStateList) | ||
+ | if path == "Failure": | ||
+ | newStateList.remove(newState) | ||
+ | else: | ||
+ | print "Path does not fail: %s" %path | ||
+ | |||
+ | path.append(r) | ||
+ | return path | ||
+ | |||
+ | return "Failure" # no solution can be reached from here | ||
+ | |||
allStates = [[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0], | allStates = [[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0], | ||
Line 110: | Line 138: | ||
print "---------------" | print "---------------" | ||
− | print "first( | + | print "first(allRules)" |
print "---------------" | print "---------------" | ||
− | print first( | + | print first(allRules) |
print "---------------" | print "---------------" | ||
− | print "rest( | + | print "rest(allRules)" |
print "---------------" | print "---------------" | ||
− | print rest( | + | print rest(allRules) |
def member(x,L): | def member(x,L): | ||
Line 126: | Line 154: | ||
print "---------------" | print "---------------" | ||
− | print "member( | + | print "member(allRules[5],allRules)" |
print "---------------" | print "---------------" | ||
− | print member( | + | print member(allRules[5],allRules) |
print "---------------" | print "---------------" | ||
− | print "member(t, | + | print "member(t,allRules) where t=allRules[5]" |
print "---------------" | print "---------------" | ||
− | t = | + | t = allRules[5] |
− | print member(t, | + | print member(t,allRules) |
print "---------------" | print "---------------" | ||
− | print "member(u, | + | print "member(u,allRules) where u=[-1,0,0,-1]" |
print "---------------" | print "---------------" | ||
u=[-1,0,0,-1] | u=[-1,0,0,-1] | ||
− | print member(u, | + | print member(u,allRules) |
print "---------------" | print "---------------" | ||
− | print "member(state[0], | + | print "member(state[0],allRules)" |
print "---------------" | print "---------------" | ||
− | print member(state[0], | + | print member(state[0],allRules) |
print "---------------" | print "---------------" | ||
Line 158: | Line 186: | ||
print "applicable rules" | print "applicable rules" | ||
print "---------------" | print "---------------" | ||
+ | print "applicableRules(initialState)" | ||
print applicableRules(initialState) | print applicableRules(initialState) | ||
Line 165: | Line 194: | ||
path = backtrack(statelist) | path = backtrack(statelist) | ||
print path | print path | ||
+ | for r in path: | ||
+ | printRule(r) | ||
</nowiki> | </nowiki> |
Latest revision as of 18:37, 14 July 2008
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): print "ApplyRule: state=%s , rule=%s" %(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): ar = [] for r in allRules: if preCondition(s,r): ar.append(r) return ar def backtrack(statelist): state = first(statelist) print "in backtrack, state=%s" %state if goal(state): print "GOAL!!!" return [] # goal reached, return empty list if len(statelist)>MAX_DEPTH: return "Failure" # depth bound exceeded if member(state,rest(statelist)): return "Failure" # cycle detected Moves = applicableRules(state) print "Applicable Rules for state %s : %s" %(state,Moves) for r in Moves: print "Trying rule %s" %r newState = applyRule(state,r) print "newState: %s" %newState newStateList = statelist newStateList.insert(0,newState) print "newStateList: %s" %newStateList path = backtrack(newStateList) if path == "Failure": newStateList.remove(newState) else: print "Path does not fail: %s" %path path.append(r) return path return "Failure" # no solution can be reached from here 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)" print applicableRules(initialState) statelist = [ initialState ] print "statelist=%s" %statelist path = backtrack(statelist) print path for r in path: printRule(r)