# 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:

1. 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.
2. 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.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
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.