# capacity 5,3
cap = [5,3]  
# state 5,3 current levels, start at [0,0]
start = [0,0]
# define goal of 4 gallons
goal = lambda xx: xx[0]+xx[1]==4

print( "================================")
print( "capacities cap", cap)
print( "start", start)
print( "goal xx[0]+xx[1]==4")
print( "================================")

################################
# actions
def fill5(state):
    return([cap[0],state[1]])

def empty5(state):
    return([0,state[1]])

def fill3(state):
    return([state[0],cap[1]])

def empty3(state):
    return([state[0],0])

def xfer53(state):
    # you can transfer min of what is in 5 into what is empty in 3
    d = min( state[0], cap[1]-state[1])
    return([ state[0]-d, state[1]+d])

def xfer35(state):
    # you can transfer min of what is in 3 into what is empty in 5
    d = min( state[1], cap[0]-state[0])
    return([ state[0]+d, state[1]-d])

# associate name with function for ease of calling
action={"fill5": fill5, "fill3": fill3, "empty5": empty5, "empty3": empty3, "xfer53": xfer53, "xfer35": xfer35}

################################

# start the exploration at start
state = start  
toexp = [ state ]

# store what we've seen
store = dict()
storekey = lambda xx: str(xx) # lists can't be keys so use string
store[ storekey(state) ] = ["start"]

# store all achieved goals
goallist = []

# breadth first search loop
while len(toexp)>0:

    # get the first item on list
    state = toexp[0]
    toexp= toexp[1:] # not efficient using list for queue

    print( "---- exploring state", state, "--------------------------------")

    # are we there?
    if goal(state):
        print( "!!!!goal!!!!", state, store[storekey(state)])
        goallist.append(str(state)+":"+str(store[storekey(state)]))

    # explore all actions in order in this state
    for name in action.keys():
        tryit = action[name](state)
        print( ">>tryit", state, name, tryit)

        if storekey(tryit) not in store:
            tostore = store[storekey(state)] + [name] # returns new list so store[state] is unchanged as desired
            store[storekey(tryit)] = tostore
            # newly seen to explore it
            toexp.append(tryit)
            print( ">>>storing", tryit, "=", tostore)
        else:
            tostore = store[storekey(state)]+ [name] # returns new list so store[state] is unchanged as desired
            print( ">>>already stored", tryit, "=", store[storekey(tryit)], "not updating to", tostore)

    print( "---- toexplore", toexp)

print( "**** all possible configurations")
for (k,v) in store.items():
    print( "store", k, v)

print( "**** all ways to get goal")
for gg in goallist:
    print( gg)