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

aoc/year2018/
day07.rs
