2019-12-14 - Space Stoichiometry
(original .ipynb)
Day 14 puzzle input is a set of sequences (mine is here) like "10 ORE => 10A", which would mean "You can produce 10 of resource 'A' using 10 of the'ORE' resource". Part 1 involves using these reactions to determine the minimum amount of ORE required to produce 1 "FUEL". Part 2 involves going the other way - finding how much FUEL you can produce with 1 trillion ORE.
quantity_idx = 0
component_idx = 1
class ReactionResult:
def __init__(self, quantity_produced, required):
self.quantity_produced = quantity_produced
self.required = required
def __repr__(self):
if not self.required:
return str(self.quantity_produced)
return f"{self.quantity_produced} <= (" + ", ".join([f"{qty}x{comp}" for qty,comp in self.required]) + ")"
def parse_component(component_str):
quantity_str, component_str = component_str.strip().split(" ")
return (int(quantity_str), component_str)
def parse_reactions(reactions_list_str):
reactions = {
"ORE": ReactionResult(1, None)
}
for reaction_str in reactions_list_str:
components_str, result_str = reaction_str.split("=>")
result_amount, result_component = parse_component(result_str)
components = [ parse_component(component_str) for component_str in components_str.split(",") ]
reactions[result_component] = ReactionResult(result_amount, components)
return reactions
def ore_for_component(reactions, quantity, component, spares, level=0, debug=False):
if component in spares:
# if the amount required or more is spare we don't need any more reactions
# so just update the structure and return 0
if spares[component] >= quantity:
spares[component] -= quantity
return 0
# if we have less spare, than is required, then just subtract the
# spare amount from the quantity required and continue with the lesser
# quantity
elif spares[component] < quantity:
quantity -= spares[component]
spares[component] = 0
if component not in reactions:
raise Exception(f"Unknown component {component}")
reaction = reactions[component]
reaction_count = int(quantity / reaction.quantity_produced)
if (reaction_count * reaction.quantity_produced) < quantity:
reaction_count += 1
# if we'll produce more than we need, add some to the spares registry
if reaction_count * reaction.quantity_produced > quantity:
spare_quantity = (reaction_count * reaction.quantity_produced) - quantity
if component in spares:
spares[component] += spare_quantity
else:
spares[component] = spare_quantity
if debug:
left_padding = "".join(level * ["\t"])
print(f"{left_padding}{quantity} x {component}")
# we have a raw material which requires no reactions, so just return
# the quantity that was requested
if not reaction.required:
return quantity
total_ore = 0
for required_quantity, required_component in reaction.required:
total_ore += ore_for_component(reactions, reaction_count * required_quantity, required_component, spares, 1 + level, debug)
return total_ore
test_reactions0 = [
"10 ORE => 10 A",
"1 ORE => 1 B",
"7 A, 1 B => 1 C",
"7 A, 1 C => 1 D",
"7 A, 1 D => 1 E",
"7 A, 1 E => 1 FUEL"
]
test_reactions1 = [
"9 ORE => 2 A",
"8 ORE => 3 B",
"7 ORE => 5 C",
"3 A, 4 B => 1 AB",
"5 B, 7 C => 1 BC",
"4 C, 1 A => 1 CA",
"2 AB, 3 BC, 4 CA => 1 FUEL"
]
test_reactions2 = [
"157 ORE => 5 NZVS",
"165 ORE => 6 DCFZ",
"44 XJWVT, 5 KHKGT, 1 QDVJ, 29 NZVS, 9 GPVTF, 48 HKGWZ => 1 FUEL",
"12 HKGWZ, 1 GPVTF, 8 PSHF => 9 QDVJ",
"179 ORE => 7 PSHF",
"177 ORE => 5 HKGWZ",
"7 DCFZ, 7 PSHF => 2 XJWVT",
"165 ORE => 2 GPVTF",
"3 DCFZ, 7 NZVS, 5 HKGWZ, 10 PSHF => 8 KHKGT"
]
test_reactions3 = [
"2 VPVL, 7 FWMGM, 2 CXFTF, 11 MNCFX => 1 STKFG",
"17 NVRVD, 3 JNWZP => 8 VPVL",
"53 STKFG, 6 MNCFX, 46 VJHF, 81 HVMC, 68 CXFTF, 25 GNMV => 1 FUEL",
"22 VJHF, 37 MNCFX => 5 FWMGM",
"139 ORE => 4 NVRVD",
"144 ORE => 7 JNWZP",
"5 MNCFX, 7 RFSQX, 2 FWMGM, 2 VPVL, 19 CXFTF => 3 HVMC",
"5 VJHF, 7 MNCFX, 9 VPVL, 37 CXFTF => 6 GNMV",
"145 ORE => 6 MNCFX",
"1 NVRVD => 8 CXFTF",
"1 VJHF, 6 MNCFX => 4 RFSQX",
"176 ORE => 6 VJHF",
]
test_reactions4 = [
"171 ORE => 8 CNZTR",
"7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL",
"114 ORE => 4 BHXH",
"14 VRPVC => 6 BMBT",
"6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL",
"6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT",
"15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW",
"13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW",
"5 BMBT => 4 WPTQ",
"189 ORE => 9 KTJDG",
"1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP",
"12 VRPVC, 27 CNZTR => 2 XDBXC",
"15 KTJDG, 12 BHXH => 5 XCVML",
"3 BHXH, 2 VRPVC => 7 MZWV",
"121 ORE => 7 VRPVC",
"7 XCVML => 6 RJRHP",
"5 BHXH, 4 VRPVC => 5 LTCX"
]
assert 31 == ore_for_component(parse_reactions(test_reactions0), 1, "FUEL", {})
assert 165 == ore_for_component(parse_reactions(test_reactions1), 1, "FUEL", {})
assert 13312 == ore_for_component(parse_reactions(test_reactions2), 1, "FUEL", {})
assert 180697 == ore_for_component(parse_reactions(test_reactions3), 1, "FUEL", {})
assert 2210736 == ore_for_component(parse_reactions(test_reactions4), 1, "FUEL", {})
puzzle_reactions = [ l.strip() for l in open("puzzle_input/day14.txt", "r").readlines() ]
print(ore_for_component(parse_reactions(puzzle_reactions), 1, "FUEL", {}))
374457
one_trillion = 1_000_000_000_000
# yes we are going to brute force this one too, thankyouverymuch
def find_a_trillion_ore(increment, reactions_table, ore_target):
current_guess = increment
ore_required = ore_for_component(parse_reactions(reactions_table), current_guess, "FUEL", {}, 0, False)
previous_guess = one_trillion - ore_required
while ore_required != ore_target:
if ore_required > ore_target:
# if we overshot it then go back, step down the increment a bit and try again
current_guess -= increment
increment = int(increment / 2)
else:
# it's late and this is 99/100 gonna be the answer so it'll have to do
if previous_guess == current_guess and increment == 1:
break
current_guess += increment
ore_required = ore_for_component(parse_reactions(reactions_table), current_guess, "FUEL", {}, 0, False)
difference = one_trillion - ore_required
previous_guess = current_guess
return current_guess
# assert 82892753 == find_a_trillion_ore(65536, test_reactions2, one_trillion)
assert 5586022 == find_a_trillion_ore(65536, test_reactions3, one_trillion)
assert 460664 == find_a_trillion_ore(65536, test_reactions4, one_trillion)
print(find_a_trillion_ore(65536, puzzle_reactions, one_trillion))
3568888