Difference between revisions of "Fox Goose Corn"
From ThePlaz.com
(given version) |
(my try) |
||
Line 12: | Line 12: | ||
def rest(list): | def rest(list): | ||
− | return list[1:] | + | return list[1:] #returns everything but the 1st one |
def printState(state): | def printState(state): | ||
Line 47: | Line 47: | ||
def applyRule(state,rule): | def applyRule(state,rule): | ||
result = range(len(state)) | result = range(len(state)) | ||
+ | #print str(result)+str(state)+str(rule) | ||
for i in range(len(state)): | for i in range(len(state)): | ||
result[i] = state[i] + rule[i] | result[i] = state[i] + rule[i] | ||
Line 69: | Line 70: | ||
"Trying rule %s" %r | "Trying rule %s" %r | ||
if preCondition(s,r): | if preCondition(s,r): | ||
− | ar | + | ar.append(r) |
return ar | return ar | ||
− | def backtrack(statelist): | + | 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], | allStates = [[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0], | ||
Line 110: | Line 128: | ||
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 144: | ||
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 159: | Line 177: | ||
print "---------------" | print "---------------" | ||
print applicableRules(initialState) | print applicableRules(initialState) | ||
+ | |||
+ | |||
+ | print "---------------" | ||
+ | print "-----Finally getting started----------" | ||
+ | print "---------------" | ||
statelist = [ initialState ] | statelist = [ initialState ] |
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