Advent of Code 2019 - Day 14

Posted on 2020-01-01

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 Reactions 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.