text: """
  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)
  