from math import factorial
global list_previous_jug_states
list_previous_jug_states = []
global list_running_count
list_running_count = []
global list_running_index
list_running_index  = []
global list_volumes
list_volumes = []
global list_jug_max
list_jug_max = []

class CreateJugs:
    #Create a new jug instance
    def __init__ (self,jug_name,jug_max):
        self.name = jug_name
        self.max = jug_max

        list_jug_max.append(self)

    @property
    def jug_max (self):
        return self.max


def set_fill_states (number_jugs, jug_max):
    #Create a list of binary starting states (e.g: 0,0,0,0....1,1,1,0 where 1 = MAX and 0 = empty)
    global list_binary_states
    list_binary_states = []
    for i in range (1<<number_jugs):
        binary_state =bin(i)[2:]
        binary_state ='0'*(number_jugs-len(binary_state))+binary_state
        list_binary_states.append(binary_state)
    list_binary_states = list_binary_states[0:len(list_binary_states)-1]

    #Create lists to hold previous states, running count for each jug, running index of previous positions
    #Running count: if start position is (binary): 1,1,0 that = 2
    #Running count: start 0,0,1 = 1



    #Sort list by number of 1s
    new_list = []
    for x in range (number_jugs):
        for item in list_binary_states:
            if item.count('1') ==  x:
                new_list.append(item)
                list_running_count.append(x)
    #Copy list back to origina function
    list_binary_states = new_list[:]

    #Now print all possible starting oreintations
    for n in range (len(list_binary_states)):
        jug_binary_state = list_binary_states[int(n)]
        jug_state = []
        for x in range (number_jugs):
            if int(jug_binary_state[x]) == 1:
                jug_state.append(list_jug_max[x].max)
            else:
                jug_state.append (0)
        list_previous_jug_states.append(jug_state)
        list_running_index.append([n])

def make_moves (jug_state,
                running_total, running_index,
                target_volume, number_jugs):
    for from_jug in range (number_jugs):
        from_jug_max = list_jug_max[from_jug].jug_max
        from_jug_state = jug_state[from_jug]

        for to_jug in range (number_jugs):
            if to_jug == from_jug: continue

            to_jug_max = list_jug_max[to_jug].jug_max
            to_jug_state = jug_state[to_jug]

            #Empty from_jug, ignore to_jug
            new_jug_state = jug_state [:]
            new_jug_state[from_jug] = 0
            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index)
            #Fill from_jug, ignore to_jug
            new_jug_state = jug_state [:]
            new_jug_state[from_jug] = from_jug_max
            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index)

            #Move as much from from_jug to to_jug
            if to_jug_state == to_jug_max: continue
            if from_jug_state == 0: continue
            if from_jug_state < (to_jug_max-to_jug_state):
                new_jug_state = jug_state [:]
                new_jug_state[from_jug] = 0
                new_jug_state[to_jug] = to_jug_state + from_jug_state
            else:
                amount_transfer = to_jug_max - to_jug_state
                new_jug_state = jug_state [:]
                new_jug_state[from_jug] = from_jug_state - amount_transfer
                new_jug_state[to_jug] = to_jug_state + amount_transfer

            if new_jug_state not in list_previous_jug_states:
                list_previous_jug_states.append(new_jug_state)
                list_running_count.append (running_total+1)
                new_index = [len(list_previous_jug_states)-1]
                list_running_index.append (running_index + new_index)

            for jug in new_jug_state:
                if jug == target_volume:
                    print ("Target reached in ", running_total + 1, "steps")
                    for item in running_index:
                        print (list_previous_jug_states[item])
                    print (new_jug_state)
                    return True


    return False, 0

if __name__ == "__main__":
    number_jugs = int(input("Please enter the number of jugs you have: "))
    #Set jug volumes
    for i in range (number_jugs):
        jug_volume = int(input(f"Please enter the volume of jug {i+1}: "))
        list_volumes.append(jug_volume)
    #Set target volume
    target_volume = int(input("Please enter the target volume: "))
    #Sort jugs in size order
    list_volumes.sort(reverse=True)
    #Create object instances
    for i in range (number_jugs):
        jug_name = "Jug" + str(i+1)
        CreateJugs (jug_name, list_volumes[i])
    # set_fill_states(number_jugs) #Set the fill states
    set_fill_states(number_jugs,list_volumes)
    #Continue iterating through jug_previous_state
    for item in list_previous_jug_states:
        jug_state = item

        index = list_previous_jug_states.index(item)
        running_total = list_running_count [index]
        running_index = list_running_index [index]
        is_destination = make_moves (jug_state,
                                    running_total,
                                    running_index,
                                    target_volume,
                                    number_jugs)

        if is_destination == True:
            print ("=====")
            break