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

aoc/year2019/
day14.rs
