aoc/year2018/
day07.rs

1//! # The Sum of Its Parts
2//!
3//! Part one is a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting)
4//! of the steps based on the dependencies between them.
5use 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 = FastMap::new();
18
19    for line in input.lines().map(str::as_bytes) {
20        // Each step is a single uppercase letter.
21        let from = line[5];
22        let to = line[36];
23
24        // Add all steps that depend on this one to children vec.
25        let step = steps.entry(from).or_insert(Step::default());
26        step.children.push(to);
27
28        // Count how many steps must finish before this step is ready.
29        // We only need the total count, the exact steps are not necessary.
30        let step = steps.entry(to).or_insert(Step::default());
31        step.remaining += 1;
32    }
33
34    steps
35}
36
37pub fn part1(input: &Input) -> String {
38    // Move all steps with no dependencies to the `ready` map. A `BTreeMap` is sorted by key
39    // so will retrieve steps in alphabetical order.
40    let mut ready = BTreeMap::new();
41    let mut blocked = FastMap::new();
42
43    for (key, step) in input.clone() {
44        if step.remaining == 0 {
45            ready.insert(key, step);
46        } else {
47            blocked.insert(key, step);
48        }
49    }
50
51    let mut done = String::new();
52
53    while let Some((key, step)) = ready.pop_first() {
54        // Keep track of the order of completed tasks.
55        done.push(key as char);
56
57        // For each dependent step, decrease the remaining count by one. Once a step reaches zero
58        // then all its dependencies have been completed and we can move it to the `ready` map.
59        for key in step.children {
60            let mut step = blocked.remove(&key).unwrap();
61            step.remaining -= 1;
62
63            if step.remaining == 0 {
64                ready.insert(key, step);
65            } else {
66                blocked.insert(key, step);
67            }
68        }
69    }
70
71    done
72}
73
74pub fn part2(input: &Input) -> u32 {
75    part2_testable(input, 5, 60)
76}
77
78pub fn part2_testable(input: &Input, max_workers: usize, base_duration: u32) -> u32 {
79    // Same as part one, move all tasks that are root nodes to the `ready` map.
80    let mut ready = BTreeMap::new();
81    let mut blocked = FastMap::new();
82
83    for (key, step) in input.clone() {
84        if step.remaining == 0 {
85            ready.insert(key, step);
86        } else {
87            blocked.insert(key, step);
88        }
89    }
90
91    // Loop until there are no more steps available and all workers are idle.
92    let mut time = 0;
93    let mut workers = Vec::new();
94
95    while !ready.is_empty() || !workers.is_empty() {
96        // Assign any steps to available workers until one or the other runs out first.
97        while !ready.is_empty() && workers.len() < max_workers {
98            let (key, step) = ready.pop_first().unwrap();
99            let finish = time + base_duration + (key - 64) as u32;
100
101            // Sort workers in reverse order, so that the worker that will finish first is at
102            // the end of the vec.
103            workers.push((finish, step));
104            workers.sort_unstable_by_key(|(time, _)| u32::MAX - time);
105        }
106
107        // Fast forward time until the earliest available worker finishes their step.
108        // This may not unblock a dependent step right away in which case the outer loop will
109        // bring things back here for another worker to complete.
110        let (finish, step) = workers.pop().unwrap();
111        time = finish;
112
113        // Update dependent tasks the same as part one.
114        for key in step.children {
115            let mut step = blocked.remove(&key).unwrap();
116            step.remaining -= 1;
117
118            if step.remaining == 0 {
119                ready.insert(key, step);
120            } else {
121                blocked.insert(key, step);
122            }
123        }
124    }
125
126    time
127}
aoc/year2018/day07.rs

aoc/year2018/
day07.rs
