year2018/
day07.rs

1use utils::bit::BitIterator;
2use utils::prelude::*;
3
4/// Scheduling steps with dependencies.
5#[derive(Clone, Debug)]
6pub struct Day07 {
7    steps: u32,
8    requirements: [u32; 26],
9    workers: usize,
10    base_duration: u32,
11}
12
13impl Day07 {
14    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
15        let step = parser::byte_range(b'A'..=b'Z').map(|x| x - b'A');
16
17        let mut steps = 0u32;
18        let mut requirements = [0u32; 26];
19        for item in step
20            .with_prefix("Step ")
21            .with_suffix(" must be finished before step ")
22            .then(step.with_suffix(" can begin."))
23            .with_suffix(parser::eol())
24            .parse_iterator(input)
25        {
26            let (first, second) = item?;
27            steps |= (1 << first) | (1 << second);
28            requirements[second as usize] |= 1 << first;
29        }
30
31        Ok(Self {
32            steps,
33            requirements,
34            workers: match input_type {
35                InputType::Example => 2,
36                InputType::Real => 5,
37            },
38            base_duration: match input_type {
39                InputType::Example => 1,
40                InputType::Real => 61,
41            },
42        })
43    }
44
45    #[must_use]
46    pub fn part1(&self) -> String {
47        let mut sequence = String::with_capacity(26);
48        let mut todo = self.steps;
49        while todo != 0 {
50            let (s, bit) = BitIterator::ones(todo)
51                .find(|&(r, _)| self.requirements[r as usize] & todo == 0)
52                .expect("no valid sequence");
53            todo &= !bit;
54            sequence.push((b'A' + s as u8) as char);
55        }
56        sequence
57    }
58
59    #[must_use]
60    pub fn part2(&self) -> u32 {
61        let mut pending = self.steps;
62        let mut incomplete = self.steps;
63        let mut second = 0;
64        let mut in_progress = Vec::with_capacity(self.workers);
65
66        while incomplete != 0 {
67            for (s, bit) in BitIterator::ones(pending)
68                .filter(|&(s, _)| self.requirements[s as usize] & incomplete == 0)
69                .take(self.workers - in_progress.len())
70            {
71                pending &= !bit;
72                in_progress.push((second + self.base_duration + s, bit));
73            }
74
75            (second, _) = *in_progress.iter().min().expect("no valid sequence");
76            in_progress.retain(|&(completed_at, bit)| {
77                if completed_at == second {
78                    incomplete &= !bit;
79                    false
80                } else {
81                    true
82                }
83            });
84        }
85
86        second
87    }
88}
89
90examples!(Day07 -> (&'static str, u32) [
91    {file: "day07_example0.txt", part1: "CABDFE", part2: 15},
92]);
year2018/day07.rs

year2018/
day07.rs
