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

aoc/year2018/
day07.rs
