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    let mut reactions: Vec<_> = repeat_with(|| {
27        Reaction {
28            amount: 0,
29            chemical: 1, // Default to ORE, other chemicals will overwrite.
30            ingredients: Vec::new(),
31        }
32    })
33    .take(lines.len() + 1)
34    .collect();
35
36    // Assign FUEL and ORE known indices as we'll need to look them up later.
37    let mut indices = FastMap::new();
38    indices.insert("FUEL", 0);
39    indices.insert("ORE", 1);
40
41    for line in lines {
42        let mut tokens = line
43            .split(|c: char| !c.is_ascii_alphanumeric())
44            .filter(|s| !s.is_empty())
45            .rev()
46            .chunk::<2>();
47
48        // Assigns other indices in the arbitrary order that chemicals are encountered.
49        let [kind, amount] = tokens.next().unwrap();
50        let size = indices.len();
51        let chemical = *indices.entry(kind).or_insert(size);
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 amount = amount.unsigned();
59            let size = indices.len();
60            let chemical = *indices.entry(kind).or_insert(size);
61            reaction.ingredients.push(Ingredient { amount, chemical });
62        }
63    }
64
65    // Sort reactions in topological order
66    let mut order = vec![0; reactions.len()];
67    topological(&reactions, &mut order, 0, 0);
68    reactions.sort_unstable_by_key(|r| order[r.chemical]);
69    reactions
70}
71
72/// Calculate the amount of ore needed for 1 fuel. This will be the most ore needed per unit of
73/// fuel. Larger amounts of fuel can use some of the leftover chemicals from intermediate reactions.
74pub fn part1(input: &[Reaction]) -> u64 {
75    ore(input, 1)
76}
77
78/// Find the maximum amount of fuel possible from 1 trillion ore with an efficient binary search.
79pub fn part2(input: &[Reaction]) -> u64 {
80    let threshold = 1_000_000_000_000;
81    let mut start = 1_u64;
82    let mut end = threshold;
83
84    while start != end {
85        let middle = (start + end).div_ceil(2);
86
87        if ore(input, middle) > threshold {
88            end = middle - 1;
89        } else {
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
