Difference between revisions of "Fox Goose Corn"

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:] #returns everything but the 1st one 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)) #print str(result)+str(state)+str(rule) 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.append(r) return ar def backtrack(stateList): print "State!!!!!!!!!!!" print str(stateList) state = first(stateList) if goal(state): return stateList '''if feast(state): return "Failure" #dead end''' if state == rest(stateList): #if state is a member of rest(statelist) return "Failure" moves = applicableRules(state) #all possible moves from state, runs precondition for m in moves: nextState = applyRule(state, m) #precondition has already run newStateList = stateList.insert(0,nextState) #add nextState to the front of list path = backtrack (newStateList) if path != "Failure": 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], [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 "---------------" print "-----Finally getting started----------" print "---------------" statelist = [ initialState ] print "statelist=%s" %statelist path = backtrack(statelist) print path