Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import defaultdict
- from heapq import heapify, heappop, heappush
- import re
- from string import ascii_uppercase
- def day7_digraph():
- out, in_ = defaultdict(set), defaultdict(set)
- with open('7.txt') as f:
- for line in f:
- m = re.match(r'Step (.) must be finished before step (.)', line)
- src, dest = m.groups()
- out[src].add(dest)
- in_[dest].add(src)
- return out, in_
- def day7_part2(workers=5, duration=60):
- out, in_ = day7_digraph()
- available_tasks = [t for t in out if not in_[t]]
- heapify(available_tasks)
- busy_workers = [(0, None)]
- while busy_workers:
- time, task = heappop(busy_workers)
- for t in out[task]:
- deps = in_[t]
- deps.remove(task)
- if not deps:
- heappush(available_tasks, t)
- while available_tasks and len(busy_workers) < workers:
- task = heappop(available_tasks)
- finish = time + duration + ascii_uppercase.index(task) + 1
- heappush(busy_workers, (finish, task))
- return time
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement