Explore a tree of states to find a goal state.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | ```
"""
A 'state tree' is (as its name implies) an object that represents a tree of
states. The tree is built by having an initial state (the 'root') and a
rule whereby child states can be reached from a parent state.
State trees are useful, for example, in solving puzzles where there are a
fixed set of moves from any given position, and a goal position which is
the solution. A couple of example puzzles are given below.
"""
from collections import deque
class StateTree(object):
"""
Representation of a tree of states.
States must be hashable (i.e., usable as dictionary keys---for example,
tuples). The initial(), reachable() and endcondtion() methods must be
subclassed. After that, the findpath() method will return a list of
states from the initial to an end state.
"""
def initial(self):
"Return the initial state."
raise NotImplementedError
def reachable(self, state):
"Yield states reachable from a given state."
raise NotImplementedError
def endcondition(self, state):
"Return whether state satisfies the end condition."
raise NotImplementedError
def findpath(self):
"Find and return shortest path from initial to end state."
# Get the initial state.
state = self.initial()
# Mapping of state to its parent, or None if initial.
parentmap = {state: None}
# Queue of states to examine.
queue = deque([state])
# Process each state in the queue.
while len(queue) > 0:
state = queue.popleft()
# Examine each new reachable state.
for child in self.reachable(state):
if child not in parentmap:
parentmap[child] = state
queue.append(child)
# If this state satisfies the end condition, return it.
if self.endcondition(state):
states = [state]
while parentmap[state] is not None:
state = parentmap[state]
states.insert(0, state)
return states
class BottlePuzzle(StateTree):
"""
There are three bottles, with capacities of 3, 5 and 8 litres. You can
pour the contents of one bottle into another until it's empty or the
other is full. How do you measure out 4 litres?
"""
# Bottle sizes.
sizes = (3, 5, 8)
# Possible pourings (from -> to).
pourings = ((0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1))
def initial(self):
return (0, 0, 8)
def reachable(self, state):
for a, b in self.pourings:
bottles = list(state)
# Get the amount poured from bottle A to bottle B.
poured = min(self.sizes[b] - bottles[b], bottles[a])
# If some was poured, yield the new state.
if poured > 0:
bottles[a] -= poured
bottles[b] += poured
yield tuple(bottles)
def endcondition(self, state):
return 4 in state
class FrogsAndToads(StateTree):
"""
The classic frogs-and-toads puzzle. An equal number of frogs and toads
face each other on a log, with a gap between them, and need to swap
places. Toads only move right, frogs only move left. A thing can move
into the gap, or jump over a different thing into the gap. How do they
do it?
"""
def initial(self):
return ('T', 'T', 'T', ' ', 'F', 'F', 'F')
def reachable(self, state):
for thing, move in (('T', 1), ('T', 2), ('F', -1), ('F', -2)):
pos = list(state)
# Find where the empty space is.
space = pos.index(' ')
# Find start position of the thing to move.
start = space - move
# If start position is out of bounds, or not of the right type,
# disallow it.
if not 0 <= start < len(pos) or pos[start] != thing:
continue
# If it's a jump, and the jumped thing isn't a different kind,
# disallow it.
if abs(move) == 2 and pos[(space + start) / 2] == thing:
continue
# Do the move and yield it.
pos[start], pos[space] = pos[space], pos[start]
yield tuple(pos)
def endcondition(self, state):
return state == ('F', 'F', 'F', ' ', 'T', 'T', 'T')
if __name__ == "__main__":
for puzzle in FrogsAndToads, BottlePuzzle:
print
print puzzle.__name__
print
for state in puzzle().findpath():
print " ", state
``` |

A 'state tree' is (as its name implies) an object that represents a tree of states. The tree is built by having an initial state (the 'root') and a rule whereby child states can be reached from a parent state.

State trees are useful, for example, in solving puzzles where there are a fixed set of moves from any given position, and a goal position which is the solution.

Tags: deque