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

aoc/year2019/
day14.rs
