Skip to main content

year2019/
day14.rs

1use std::num::NonZeroU32;
2use utils::hash::IndexedMap;
3use utils::prelude::*;
4use utils::str::TinyStr8;
5
6/// Calculating the maximum output from a process chain.
7#[derive(Clone, Debug)]
8pub struct Day14 {
9    order: Vec<usize>,
10    reactions: Vec<Reaction>,
11}
12
13#[derive(Clone, Debug)]
14struct Reaction {
15    output_amount: NonZeroU32,
16    inputs: Vec<Input>,
17}
18
19#[derive(Clone, Copy, Debug)]
20struct Input {
21    index: usize,
22    amount: NonZeroU32,
23}
24
25const ORE: usize = 0;
26const FUEL: usize = 1;
27const PART2_LIMIT: u64 = 1_000_000_000_000;
28
29impl Day14 {
30    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
31        let component =
32            parser::nonzero_u32().then(parser::tinystr8(u8::is_ascii_uppercase).with_prefix(b' '));
33        let reaction = component
34            .repeat(", ", 1)
35            .then(component.with_prefix(" => "))
36            .with_consumed()
37            .with_eol();
38
39        let mut reactions = IndexedMap::new();
40        reactions.intern(const { TinyStr8::from_const(b"ORE") });
41        reactions.intern(const { TinyStr8::from_const(b"FUEL") });
42        reactions[ORE] = Some(Reaction {
43            output_amount: NonZeroU32::MIN,
44            inputs: Vec::new(),
45        });
46
47        for item in reaction.parse_iterator(input) {
48            let ((inputs, (output_amount, output_index)), line) = item?;
49
50            let output = reactions.intern(output_index);
51            let inputs = inputs
52                .into_iter()
53                .map(|(amount, name)| Input {
54                    index: reactions.intern(name),
55                    amount,
56                })
57                .collect();
58
59            if output == ORE {
60                return Err(InputError::new(
61                    input,
62                    line,
63                    "expected ORE to be an input only",
64                ));
65            }
66            if reactions[output].is_some() {
67                return Err(InputError::new(
68                    input,
69                    line,
70                    "duplicate reaction for chemical",
71                ));
72            }
73
74            reactions[output] = Some(Reaction {
75                output_amount,
76                inputs,
77            });
78        }
79
80        let Some(reactions): Option<Vec<Reaction>> = reactions.into_values().collect() else {
81            return Err(InputError::new(
82                input,
83                0,
84                "expected every chemical to have a reaction",
85            ));
86        };
87
88        let Some(order) = Self::reaction_order(&reactions) else {
89            return Err(InputError::new(input, 0, "expected acyclic reaction graph"));
90        };
91
92        Ok(Self { order, reactions })
93    }
94
95    fn reaction_order(reactions: &[Reaction]) -> Option<Vec<usize>> {
96        #[derive(Clone, Copy, Debug)]
97        enum State {
98            Unvisited,
99            Visiting,
100            Done,
101        }
102
103        fn depth(
104            reactions: &[Reaction],
105            chemical: usize,
106            state: &mut [State],
107            depths: &mut [usize],
108        ) -> Option<usize> {
109            match state[chemical] {
110                State::Done => Some(depths[chemical]),
111                State::Visiting => None,
112                State::Unvisited if chemical == ORE => Some(depths[chemical]),
113                State::Unvisited => {
114                    state[chemical] = State::Visiting;
115
116                    let mut max_input_depth = 0;
117                    for input in &reactions[chemical].inputs {
118                        max_input_depth =
119                            max_input_depth.max(depth(reactions, input.index, state, depths)?);
120                    }
121                    depths[chemical] = max_input_depth + 1;
122
123                    state[chemical] = State::Done;
124                    Some(depths[chemical])
125                }
126            }
127        }
128
129        let mut state = vec![State::Unvisited; reactions.len()];
130        let mut depths = vec![0; reactions.len()];
131        depth(reactions, FUEL, &mut state, &mut depths)?;
132
133        let mut order = (1..reactions.len())
134            .filter(|&i| matches!(state[i], State::Done))
135            .collect::<Vec<_>>();
136        order.sort_unstable_by_key(|&i| depths[i]);
137
138        Some(order)
139    }
140
141    #[must_use]
142    pub fn part1(&self) -> u64 {
143        self.ore_needed(1)
144    }
145
146    #[must_use]
147    pub fn part2(&self) -> u64 {
148        // Using a binary search in a window around PART2_LIMIT instead of from 1 to PART2_LIMIT
149        // reduces ore_needed calls from 40 (log2(PART2_LIMIT)) to ~25
150        let mut lower = PART2_LIMIT / self.ore_needed(1);
151        let mut upper = 2 * lower.max(1);
152
153        while self.ore_needed(upper) <= PART2_LIMIT {
154            lower = upper;
155            upper *= 2;
156        }
157
158        while lower + 1 < upper {
159            let middle = lower.midpoint(upper);
160            if self.ore_needed(middle) <= PART2_LIMIT {
161                lower = middle;
162            } else {
163                upper = middle;
164            }
165        }
166
167        lower
168    }
169
170    #[inline]
171    fn ore_needed(&self, fuel_amount: u64) -> u64 {
172        let mut demand = vec![0u64; self.reactions.len()];
173        demand[FUEL] = fuel_amount;
174
175        for &chemical in self.order.iter().rev() {
176            let needed = demand[chemical];
177            let reaction = &self.reactions[chemical];
178            let batches = needed.div_ceil(u64::from(reaction.output_amount.get()));
179            for input in &reaction.inputs {
180                demand[input.index] += u64::from(input.amount.get()) * batches;
181            }
182        }
183
184        demand[ORE]
185    }
186}
187
188examples!(Day14 -> (u64, u64) [
189    {file: "day14_example0.txt", part1: 31},
190    {file: "day14_example1.txt", part1: 165},
191    {file: "day14_example2.txt", part1: 13312, part2: 82892753},
192    {file: "day14_example3.txt", part1: 180697, part2: 5586022},
193    {file: "day14_example4.txt", part1: 2210736, part2: 460664},
194]);