AoC 2019 D14: Space Stoichiometry

C++ | Problem statement | Source code | Tags: RecursionBinary search

← Previous Back to AoC Index Next →

Part 1

Initially I simplified each recipe to "how much ORE is needed to produce 1 unit of X", but I realized that each reaction must be run in whole, so I need to account for leftovers. That is, if I have 10 ORE => 10 A and I need 7 A, I have to run the reaction once and have 3 A left, instead of using 7 ORE directly. This also makes memoization a bit tricky, because the number of ORE not just depends on the target chemical and amount, but also the current leftovers. In the end I forewent memoization and just did a straightforward recursive implementation:

long long num_ores(
    const std::map<std::string, Recipe> &recipes,
    const std::string &name,
    long long quantity,
    std::map<std::string, long long> &leftovers
);
cpp

Part 2

This problem just screams "binary search", since the relationship between FUEL produced and ORE consumed is monotonic, and the search space is huge. We just bisect the range [0, 1000000000000LL] (1 fuel requires more than 1 trillion ORES to 1 fuel only requires 1 ORE), each time taking the left half if the midpoint is not feasible with 1000000000000LL ores, and the right half otherwise. Technically we can shrink the range slightly, because we know that at least 1000000000000LL / ores_for_1_fuel fuel can be produced, but it doesn't really matter, since 1 trillion is just 40 iterations of bisections.

// [0..left] is feasible, [right..ore_cap] is not
long long left = 1;
long long right = ore_cap;
while (left <= right) {
    long long mid = (left + right) / 2;
    std::map<std::string, long long> leftovers;
    long long ores = num_ores(recipes, "FUEL", mid, leftovers);
    if (ores <= ore_cap) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
cpp

← Previous Back to AoC Index Next →