Our task today is to find the best substitutions to come up with the least amount of ore we need. This is a dependency graph, but with the twist of having to find substitutions in what amounts to be a constrained equation ($O\cdot{ore} >= F\cdot{feul}$).
We can keep track of how many input we still need to find reactions for, subtracting reactions as long as we haven't yet satisfied all the inputs. This can and should lead to negative numbers in the 'needs' column, where we produced too much of a specific output!
from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass
from math import ceil
from typing import Dict, Iterable, Tuple, cast
Symbol = str
@dataclass
class Reaction:
# output this produces
symbol: Symbol
quantity: int
inputs: Dict[Symbol, int]
@classmethod
def from_line(cls, line: str) -> Reaction:
inputs, output = map(str.strip, line.split("=>"))
def symbol_quantity(s: str) -> Tuple[Symbol, int]:
q, sym = map(str.strip, s.split())
return cast(Symbol, sym), int(q)
return cls(
*symbol_quantity(output),
dict(symbol_quantity(s) for s in inputs.split(",")),
)
Reactions = Dict[Symbol, Reaction]
def read_reactions(lines: Iterable[str]) -> Reactions:
return {reaction.symbol: reaction for reaction in map(Reaction.from_line, lines)}
def minimum_ore(reactions: Reactions, fuel: int = 1) -> int:
need = defaultdict(int)
need["FUEL"] = fuel
while any((symbol := k) for k, v in need.items() if k != "ORE" and v > 0):
reaction, needed = reactions[symbol], need[symbol]
multiplier = ceil(needed / reaction.quantity)
for input, quantity in reaction.inputs.items():
need[input] += multiplier * quantity
need[symbol] -= reaction.quantity * multiplier
return need["ORE"]
tests = {
(
"9 ORE => 2 A\n8 ORE => 3 B\n7 ORE => 5 C\n3 A, 4 B => 1 AB\n5 B, 7 C => 1 BC\n"
"4 C, 1 A => 1 CA\n2 AB, 3 BC, 4 CA => 1 FUEL"
): 165,
(
"157 ORE => 5 NZVS\n165 ORE => 6 DCFZ\n44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL\n"
"12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ\n179 ORE => 7 PSHF\n177 ORE => 5 HKGWZ\n7 DCFZ, 7 PSHF => 2 XJWVT\n"
"165 ORE => 2 GPVTF\n3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT\n"
): 13312,
(
"2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG\n17 NVRVD, 3 JNWZP => 8 VPVL\n"
"53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL\n22 VJHF, 37 MNCFX => 5 FWMGM\n"
"139 ORE => 4 NVRVD\n144 ORE => 7 JNWZP\n5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC\n"
"5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV\n145 ORE => 6 MNCFX\n1 NVRVD => 8 CXFTF\n"
"1 VJHF, 6 MNCFX => 4 RFSQX\n176 ORE => 6 VJHF\n"
): 180697,
(
"171 ORE => 8 CNZTR\n7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL\n"
"114 ORE => 4 BHXH\n14 VRPVC => 6 BMBT\n6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL\n"
"6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT\n"
"15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW\n13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW\n"
"5 BMBT => 4 WPTQ\n189 ORE => 9 KTJDG\n1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP\n"
"12 VRPVC, 27 CNZTR => 2 XDBXC\n15 KTJDG, 12 BHXH => 5 XCVML\n3 BHXH, 2 VRPVC => 7 MZWV\n"
"121 ORE => 7 VRPVC\n7 XCVML => 6 RJRHP\n5 BHXH, 4 VRPVC => 5 LTCX"
): 2210736,
}
for testinput, expected in tests.items():
assert minimum_ore(read_reactions(testinput.splitlines())) == expected
import aocd
data = aocd.get_data(day=14, year=2019)
reactions = read_reactions(data.splitlines())
print("Part 1:", minimum_ore(reactions))
Part 1: 1920219
We already have a way to calculate how much ore we need for 1 fuel unit; all we have to do now is ask for more, until we know that we can't produce 'that much'. The trick is to get to maxfuel + 1 quickly.
Luckily, there is a direct relationship between ore input and fuel output; we can take the ratio between how much we needed for our current attempt, and the maximum, and use that to increment our fuel guess. Then add 1 to see if that's too much. Note that as we get close, we might actually decrease our guess, so we need to make sure we don't actually go down (by using max(..., fuel).
ORE: int = 10**12
def maximum_fuel(reactions: Reactions) -> int:
fuel = 2
while (needed := minimum_ore(reactions, fuel)) <= ORE:
fuel = max(fuel * ORE // needed, fuel) + 1
return fuel - 1
part2_tests = {
# minimum from part 1 test: expected
13312: 82892753,
180697: 5586022,
2210736: 460664,
}
for testinput, minimum in tests.items():
expected = part2_tests.get(minimum)
if not expected:
continue
assert maximum_fuel(read_reactions(testinput.splitlines())) == expected
print("Part 2:", maximum_fuel(reactions))
Part 2: 1330066