1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

//! # Space Stoichiometry
//!
//! Sorting the reactions in [topological order](https://en.wikipedia.org/wiki/Topological_sorting)
//! from `FUEL` at the start to `ORE` at the end, allows us to process each reaction only once.
use crate::util::hash::*;
use crate::util::iter::*;
use crate::util::parse::*;
use std::cmp::Ordering;

struct Ingredient {
    amount: u64,
    chemical: usize,
}

pub struct Reaction {
    amount: u64,
    chemical: usize,
    ingredients: Vec<Ingredient>,
}

/// To speed things up when processing, we use a temporary map to convert chemical names into
/// contiguous indices.
pub fn parse(input: &str) -> Vec<Reaction> {
    let lines: Vec<_> = input.lines().collect();

    let mut reactions: Vec<_> = (0..lines.len() + 1)
        .map(|_| {
            Reaction {
                amount: 0,
                chemical: 1, // Default to ORE, other chemicals will overwrite.
                ingredients: Vec::new(),
            }
        })
        .collect();

    // Assign FUEL and ORE known indices as we'll need to look them up later.
    let mut indices = FastMap::new();
    indices.insert("FUEL", 0);
    indices.insert("ORE", 1);

    for line in lines {
        let mut tokens = line
            .split(|c: char| !c.is_ascii_alphanumeric())
            .filter(|s| !s.is_empty())
            .rev()
            .chunk::<2>();

        // Assigns other indices in the arbitrary order that chemicals are encountered.
        let [kind, amount] = tokens.next().unwrap();
        let size = indices.len();
        let chemical = *indices.entry(kind).or_insert(size);

        let reaction = &mut reactions[chemical];
        reaction.amount = amount.unsigned();
        reaction.chemical = chemical;

        for [kind, amount] in tokens {
            let amount = amount.unsigned();
            let size = indices.len();
            let chemical = *indices.entry(kind).or_insert(size);
            reaction.ingredients.push(Ingredient { amount, chemical });
        }
    }

    // Sort reactions in topological order
    let mut order = vec![0; reactions.len()];
    topological(&reactions, &mut order, 0, 0);
    reactions.sort_unstable_by_key(|r| order[r.chemical]);
    reactions
}

/// Calculate the amount of ore needed for 1 fuel. This will be the most ore needed per unit of
/// fuel. Larger amounts of fuel can use some of the leftover chemicals from intermediate reactions.
pub fn part1(input: &[Reaction]) -> u64 {
    ore(input, 1)
}

/// Find the maximum amount of fuel possible from 1 trillion ore with an efficient binary search.
pub fn part2(input: &[Reaction]) -> u64 {
    let threshold = 1_000_000_000_000;
    let mut start = 1;
    let mut end = threshold;

    while start < end {
        let middle = (start + end) / 2;

        match ore(input, middle).cmp(&threshold) {
            Ordering::Less => start = middle + 1,
            Ordering::Equal => return middle,
            Ordering::Greater => end = middle - 1,
        }
    }

    start
}

/// Sort reactions in topological order from FUEL at the root to ORE at the leaves. Reactions may
/// occur more than once at different depths in the graph, so we take the maximum depth.
fn topological(reactions: &[Reaction], order: &mut [usize], chemical: usize, depth: usize) {
    order[chemical] = order[chemical].max(depth);

    for ingredient in &reactions[chemical].ingredients {
        topological(reactions, order, ingredient.chemical, depth + 1);
    }
}

/// Run the reactions to find ore needed. Each chemical is processed only once, so we don't need
/// to track excess values of intermediate chemicals.
fn ore(reactions: &[Reaction], amount: u64) -> u64 {
    let mut total = vec![0; reactions.len()];
    total[0] = amount;

    for reaction in &reactions[..reactions.len() - 1] {
        let multiplier = total[reaction.chemical].div_ceil(reaction.amount);

        for ingredient in &reaction.ingredients {
            total[ingredient.chemical] += multiplier * ingredient.amount;
        }
    }

    total[1]
}