""" 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