Advent of Code 2019 - Day 14
Advent of Code 2019 - Day 14
Find my full solution repo here.
Think Before You Code
In order to avoid the mistake I made on day 12, I spent a while thinking about the proper approach to this problem before writing a single line of code. My main insights were:
- Each chemical can only be created by a single reaction. This significantly reduces the complexity of the problem, because you don’t have to compare different ways of producing a chemical.
- Given (1), you can model fuel’s supply chain as a directed graph of reactions, where each child node holds info about the reaction (since there can only be one) that creates each reagent (input) of the current reaction.
I modeled this graph using the following class definitions:
class Chemical:
def __init__(self, count, name):
self.count = count
self.name = name
class Reaction:
def __init__(self, reagents, product):
self.reagents = reagents
self.product = product
class ReactionNode:
def __init__(self, reaction, parent):
self.reaction = reaction
self.parent = parent
self.children = []
Building a Graph
With a list of Reaction
s given by the puzzle input, I set to building the
graph with a recursive approach. Some reactions are duplicated, since each
chemical is traced all the way back to its base ORE. However, I think that’s an
acceptable tradeoff given how much easier it is to reason about the problem with
a data structure that fits the problem.
def build_graph(reactions, chemical, parent):
reaction = reactions[find_reaction(reactions, chemical)]
cur_node = ReactionNode(reaction, parent)
if parent is not None:
parent.children.append(cur_node)
if cur_node.reaction.reagents[0].name == "ORE":
return
for reagent in reaction.reagents:
build_graph(reactions, reagent.name, cur_node)
if cur_node.reaction.product.name == "FUEL":
return cur_node
# List of `Reaction`s
reactions = prep_input("./input/day14.txt")
graph_root = build_graph(reactions, "FUEL", None)
At What Cost?
Now that I had a working data structure, all I really have to do is traverse the graph and sum the costs. I again used a recursive approach to this by priming a dictionary of “costs” with my goal (a single unit of fuel) and then traversed the graph.
def calculate_cost(costs, node):
product_cost = costs[node.reaction.product.name]
product_yield = node.reaction.product.count
reaction_ct = product_cost // product_yield
if product_cost % product_yield > 0:
reaction_ct += 1
costs[node.reaction.product.name] -= product_yield * reaction_ct
for reagent in node.reaction.reagents:
try:
costs[reagent.name] += reagent.count * reaction_ct
except:
costs[reagent.name] = reagent.count * reaction_ct
for child in node.children:
calculate_cost(costs, child)
costs = {"FUEL": 1}
calculate_cost(costs, graph_root)
min_ore = costs["ORE"]
print("part 1: " + str(min_ore))
This function calculates each cost in terms of the child reactions and does so until getting to the deepest nodes, which have “ORE” as inputs.
Now Try One Trillion
I used the same method of passing cost requirements in terms of fuel to the cost
function for part 2, with a twist. I ran a binary search to find the optimal
fuel output by checking that I had maximized the ore usage and then printing
mid
(the target fuel output) as the solution.
low = 1
high = 1000000000000
found = False
while not found:
mid = (low + high) // 2
costs = {"FUEL": (low + high) // 2}
calculate_cost(costs, graph_root)
ore_diff = 1000000000000 - costs["ORE"]
if ore_diff < min_ore and ore_diff > 0:
found = True
elif ore_diff > 0:
low = mid
else:
high = mid
print("part 2: " + str(mid))
This was a fantastic puzzle! Also, I’m now officially more than halfway done - technically I have been since finishing day 13 part 2, but I didn’t point it out in that post. :)
Find my full solution repo here.