aoc/year2019/
day14.rs

1//! # Space Stoichiometry
2//!
3//! Sorting the reactions in [topological order](https://en.wikipedia.org/wiki/Topological_sorting)
4//! from `FUEL` at the start to `ORE` at the end, allows us to process each reaction only once.
5use crate::util::hash::*;
6use crate::util::iter::*;
7use crate::util::parse::*;
8use std::cmp::Ordering;
9use std::iter::repeat_with;
10
11struct Ingredient {
12    amount: u64,
13    chemical: usize,
14}
15
16pub struct Reaction {
17    amount: u64,
18    chemical: usize,
19    ingredients: Vec<Ingredient>,
20}
21
22/// To speed things up when processing, we use a temporary map to convert chemical names into
23/// contiguous indices.
24pub fn parse(input: &str) -> Vec<Reaction> {
25    let lines: Vec<_> = input.lines().collect();
26
27    let mut reactions: Vec<_> = repeat_with(|| {
28        Reaction {
29            amount: 0,
30            chemical: 1, // Default to ORE, other chemicals will overwrite.
31            ingredients: Vec::new(),
32        }
33    })
34    .take(lines.len() + 1)
35    .collect();
36
37    // Assign FUEL and ORE known indices as we'll need to look them up later.
38    let mut indices = FastMap::new();
39    indices.insert("FUEL", 0);
40    indices.insert("ORE", 1);
41
42    for line in lines {
43        let mut tokens = line
44            .split(|c: char| !c.is_ascii_alphanumeric())
45            .filter(|s| !s.is_empty())
46            .rev()
47            .chunk::<2>();
48
49        // Assigns other indices in the arbitrary order that chemicals are encountered.
50        let [kind, amount] = tokens.next().unwrap();
51        let size = indices.len();
52        let chemical = *indices.entry(kind).or_insert(size);
53
54        let reaction = &mut reactions[chemical];
55        reaction.amount = amount.unsigned();
56        reaction.chemical = chemical;
57
58        for [kind, amount] in tokens {
59            let amount = amount.unsigned();
60            let size = indices.len();
61            let chemical = *indices.entry(kind).or_insert(size);
62            reaction.ingredients.push(Ingredient { amount, chemical });
63        }
64    }
65
66    // Sort reactions in topological order
67    let mut order = vec![0; reactions.len()];
68    topological(&reactions, &mut order, 0, 0);
69    reactions.sort_unstable_by_key(|r| order[r.chemical]);
70    reactions
71}
72
73/// Calculate the amount of ore needed for 1 fuel. This will be the most ore needed per unit of
74/// fuel. Larger amounts of fuel can use some of the leftover chemicals from intermediate reactions.
75pub fn part1(input: &[Reaction]) -> u64 {
76    ore(input, 1)
77}
78
79/// Find the maximum amount of fuel possible from 1 trillion ore with an efficient binary search.
80pub fn part2(input: &[Reaction]) -> u64 {
81    let threshold = 1_000_000_000_000;
82    let mut start = 1_u64;
83    let mut end = threshold;
84
85    while start != end {
86        let middle = (start + end).div_ceil(2);
87
88        match ore(input, middle).cmp(&threshold) {
89            Ordering::Greater => end = middle - 1,
90            _ => start = middle,
91        }
92    }
93
94    start
95}
96
97/// Sort reactions in topological order from FUEL at the root to ORE at the leaves. Reactions may
98/// occur more than once at different depths in the graph, so we take the maximum depth.
99fn topological(reactions: &[Reaction], order: &mut [usize], chemical: usize, depth: usize) {
100    order[chemical] = order[chemical].max(depth);
101
102    for ingredient in &reactions[chemical].ingredients {
103        topological(reactions, order, ingredient.chemical, depth + 1);
104    }
105}
106
107/// Run the reactions to find ore needed. Each chemical is processed only once, so we don't need
108/// to track excess values of intermediate chemicals.
109fn ore(reactions: &[Reaction], amount: u64) -> u64 {
110    let mut total = vec![0; reactions.len()];
111    total[0] = amount;
112
113    for reaction in &reactions[..reactions.len() - 1] {
114        let multiplier = total[reaction.chemical].div_ceil(reaction.amount);
115
116        for ingredient in &reaction.ingredients {
117            total[ingredient.chemical] += multiplier * ingredient.amount;
118        }
119    }
120
121    total[1]
122}
aoc/year2019/day14.rs

aoc/year2019/
day14.rs
