In [55]:

    

l = ! cat input.txt | tr '\n' ';'
l = l[0].rstrip(';').split(';')
l = list(map(lambda v: (v[5], v[-12]), l))


    

In [56]:

    

def parse_list(l):
    letters = []
    for t in l:
        for i in [0, 1]:
            letters.append(t[i])
    letters = set(letters)
    requirements = {c: [] for c in letters}
    for t in l:
        requirements[t[1]].append(t[0])
    return requirements


    

In [3]:

    

def sequential(requirements):
    seq = []
    acc = requirements
    available = sorted([k for k in acc if len(acc[k]) == 0])
    while len(available) > 0:
        available = sorted(available)
        current = available.pop(0)
        seq.append(current)
        for k in acc:
            if current in acc[k]:
                acc[k].remove(current)
                if len(acc[k]) == 0:
                    available.append(k)
    return ''.join(seq)


    

In [4]:

    

test_list = [('C', 'A'), ('C', 'F'), ('A', 'B'), ('A', 'D'), ('B', 'E'), ('D', 'E'), ('F', 'E')]
test_requirements = parse_list(test_list)
sequential(test_requirements)


    

    
Out[4]:





'CABDFE'

In [5]:

    

requirements = parse_list(l)
sequential(requirements)


    

    
Out[5]:





'CGKMUWXFAIHSYDNLJQTREOPZBV'

In [64]:

    

def concurrent(requirements, n=5):
    
    acc = requirements
    workers = [(0, None) for _ in range(n)]  # time-to-finish & task
    ready = list(range(n))
    pending = list(alphabet)
    available = sorted([k for k in acc if len(acc[k]) == 0])
    time = 0
    while len(pending) > 0:
        
        # assign tasks to ready workers
        for i in ready:
            if len(available) > 0:
                task = available.pop(0)
                workers[i] = (cost[task] - 1, task)
        
        # time moves & check if there are complete tasks
        for i, w in enumerate(workers):
            if (w[0] == 0) and (w[1] is not None):
                pending.remove(w[1])
                
                # update requirements
                for k in acc:
                    if w[1] in acc[k]:
                        acc[k].remove(w[1])
                        if len(acc[k]) == 0:
                            available.append(k)
                            
                workers[i] = (0, None)
            
            if w[0] > 0:
                workers[i] = (w[0] - 1, w[1])
                
        # update ready workers
        ready = [i for i, w in enumerate(workers) if w == (0, None)]
        
        # increase time
        time += 1
        
    return time


    

In [65]:

    

alphabet = 'ABCDEF'
cost = dict(zip(alphabet, [i + 1 for i, _ in enumerate(alphabet)]))
test_requirements = parse_list(test_list)
concurrent(test_requirements, n=2)


    

    
Out[65]:





15

In [66]:

    

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
cost = dict(zip(alphabet, [60 + i + 1 for i, _ in enumerate(alphabet)]))


    

In [67]:

    

requirements = parse_list(l)
concurrent(requirements, n=5)


    

    
Out[67]:





1046