pouring water with bfs

pouring_water.py

from copy import copy

def ancesters(child, parents):
    """
    when given a child and a child->parent dict, returns all child's ancesters
    from youngest to oldest
    """
    yield child
    while parents.get(child):
        child = parents.get(child)
        yield child

class Container(object):
    """
    Represents a container containing water
    + and - are overloaded and serve to add water and to sub water from the container
    """
    def __init__(self, capacity, filled):
        self.capacity = capacity
        self.filled = filled
    
    def empty(self):
        return self.capacity - self.filled
        
    def __add__(self, quantity):
        if quantity > 0 : 
            assert quantity <= self.empty()
        else:             
            assert quantity <= self.filled
        self.filled += quantity
        return self
    
    def __sub__(self, quantity):
        return self + (-quantity)
        
    def __str__(self):
        return "%d" % self.filled
    
    def __repr__(self):
        return "%d" % self.filled
     
    @staticmethod
    def possible_to_pour(one, other):
        """
        Is there water in one is space in other ?
        """
        return one.filled > 0 and other.empty() > 0
    
    @staticmethod  
    def pour(one, other):
        """
        Returns two new containers with one poured into other
        """
        new_one, new_other = copy(one), copy(other)
        q = min(new_one.filled, new_other.empty())
        new_other += q
        new_one   -= q
        return new_one, new_other
        
class State(tuple):
    def _hash(self):
        return sum(i**10*v.filled for i,v in enumerate(self))
         
    def next_states(self):
        """
        Generate new states, pouring water between combinations of containers
        """
        pour, possible_to_pour = Container.pour, Container.possible_to_pour
        
        for i, first_container in enumerate(self):
          for j, second_container in enumerate(self):
            if j!=i and possible_to_pour(first_container, second_container):
                next_state = list(self)
                next_state[i], next_state[j] = pour(next_state[i], next_state[j])
                yield State(next_state)
            
    def _bfs(self, container, value, key):
        q = []
        q.append(self)
        
        seen = set()
        parents = dict()
        
        while len(q) > 0:
            s = q[0]
            del q[0]
            if key(s[container]) == value:
                yield ancesters(s, parents)
            else:
                for next_state in s.next_states():
                    h = next_state._hash()
                    if h not in seen:
                        seen.add(h)
                        q.append(next_state)
                        parents[next_state] = s
                
    def solve(self, container, value, key=lambda x: x.filled):
        return self._bfs(container, value, key)                
                                
c1 = Container(10, 0)
c2 = Container(7, 7)
c3 = Container(4, 4)

s = State([c1, c2, c3])
paths = s.solve(2, 2)
for p in paths:
    for s in p:
        print s
    print