1use std::num::NonZeroU32;
2use utils::hash::IndexedMap;
3use utils::prelude::*;
4use utils::str::TinyStr8;
5
6#[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 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]);