import itertools

machine_names = ["M1", "M2"]
num_tasks = 4

time_to_complete = {
    "M1":[5,3,5,4],
    "M2":[4,2,7,5]
}

price_to_do = {
    "M1":[5,4,2,6],
    "M2":[3,7,3,3]
}

switching_time = {
    ("M1","M1"):0,
    ("M1","M2"):1,
    ("M2","M1"):2,
    ("M2","M2"):0
}

switching_price = {
    ("M1","M1"):0,
    ("M1","M2"):2,
    ("M2","M1"):1,
    ("M2","M2"):0
}

#finds the total cost for a potential sequence of machine usages.
#can work using time or price - just insert whatever dicts are needed.
def total_cost(machine_seq, task_cost, switching_cost):
    cost = 0
    prev = None
    for task_idx, cur in enumerate(machine_seq):
        cost += task_cost[cur][task_idx]
        if prev != None:
            cost += switching_cost[(prev, cur)]
        prev = cur
    return cost

def total_price(machine_seq):
    return total_cost(machine_seq, price_to_do, switching_price)

def total_time(machine_seq):
    return total_cost(machine_seq, time_to_complete, switching_time)

def get_cheapest_sequence(max_allowable_time):
    valid_seqs = []
    #find all sequences that are completed by the deadline
    for candidate_seq in itertools.product(machine_names, repeat=num_tasks):
        if total_time(candidate_seq) <= max_allowable_time:
            valid_seqs.append(candidate_seq)

    if len(valid_seqs) == 0:
        return None

    #identify cheapest valid sequence
    return min(valid_seqs, key=total_price)

print get_cheapest_sequence(10000)