codepad

Language:

LEFT, RIGHT = 0, 1

def states():
    """Generate all possible states for the missionaries and cannibals 
    problem. This is an ugly way to do it :P"""
    r = range(0, 4)
    for a in r:
        for b in r:
            for c in r:
                for d in r:
                    if is_legal_state(a, b, c, d, LEFT):
                        yield a, b, c, d, LEFT
                    if is_legal_state(a, b, c, d, RIGHT):
                        yield a, b, c, d, RIGHT

def is_legal_state(m1, c1, m2, c2, side):
    """Check if a state appears to be legal."""
    if (c1 + c2) != 3 or (m1 + m2) != 3:
        return False
    elif m1 < 0 or m2 < 0 or c1 < 0 or c2 < 0:
        return False
    elif (m1 > 0 and m1 < c1) or (m2 > 0 and m2 < c2):
        return False
    elif (m1 + c1 == 6 and side == RIGHT) or (m2 + c2 == 6 and side == LEFT):
        return False
    return True

def gen_successor_states(m1, c1, m2, c2, side):
    """Generate all moves from a given state."""    
    if side is LEFT:
        yield m1-1, c1-1, m2+1, c2+1, RIGHT # 1 of both over
        yield m1-1, c1, m2+1, c2, RIGHT # 1 missionary over
        yield m1, c1-1, m2, c2+1, RIGHT # 1 cannibal over
        yield m1, c1-2, m2, c2+2, RIGHT # 2 cannibals over
        yield m1-2, c1, m2+2, c2, RIGHT # 2 missionaries over
    else:
        yield m1+1, c1+1, m2-1, c2-1, LEFT
        yield m1+1, c1, m2-1, c2, LEFT
        yield m1, c1+1, m2, c2-1, LEFT
        yield m1, c1+2, m2, c2-2, LEFT
        yield m1+2, c1, m2-2, c2, LEFT

def successors(state, legal_states):
    """Return all legal successor states."""
    states = set()
    for succ in gen_successor_states(*state):
        if is_legal_state(*succ):
            states.add(succ)
    return states

def state_label(state):
    """Create the label for each state."""
    
    return "(%3s%3s,%3s%3s,%s)" % (
        "M" * state[0], 
        "C" * state[1], 
        "M" * state[2], 
        "C" * state[3], 
        state[4] == LEFT and "<-" or "->"
    )

def print_state_space():
    "Generate the state space."
    
    reachable, legal_states = set(), set()
    prev_reached, next_reached = set(), set()
    initial, goal = (3, 3, 0, 0, LEFT), (0, 0, 3, 3, RIGHT)
    space = { }
    
    # generate the set of legal-looking states
    for state in states():
        legal_states.add(state)
    
    prev_reached.add(initial)
    prev_reached.add(goal)
    
    # generate all successors
    while len(prev_reached):
        next_reached.clear()
        for state in prev_reached:
            space[state] = successors(state, legal_states)
            reachable.add(state)
            
            # record newly reached
            next_reached.update(space[state])
        
        # update the various sets
        next_reached.difference_update(reachable)
        next_reached, prev_reached = prev_reached, next_reached
        reachable.update(prev_reached)
    
    # make it easier to print out the graph
    key = 1
    keys = { }
    for state in space:
        keys[state] = key
        key += 1
    
    # print out the DOT language version of the state space
    colors = {goal:" color=blue", initial:" color=green"}
    for state in space:
        print keys[state], "[label=\"%s\"%s]" \
            % (state_label(state), state in colors and colors[state] or "")
        
        for succ in space[state]:
            print keys[state], "->", keys[succ]
        print
        
print_state_space()

Private [?]

Run code