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. As there are only 26 possible different
5//! steps, we can use bitmasks to store the dependency graph, enabling extremely quick lookup.
6use std::cmp::Reverse;
7
8use crate::util::bitset::*;
9
10type Input = [Step; 26];
11
12#[derive(Clone, Copy, Default)]
13pub struct Step {
14    todo: bool,
15    from: u32,
16    to: u32,
17}
18
19pub fn parse(input: &str) -> Input {
20    let mut steps = [Step::default(); 26];
21
22    for line in input.as_bytes().chunks(49) {
23        // Each step is a single uppercase letter.
24        let from = to_index(line[5]);
25        let to = to_index(line[36]);
26
27        // Track dependencies as bitmasks.
28        steps[from].todo = true;
29        steps[from].to |= 1 << to;
30
31        steps[to].todo = true;
32        steps[to].from |= 1 << from;
33    }
34
35    steps
36}
37
38pub fn part1(input: &Input) -> String {
39    let mut steps = *input;
40    let mut done = String::new();
41
42    // Find next available step in alphabetical order.
43    while let Some(i) = next_ready(&steps) {
44        // Prevent this step from being considered again.
45        steps[i].todo = false;
46
47        // Keep track of the order of completed tasks.
48        done.push(from_index(i));
49
50        // For each dependent step, remove this step from the remaining required steps.
51        for j in steps[i].to.biterator() {
52            steps[j].from ^= 1 << i;
53        }
54    }
55
56    done
57}
58
59pub fn part2(input: &Input) -> usize {
60    part2_testable(input, 5, 60)
61}
62
63pub fn part2_testable(input: &Input, max_workers: usize, base_duration: usize) -> usize {
64    let mut steps = *input;
65    let mut time = 0;
66    let mut workers = Vec::new();
67
68    // Loop until there are no more steps available and all workers are idle.
69    while next_ready(&steps).is_some() || !workers.is_empty() {
70        // Assign any steps to available workers until one or the other runs out first.
71        while let Some(i) = next_ready(&steps)
72            && workers.len() < max_workers
73        {
74            // Prevent this step from being considered again.
75            steps[i].todo = false;
76
77            // Add task duration based on step.
78            let finish = time + base_duration + i + 1;
79
80            // Sort workers in reverse order, so that the worker that will finish first is at
81            // the end of the vec.
82            workers.push((finish, i));
83            workers.sort_unstable_by_key(|&(finish, _)| Reverse(finish));
84        }
85
86        // Fast forward time until the earliest available worker finishes their step.
87        // This may not unblock a dependent step right away, in which case the outer loop will
88        // bring things back here for another worker to complete.
89        let (finish, i) = workers.pop().unwrap();
90        time = finish;
91
92        // Update dependent tasks the same as part one.
93        for j in steps[i].to.biterator() {
94            steps[j].from ^= 1 << i;
95        }
96    }
97
98    time
99}
100
101fn to_index(b: u8) -> usize {
102    usize::from(b - b'A')
103}
104
105fn from_index(i: usize) -> char {
106    char::from(i as u8 + b'A')
107}
108
109fn next_ready(steps: &[Step]) -> Option<usize> {
110    steps.iter().position(|step| step.todo && step.from == 0)
111}
aoc/year2018/day07.rs

aoc/year2018/
day07.rs
