In [48]:

    

from collections import namedtuple
from queue import Queue
import itertools
import copy
from functools import reduce
import operator


    

In [19]:

    

BucketGameState = namedtuple('BucketGameState', ['bucketCapacityTuple', 'pathToPresentTuple'])


    

In [20]:

    

def genarateNextMoves(presentBucketState, bucketCapacities):
    assert len(presentBucketState) == len(bucketCapacities)
    assert all(present <= capacity for present, capacity in zip(presentBucketState, bucketCapacities))
    
    validNextBucketStates = set()
    
    # fill up any bucket from Universe
    # empty any bucket to Universe
    for ind,capacity in enumerate(bucketCapacities):
        nextBucketState = list(presentBucketState)
        nextBucketState[ind] = capacity
        validNextBucketStates.add(tuple(nextBucketState))
        assert all(present <= capacity for present, capacity in zip(nextBucketState, bucketCapacities))
        nextBucketState[ind] = 0
        validNextBucketStates.add(tuple(nextBucketState))
        assert all(present <= capacity for present, capacity in zip(nextBucketState, bucketCapacities))

    # transfer contents from b1 to b2 till b1 empty
    # transfer contents from b1 to b2 till b2 full{}
    numBucket = len(bucketCapacities)
    for b1,b2 in itertools.permutations(range(numBucket),2):
        spaceInb2 = bucketCapacities[b2] - presentBucketState[b2]
        if spaceInb2>=presentBucketState[b1]:
            nextBucketState = list(presentBucketState)
            nextBucketState[b2] = presentBucketState[b2] + presentBucketState[b1]
            nextBucketState[b1] = 0
            assert sum(nextBucketState)==sum(presentBucketState)
            assert all(present <= capacity for present, capacity in zip(nextBucketState, bucketCapacities))
            validNextBucketStates.add(tuple(nextBucketState))
        elif spaceInb2<presentBucketState[b1]:
            nextBucketState = list(presentBucketState)
            nextBucketState[b2] = bucketCapacities[b2]
            nextBucketState[b1] = presentBucketState[b1] - spaceInb2
            assert sum(nextBucketState)==sum(presentBucketState)
            assert all(present <= capacity for present, capacity in zip(nextBucketState, bucketCapacities))
            validNextBucketStates.add(tuple(nextBucketState))
    
    return validNextBucketStates


    

In [21]:

    

pbs = (0,0,0)
bc = (2,3,4)
print(genarateNextMoves(pbs, bc))

pbs = (1,1,1)
bc = (2,3,4)
print(genarateNextMoves(pbs, bc))

pbs = (0,0,4)
bc = (2,3,4)
genarateNextMoves(pbs, bc)


    

    




{(0, 3, 0), (0, 0, 0), (2, 0, 0), (0, 0, 4)}
{(1, 1, 0), (2, 1, 0), (0, 1, 1), (0, 1, 2), (2, 1, 1), (1, 3, 1), (1, 0, 2), (1, 0, 1), (1, 2, 0), (2, 0, 1), (0, 2, 1), (1, 1, 4)}






    
Out[21]:





{(0, 0, 0), (0, 0, 4), (0, 3, 1), (0, 3, 4), (2, 0, 2), (2, 0, 4)}

In [52]:

    

class BucketGame:
    def __init__(self, bucketCapacity, targetVolume):
        self.__bucketCapacityTuple = tuple(bucketCapacity)
        self.__targetVolume = targetVolume
        self.__exploredBucketStates = set()
        self.__statesToExploreQueue = Queue()
        self.__solution = None

    def __isSolved(self, bucketState):
        return sum(bucketState) == self.__targetVolume
    
    def solve(self):
        if sum(self.__bucketCapacityTuple) < self.__targetVolume:
            return None
        if any(bucketCapacity<=0 for bucketCapacity in self.__bucketCapacityTuple):
            return None
        
        firstState = BucketGameState(bucketCapacityTuple=tuple([0]*len(self.__bucketCapacityTuple)), pathToPresentTuple=[])
        self.__statesToExploreQueue.put_nowait(firstState)
        while self.__statesToExploreQueue.qsize()>0 and self.__solution is None:
            self.__solve()
        return self.__solution
        
    def __solve(self):
        assert self.__statesToExploreQueue.qsize()>0
        presentState = self.__statesToExploreQueue.get_nowait()
        presentBucketState = presentState.bucketCapacityTuple
        
        if presentBucketState in self.__exploredBucketStates:
            return
        elif self.__isSolved(presentBucketState):
            self.__solution = presentState
            return
        else:
            self.__exploredBucketStates.add(presentBucketState)
            pathToNextTuple = copy.deepcopy(presentState.pathToPresentTuple)
            pathToNextTuple.append(presentBucketState)
            futureBucketStates = genarateNextMoves(presentBucketState, self.__bucketCapacityTuple)
            for futureBucketState in futureBucketStates - self.__exploredBucketStates:
                futureState = BucketGameState(bucketCapacityTuple=tuple(futureBucketState),
                                              pathToPresentTuple=pathToNextTuple)
                self.__statesToExploreQueue.put_nowait(futureState)


    

In [59]:

    

bucketCapacities = [7,11]
targetVolume = 6
bg = BucketGame(bucketCapacities, targetVolume)
solution = bg.solve()
pathLength = len(solution.pathToPresentTuple)
print(solution)


    

    




BucketGameState(bucketCapacityTuple=(6, 0), pathToPresentTuple=[(0, 0), (7, 0), (0, 7), (7, 7), (3, 11), (3, 0), (0, 3), (7, 3), (0, 10), (7, 10), (6, 11)])

In [54]:

    

possibleStates = reduce(operator.mul, (i+1 for i in bucketCapacities))
exploredStates = len(bg._BucketGame__exploredBucketStates)
print("possibleStates = ",possibleStates)
print("exploredStates = ",exploredStates)


    

    




possibleStates =  96
exploredStates =  23

In [66]:

    

bucketCapacities = [7,11]
for targetVolume in range(sum(bucketCapacities)+1):
    bg = BucketGame(bucketCapacities, targetVolume)
    solution = bg.solve()
    pathLength = len(set(solution.pathToPresentTuple+[solution.bucketCapacityTuple]))-1 if solution is not None else None
    print(targetVolume,pathLength)


    

    




0 0
1 9
2 15
3 5
4 3
5 13
6 11
7 1
8 7
9 17
10 7
11 1
12 11
13 13
14 3
15 5
16 15
17 9
18 2

In [67]:

    

bucketCapacities = [2,4]
for targetVolume in range(sum(bucketCapacities)+1):
    bg = BucketGame(bucketCapacities, targetVolume)
    solution = bg.solve()
    pathLength = len(set(solution.pathToPresentTuple+[solution.bucketCapacityTuple]))-1 if solution is not None else None
    print(targetVolume,pathLength)


    

    




0 0
1 None
2 1
3 None
4 1
5 None
6 2

In [ ]: