Discussion on: Advent of Code 2019 Solution Megathread - Day 14: Space Stoichiometry

View post
After much stewing and drawing diagrams, I realized it was an acyclic directed graph. It's always a graph! Part 2 took a little bit of pragmatic, targeted brute forcing because I was sleepy.
"""Make fuel out of ore based on stoichiometric recipes"""
from dataclasses import dataclass
from typing import List, Dict
from math import ceil


@dataclass
class Component:
    """An input component to a reaction"""
    name: str
    quantity: int


@dataclass
class Equation:
    """A stoichiometric reaction equation using multiple ingredients to make some output"""
    name: str
    quantity: int
    ingredients: Dict[str, Component]


@dataclass
class Node:
    """A node in a dependency graph of stoichiometric equations.

    Nodes are ingredients.  They have dependents (things that use them
    as inputs) and dependencies (things they need to make themselves).

    Dynamically, they resolve themselves by listening to their dependents
    telling them how much of themself they need and, based on the equations,
    calculating the minimum amount that can be made to achieve that.
    """
    name: str
    dependents: List["Node"]
    dependencies: List["Node"]
    amount_needed: int = 0
    amount_made: int = 0
    resolved: bool = False


def parse(text):
    """Parses input text to build the recipes database.

    Expects text in the form of equations (one per line):
    3 IMFS, 4 ABCD, 1 EFGH => 6 OUTP

    Returns a dict of output names to recipe Equations.
    """
    result = dict()
    for line in text.splitlines():
        inputs, outputs = line.split(" => ")
        ingredients = dict()
        for inp in inputs.split(", "):
            qty, name = inp.split()
            ingredients[name] = Component(name, int(qty))
        out_qty, out_name = outputs.split()
        result[out_name] = Equation(out_name, int(out_qty), ingredients)

    # Additionally, ORE is free.  You can make 1 ORE with no inputs.
    result["ORE"] = Equation(1, dict())
    return result


def generate_digraph(recipes: Dict[str, Equation]) -> Dict[str, Node]:
    """Generates a graph of component dependencies."""
    digraph = {name: Node(name, [], []) for name in recipes}

    for name, eqn in recipes.items():
        for ingredient_name in eqn.ingredients:
            digraph[name].dependencies.append(digraph[ingredient_name])
            digraph[ingredient_name].dependents.append(digraph[name])

    return digraph


def resolve_digraph(fuel: int, recipes: Dict[str, Equation], digraph: Dict[str, Node]):
    """Based on the desired amount of fuel, calculates how much of each 
    component is needed, and, based on output amounts in the recipes,
    how much of each component is actually created to minimize waste.

    Initializes information at FUEL--the top of the graph--and starts
    solving recursively from the bottom of the graph: ORE.
    """
    digraph["FUEL"].amount_needed = fuel
    resolve(digraph["ORE"], recipes)


def resolve(node: Node, recipes: Dict[str, Equation]):
    """Resolve a node.

    A node can be resolved if all of the components that depend on it
    have been resolved and have decided how much of it they need.
    Then, it calculates how much should be made based on the recipes.
    And it informs its dependencies how much of each of them it will
    need.
    """
    for dependent in node.dependents:
        if not dependent.resolved:
            resolve(dependent, recipes)

    needed = node.amount_needed
    possible = recipes[node.name].quantity
    batches = ceil(needed / possible)
    node.amount_made = batches * possible

    for dependency in node.dependencies:
        dependency.amount_needed += batches * \
            recipes[node.name].ingredients[dependency.name].quantity

    node.resolved = True


if __name__ == "__main__":
    with open("data/day14.txt") as f:
        recipes = parse(f.read())
        digraph = generate_digraph(recipes)

    # Part 1: How much ORE to make 1 FUEL?
    resolve_digraph(1, recipes, digraph)
    print(f"Amount of ore needed: {digraph['ORE'].amount_made}")

    # Part 2: How much FUEL can you make with 1 ORE.
    # Actually, I started 'fuel' at 1 and ran for a while to collect
    # data points.  I graphed it, found the approximate trend line,
    # hedged low, and used that new number as my start point.
    # It was only a few iterations before I found the real answer :)
    fuel = 1934973
    while True:
        digraph = generate_digraph(recipes)
        resolve_digraph(fuel, recipes, digraph)
        if digraph["ORE"].amount_made > 1_000_000_000_000:
            print(f"{fuel - 1} fuel possible on a trillion ore.")
            break

        print(f"{fuel} fuel needs {digraph['ORE'].amount_made} ore.")
        fuel += 1