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 std::iter::repeat_with;
6
7use crate::util::hash::*;
8use crate::util::iter::*;
9use crate::util::parse::*;
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    // Default chemical is ORE, other chemicals will overwrite.
28    let mut reactions: Vec<_> =
29        repeat_with(|| Reaction { amount: 0, chemical: 1, ingredients: Vec::new() })
30            .take(lines.len() + 1)
31            .collect();
32
33    // Assign FUEL and ORE known indices as we'll need to look them up later.
34    let mut indices = FastMap::new();
35    indices.insert("FUEL", 0);
36    indices.insert("ORE", 1);
37
38    let mut lookup = |s| {
39        let size = indices.len();
40        *indices.entry(s).or_insert(size)
41    };
42
43    for line in lines {
44        let mut tokens = line
45            .split(|c: char| !c.is_ascii_alphanumeric())
46            .filter(|s| !s.is_empty())
47            .rev()
48            .chunk::<2>();
49
50        // Assigns other indices in the arbitrary order that chemicals are encountered.
51        let [kind, amount] = tokens.next().unwrap();
52        let chemical = lookup(kind);
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 chemical = lookup(kind);
60            reaction.ingredients.push(Ingredient { amount: amount.unsigned(), chemical });
61        }
62    }
63
64    // Sort reactions in topological order.
65    let mut order = vec![0; reactions.len()];
66    topological(&reactions, &mut order, 0, 0);
67    reactions.sort_unstable_by_key(|r| order[r.chemical]);
68    reactions
69}
70
71/// Calculate the amount of ore needed for 1 fuel. This will be the most ore needed per unit of
72/// fuel. Larger amounts of fuel can use some of the leftover chemicals from intermediate reactions.
73pub fn part1(input: &[Reaction]) -> u64 {
74    ore(input, 1)
75}
76
77/// Find the maximum amount of fuel possible from 1 trillion ore with an efficient binary search.
78pub fn part2(input: &[Reaction]) -> u64 {
79    let threshold = 1_000_000_000_000;
80    let mut start = 1_u64;
81    let mut end = threshold;
82
83    while start != end {
84        let middle = (start + end).div_ceil(2);
85
86        if ore(input, middle) > threshold {
87            end = middle - 1;
88        } else {
89            start = middle;
90        }
91    }
92
93    start
94}
95
96/// Sort reactions in topological order from FUEL at the root to ORE at the leaves. Reactions may
97/// occur more than once at different depths in the graph, so we take the maximum depth.
98fn topological(reactions: &[Reaction], order: &mut [usize], chemical: usize, depth: usize) {
99    order[chemical] = order[chemical].max(depth);
100
101    for ingredient in &reactions[chemical].ingredients {
102        topological(reactions, order, ingredient.chemical, depth + 1);
103    }
104}
105
106/// Run the reactions to find ore needed. Each chemical is processed only once, so we don't need
107/// to track excess values of intermediate chemicals.
108fn ore(reactions: &[Reaction], amount: u64) -> u64 {
109    let mut total = vec![0; reactions.len()];
110    total[0] = amount;
111
112    for reaction in &reactions[..reactions.len() - 1] {
113        let multiplier = total[reaction.chemical].div_ceil(reaction.amount);
114
115        for ingredient in &reaction.ingredients {
116            total[ingredient.chemical] += multiplier * ingredient.amount;
117        }
118    }
119
120    total[1]
121}
aoc/year2019/day14.rs

aoc/year2019/
day14.rs
