Welcome, guest | Sign In | My Account | Store | Cart

Explore a tree of states to find a goal state.

Python, 146 lines
  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.