missionarycannibal.py

from collections import deque

initial_state = (3,3,0,0,0,0,0)
goal_state = (0,0, 3,3, 0, 0, 1)

def give_me_the_actions(state):
    action_set=[]
    a,b,c,d,e,f,g=state


    if g==0:
        m=a
        n=b
    else:
        m=c
        n=d

    capacity=e+f
    if capacity<2:
        if n>0:
            action_set+=["PickUpACannibal"]
        if (m>n and m>0) or m==1:
            action_set+=["PickUpAMissionary"]
        if capacity==0 and (m==2 and n>1):
            action_set+=["PickUpTwoMissionaries"]


    if e==1 and not (m==0 and n>1):
        action_set+=["DropOffAMissionary"]

    if e==2 and not (m==0 and n>2):
        action_set+=["DropOffTwoMissionaries"]

    ###
    if f>0 and (m>n or m==0):
        action_set+=["DropOffACannibal"]

    if e!=0 or f!=0:
        action_set+=["MoveBoat"]

    return action_set

def give_me_the_results(state, action):
    a,b,c,d,e,f,g = state
    if action is "PickUpAMissionary":
        return (a-(1-g),b,c-g,d,e+1,f,g)
    if action is "PickUpTwoMissionaries":
        return (a-2*(1-g),b,c-2*g,d,e+2,f,g)
    if action is "PickUpACannibal":
        return (a,b-(1-g),c,d-g,e,f+1,g)
    if action is "DropOffAMissionary":
        return (a+(1-g),b,c+g,d,e-1,f,g)
    if action is "DropOffTwoMissionaries":
        return (a+2*(1-g), b, c+2*g, d, e-2, f, g)
    if action is "DropOffACannibal":
        return (a,b+(1-g),c,d+g,e,f-1,g)
    if action is "MoveBoat":
        return (a,b,c,d,e,f,(1-g))
    raise ValueError("Hello Please Help Me I'm Here")

def state_consistency_check(state):
    a,b,c,d,e,f,g=state
    assert (a>=0)
    assert (b>=0)
    assert (c>=0)
    assert (d>=0)
    assert (e>=0)
    assert (f>=0)
    assert (g>=0)
    assert (a+c+e==3)
    assert (b+d+f==3)
    assert (a>=b or a==0)
    assert (c>=d or c==0)

def readable_state(state):
    a,b,c,d,e,f,g=state
    if g==0:
        return "M"*a+"C"*b+"("+"M"*e+"C"*f+")"+"        "+"M"*c + "C"*d
    else:
        return "M"*a+"C"*b+"        "+"("+"M"*e+"C"*f+")"+"M"*c + "C"*d

def BFS_missionary_cannibal(initial_state, debug=False, readable_print=True):
    fringe=deque([initial_state])
    discovered_from={}
    cnt=0
    discovered_from[initial_state]=None
    while len(fringe)>0:
        state=fringe.pop()
        applicable_actions=give_me_the_actions(state)
        if debug:
            print(readable_state(state), applicable_actions,state)

        if state == goal_state:
            path=[]
            while state is not None:
                path.append(state)
                state=discovered_from[state]
            path.reverse()
            if not readable_print:
                return path
            else:
                for state in path:
                    print(readable_state(state))
        for action in applicable_actions:
            child_state=give_me_the_results(state, action)
            state_consistency_check(child_state)
            if child_state not in discovered_from:
                discovered_from[child_state]=state
                fringe.appendleft(child_state)
        cnt+=1
        if debug and cnt%100==0:
            print("Running ",cnt)

if __name__ == '__main__':
    BFS_missionary_cannibal(initial_state, readable_print=True)