k4st
-
Python,
pasted
on Oct 3:
|
|
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()
|
Output:
|
|
1 [label="(MMM C, CC,<-)"]
1 -> 2
1 -> 14
2 [label="(MMM , CCC,->)"]
2 -> 1
2 -> 3
3 [label="(MMM CC, C,<-)"]
3 -> 11
3 -> 2
3 -> 16
4 [label="( M C, MM CC,<-)"]
4 -> 9
4 -> 13
5 [label="( CC,MMM C,->)"]
5 -> 10
5 -> 6
6 [label="( MM CC, M C,<-)"]
6 -> 14
6 -> 5
7 [label="(MMMCCC, ,<-)" color=green]
7 -> 11
7 -> 15
7 -> 16
8 [label="( CC,MMM C,<-)"]
8 -> 9
8 -> 13
9 [label="( C,MMM CC,->)"]
9 -> 10
9 -> 4
9 -> 8
10 [label="( CCC,MMM ,<-)"]
10 -> 9
10 -> 5
11 [label="(MMM C, CC,->)"]
11 -> 3
11 -> 7
12 [label="( C,MMM CC,<-)"]
12 -> 13
13 [label="( ,MMMCCC,->)" color=blue]
13 -> 12
13 -> 4
13 -> 8
14 [label="( M C, MM CC,->)"]
14 -> 1
14 -> 6
15 [label="(MMM CC, C,->)"]
15 -> 7
16 [label="( MM CC, M C,->)"]
16 -> 3
16 -> 7
|
|