Advertisement
Guest User

Advent of Code day 7 part 2

a guest
Dec 10th, 2018
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.10 KB | None | 0 0
  1. from collections import defaultdict
  2. from heapq import heapify, heappop, heappush
  3. import re
  4. from string import ascii_uppercase
  5.  
  6. def day7_digraph():
  7.     out, in_ = defaultdict(set), defaultdict(set)
  8.     with open('7.txt') as f:
  9.         for line in f:
  10.             m = re.match(r'Step (.) must be finished before step (.)', line)
  11.             src, dest = m.groups()
  12.             out[src].add(dest)
  13.             in_[dest].add(src)
  14.     return out, in_
  15.  
  16. def day7_part2(workers=5, duration=60):
  17.     out, in_ = day7_digraph()
  18.     available_tasks = [t for t in out if not in_[t]]
  19.     heapify(available_tasks)
  20.     busy_workers = [(0, None)]
  21.     while busy_workers:
  22.         time, task = heappop(busy_workers)
  23.         for t in out[task]:
  24.             deps = in_[t]
  25.             deps.remove(task)
  26.             if not deps:
  27.                 heappush(available_tasks, t)
  28.         while available_tasks and len(busy_workers) < workers:
  29.             task = heappop(available_tasks)
  30.             finish = time + duration + ascii_uppercase.index(task) + 1
  31.             heappush(busy_workers, (finish, task))
  32.     return time
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement