1use crate::util::hash::*;
6use std::collections::BTreeMap;
7
8type Input = FastMap<u8, Step>;
9
10#[derive(Clone, Default)]
11pub struct Step {
12 remaining: u32,
13 children: Vec<u8>,
14}
15
16pub fn parse(input: &str) -> Input {
17 let mut steps: Input = FastMap::new();
18
19 for line in input.lines().map(str::as_bytes) {
20 let from = line[5];
22 let to = line[36];
23
24 steps.entry(from).or_default().children.push(to);
26
27 steps.entry(to).or_default().remaining += 1;
30 }
31
32 steps
33}
34
35pub fn part1(input: &Input) -> String {
36 let mut ready = BTreeMap::new();
39 let mut blocked = FastMap::new();
40
41 for (key, step) in input.clone() {
42 if step.remaining == 0 {
43 ready.insert(key, step);
44 } else {
45 blocked.insert(key, step);
46 }
47 }
48
49 let mut done = String::new();
50
51 while let Some((key, step)) = ready.pop_first() {
52 done.push(key as char);
54
55 for key in step.children {
58 let mut step = blocked.remove(&key).unwrap();
59 step.remaining -= 1;
60
61 if step.remaining == 0 {
62 ready.insert(key, step);
63 } else {
64 blocked.insert(key, step);
65 }
66 }
67 }
68
69 done
70}
71
72pub fn part2(input: &Input) -> u32 {
73 part2_testable(input, 5, 60)
74}
75
76pub fn part2_testable(input: &Input, max_workers: usize, base_duration: u32) -> u32 {
77 let mut ready = BTreeMap::new();
79 let mut blocked = FastMap::new();
80
81 for (key, step) in input.clone() {
82 if step.remaining == 0 {
83 ready.insert(key, step);
84 } else {
85 blocked.insert(key, step);
86 }
87 }
88
89 let mut time = 0;
91 let mut workers = Vec::new();
92
93 while !ready.is_empty() || !workers.is_empty() {
94 while !ready.is_empty() && workers.len() < max_workers {
96 let (key, step) = ready.pop_first().unwrap();
97 let finish = time + base_duration + (key - 64) as u32;
98
99 workers.push((finish, step));
102 workers.sort_unstable_by_key(|(time, _)| u32::MAX - time);
103 }
104
105 let (finish, step) = workers.pop().unwrap();
109 time = finish;
110
111 for key in step.children {
113 let mut step = blocked.remove(&key).unwrap();
114 step.remaining -= 1;
115
116 if step.remaining == 0 {
117 ready.insert(key, step);
118 } else {
119 blocked.insert(key, step);
120 }
121 }
122 }
123
124 time
125}