Fox Goose Corn

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)